Cluster Analysis on Big data

I have a very large data set on booking price of the hotel packages which is containing approximately 10 columns and 100,000 rows.

Majority of the variables are categorical here while there is only one continuous variable (i.e. price). Categorical variables are Cabin class, Board basis, In house rating, departure date, etc.

My problem is I want to do a cluster analysis on this big data set in order to group the prices which have similar variations with the departure date.

I used K-means algorithm for this purpose but it takes lot of time to clustering and it should be define the number of clusters at the beginning. But there is no way to find the number of clusters at the beginning.

So how can I do this efficiently? Is there any clustering algorithms to do this more efficiently than K-means algorithm?
I suggest that you take a random sample of your data and play around with it. Then do the same on another random sample. Use those results to find the number of clusters. Then use those results on your full data set.