Shasoosh
November 12th, 2009, 03:08 AM
There's an Hash table T[1..m]
n series with key numbers (k1,k2,k3...kn)
and an Hash function of some sort - h
we'll insert the n keys into the hash table with the h function (with stringing in case of a collision)
we'll use merge sort on the linked lists
we'll concatenate the linked lists in the T cell order
1.what's the Average case performance?
2.what's the worst case performance?
3. do you think that in any case we'll get a sorting of the keys (k1,k2,k3...kn)?
if not, in which case we will get a sorted series?
sorry for my English
thanks
n series with key numbers (k1,k2,k3...kn)
and an Hash function of some sort - h
we'll insert the n keys into the hash table with the h function (with stringing in case of a collision)
we'll use merge sort on the linked lists
we'll concatenate the linked lists in the T cell order
1.what's the Average case performance?
2.what's the worst case performance?
3. do you think that in any case we'll get a sorting of the keys (k1,k2,k3...kn)?
if not, in which case we will get a sorted series?
sorry for my English
thanks