Sorting is one of the basic computation needs in programming and hence performance of sorting algorithms are critical. Usually, sorting algorithms are chosen based on it’s time and space complexities meeting the needs. Often algorithms which are simpler to implement do not yield better complexities. They are broadly classified as comparison based sort and non-comparison based sort.This page summarizes the key sorting algorithms being known to computation community. Follow the links in the bold sub-heading to learn more about individual algorithms along with sample program in java.
Minimum data element from the unsorted sub-array has been selected and swapped with the first element of the unsorted sub-array. Comparison based sort. Time complexity is quadratic.
Swaps adjacent elements in multiple passes until all the elements are sorted. Time complexity is quadratic and it’s a comparison based sort.
Like sorting a deck of cards. Pick the card from beginning to end one by one and place it in appropriate place in the sorted deck. Comparison based sort. Time complexity is quadratic.
Popular sort following divide and conquer strategy. Usually a 2 step recursive process. First step involves splitting the list into half at every step till the whole list is broken into individual elements. Second step is merging the splited list ensuring that at every step, partial list is sorted. Time complexity O(n log n). Comparison sort.
Preferred over merge sort due to its better space complexity. Worst case complexity is quadratic but rare. Quick sort is a recursive implementation. Based on the chosen pivot, list is partitioned fixing the pivot’s position. Left and the right partitions are further partitioned till the partition size is reduced to one element. While returning the end partitions and the chosen pivots form the sorted array.
Heap sort provides a stable sort of time complexity O(n log n). It’s based on binary heap. Heapify procedure is critical to this sort.
Counting sort
Counting sort provides sorting in linear time. It’s a non-comparison based sort. It’s suited only when the the elements to be sorted fall in a narrow range. Learn more on it from GeekforGeeks.
Radix sort
Radix sort work on the shortcoming of counting sort. If the range of elements to be sorted is broader, counting sort fails to O(n^2). Radix sort fills the gap by sorting digit by digit from least significant digit to the most significant digit. It internally uses radix sort. Learn more on it from GeekforGeeks.
Bucket sort
It’s a better performing sort. It’s suitable when the elements to be sorted are uniformly distributed. Input elements are bucketed and then individual buckets are sorted. Learn more on it from GeekforGeeks.
Visualizations are a great way to understand algorithms. Find the visualization tools on the above algorithms in link1 and link2.
Apache commons collection and Google guava provide number of sorted collections. JDK’s Collection.sort uses optimized merge sort and Arrays.sort uses optimized quick sort.
Sub page links
- Bubble Sort
- Heap sort implementation in Java
- Insertion sort in Java
- Merge Sort
- Quick Sort
- Selection Sort