Thursday, January 24, 2008

Techy: Questions - hints

Hints to questions asked in my earlier post Techy: Questions

  1. The random function in Unix gives a number between 0 and RAND_MAX (which is fairly large). So starting with the 1st index as seed, call random function K-1 times with the seed for each call being the output of the previous call of the random function. Once these K numbers are available, sort them and iterate on the list using these numbers.
  2. Try using a modification of the quicksort alogrithm, with the pivot at the kth item. Pivots in subsequent iterations will also be the kth item of the original list. The actual location of the pivot in the sublist will depend on the size of the sublist and of any sub lists which have smaller entries than the sublist under consideration.

No comments: