Implement, time & rank various sorting algorithms
Quick Sort is based on the divide and conquer algorithm. Pick an element as a pivot and partition the array around the selected pivot. Two partitions (left & right) are made by placing array elements in the correct position relative to the pivot. The pivot is in-place and then partitions have to be sorted recusively
Merge Sort - works by dividing an array into smaller subarrays (left & right). Repeat dividing the array till subarrays contains a single element. Sorting each subarray, while merging subarrays back together.
Tim Sort and Tim Sort recursive are hybrid, stable sorting algorithm, derived from merge sort and insertion sort. Used in Java’s Arrays.sort(), Python’s sorted() and sort() functions. First sort a small run using Insertion Sort, then merges the pieces using a merge of merge sort. Divide the array into blocks known as RUN. Sort those runs using insertion sort and then merge runs.
Heap Sort is a comparison-based sorting technique based on Binary Heap data structure. It is similar to the selection sort where we first find the minimum element and place the minimum element at the beginning. Repeat the same process for the remaining elements.
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. This algorithm is not suitable for large data sets as its average and worst-case time complexity is quite high.
Insertion Sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.
Selection Sort is a simple and efficient sorting algorithm that works by repeatedly selecting the smallest (or largest) element from the unsorted portion of the list and moving it to the sorted portion of the list.
Tree Sort is a sorting algorithm that is based on Binary Search Tree data structure. It first creates a binary search tree from the elements of the input list or array and then performs an in-order traversal on the created binary search tree to get the elements in sorted order.
Shell Sort is mainly a variation of Insertion Sort. In insertion sort, we move elements only one position ahead. When an element has to be moved far ahead, many movements are involved. The idea of ShellSort is to allow the exchange of far items.
Bucket Sort works by distributing the elements into a fixed number of buckets based on their values and then sorting each bucket individually. It is efficient when the input data is uniformly distributed over a range. The algorithm's performance depends on the distribution of the data and the number of buckets used.
Radix Sort is a stable sorting subroutine-based integer sorting algorithm. It is a sorting algorithm that does not use comparisons to sort a collection of integers. It classifies keys based on individual digits with the same significant position and value.
- Find out the maximum element in the array
- Initialize an array called count of length max+1.
- Store the count of each element at their respective index in count array.
For example: if the count of element 3 is 2 then, 2 is stored in the 3rd position of count array. If element "5" is not present in the array, then 0 is stored in 5th position.
- Store cumulative sum of the elements of the count array. It helps in placing the elements into the correct index of the sorted array.
- Find the index of each element of the original array in the count array. This gives the cumulative count. Place the element at the index calculated as shown in figure below.
- After placing each element at its correct position, decrease its count by one.