Question

Data Structures and Algorithm Analysis in C++ by Clifford Shaffer

Devise an efficient algorithm to sort a set of numbers with values in the range 0 to 30, 000. There are no duplicates. Keep memory requirements to a minimum.

Answer 1

Insertion sort, bubble sort, and selection sort has O(n^2) sorting algorithms                                                          Quicksort, which is worst-case  O(n^2) but quite often O(nlogn) with good constants and properties.                  The O(nlogn) algorithms, like merge-sort and heap-sort, which are also good general-purpose sorting algorithms.

Radix Sort is the answer. The idea of Radix Sort is to do digit by digit sort starting from least significant digit to most significant digit. Radix sort uses counting sort as a subroutine to sort.

Radix Sort is the answer. The idea of Radix Sort is to do digit by digit sort starting from least significant digit to most significant digit. Radix sort uses counting sort as a subroutine to sort.