Your cart is currently empty!
Goals: Understanding of radix and counting sorts. Understanding of selection. Requirements: Write a C program to compute the kth smallest number in a sequence of n integers in the range 0 . . . 999,999,999. The input will consist of: n and k. 1 ≤ k ≤ n…
Goals:
Requirements:
999,999,999. The input will consist of:
The input will be read from standard input as either keyboard typing or as a shell redirect (<) from a file. Do NOT prompt for a file name!
Your program will apply counting sort up to 9 times, once for each of the digit positions. The first sort will operate on the “hundred millions” digits. The last sort will operate on the “ones” digits. (This is similar to an MSD radix sort.) Each of the sorts may eliminate a significant fraction of the remaining values. This may also decrease n and k for the next counting sort.
Your program should indicate the number of remaining values after each counting sort.
Getting Started:
The third phase of this counting sort then gives the following starting positions:
Since the kth smallest number would be stored at array position k – 1 (2,000,000) after all digit positions have been processed, only the 400,000 inputs in the range 500,000,000 . . . 599,999,999 are kept in the fourth phase for the next counting sort. In addition, k is reduced to 100,001.
After running the second phase of the counting sort for the “ten millions” digits, suppose the count table contains:
The third phase of this counting sort gives the following starting positions:
Since the kth smallest number would be stored at array position k – 1 (100,000) after all digit positions have been processed, only the 40,000 inputs in the range 520,000,000 . . . 529,999,999 are kept in the fourth phase for the next counting sort. In addition, k is reduced to 30,001.
results against. This program demonstrates selection by partitioning.