Definition:
A sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are either numerical order or lexicographical order.
Generally, sorting algorithms are classified into two different categories:
1.Comparison sort:
Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort, Heap Sort
2. Non-comparison sort:
Counting Sort, Radix Sort
The table below provides a comparison for 8 kinds of algorithms based on time complexity, space complexity, stability.
Now, let’s dive deep to discuss 8 basic sort algorithms in the table.
1.Bubble Sort:
Algorithm
Bubble sort is a simple sorting algorithm. It works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. Because it only uses comparisons to operate on elements, it is a comparison sort.
Implementation:
function bubbleSort(arr) {let len = arr.length;for (let i = 0; i < len - 1; i++) {for (let j = 0; j < len - 1 - i; j++) {if (let[j] > let[j+1]) { //swaplet temp = arr[j+1];arr[j+1] = arr[j];arr[j] = temp;}}}return arr;}
2.Selection Sort
Algorithm
- Find the minimum value in the list
- Swap it with the value in the first position
- Repeat the steps above for the remainder of the list (starting at the second position and advancing each time)
Implementation:
function selectionSort(arr) {let len = arr.length;let minIndex, temp;for (var i = 0; i < len - 1; i++) {minIndex = i;for (var j = i + 1; j < len; j++) {if (arr[j] < arr[minIndex]) { // find minimum numberminIndex = j;}}temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}return arr;}
3.Insertion Sort
Algorithm
Every iteration of insertion sort removes an element from the input data, inserting it into the correct position in the already-sorted list until no input elements remain. The choice of which element to remove from the input is arbitrary and can be made using almost any choice algorithm.
Sorting is typically done in-place. The resulting array after k iterations has the property where the first k+1 entries are sorted. In each iteration the first remaining entry of the input is removed, inserted into the result at the correct position, thus extending the result.
Implementation:
function insertionSort(arr) {let len = arr.length;let preIndex, current;for (var i = 1; i < len; i++) {preIndex = i - 1;current = arr[i];while (preIndex >= 0 && arr[preIndex] > current) {arr[preIndex + 1] = arr[preIndex];preIndex--;}arr[preIndex + 1] = current;}return arr;}
4. Merge Sort
Algorithm
Conceptually, a merge sort works as follows:
- If the list is of length 0 or 1, then it is already sorted. Otherwise:
- Divide the unsorted list into two sublists of about half the size.
- Sort each sublist recursively by re-applying merge sort.
- Merge the two sublists back into one sorted list.
Implementation:
function mergeSort(arr) {let len = arr.length;if (len < 2) {return arr; // base case}let middle = Math.floor(len / 2),left = arr.slice(0, middle),right = arr.slice(middle);return merge(mergeSort(left), mergeSort(right));}function merge(left, right) {let result = [];while (left.length>0 && right.length>0) {if (left[0] <= right[0]) {result.push(left.shift());}else {result.push(right.shift());}}while (left.length) result.push(left.shift());
while (right.length) result.push(right.shift());return result;}
5. Quick Sort
Algorithm
Quicksort sorts by employing a divide and conquer strategy to divide a list into two sub-lists.
The steps are:
- Pick an element, called the pivot, from the list.
- Reorder the list so that all elements which are less than the pivot come before the pivot and so that all elements greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
- Recursively sort the sub-list of lesser elements and the sub-list of greater elements. The base case of the recursion is lists of size zero or one, which are always sorted.
Implementation:
function quickSort(arr, left, right) {let len = arr.length,
let partitionIndex,
let left =typeof left !='number' ? 0 : left,
right =typeof right !='number' ? len - 1 : right;if (left < right) {partitionIndex = partition(arr, left, right);quickSort(arr, left, partitionIndex-1);quickSort(arr, partitionIndex+1, right);}return arr;}function partition(arr, left ,right) { // find pivotlet pivot = left,index = pivot + 1;for (var i = index; i <= right; i++) {if (arr[i] < arr[pivot]) {swap(arr, i, index);index++;}}swap(arr, pivot, index - 1);return index-1;}function swap(arr, i, j) {let temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
6. Heap Sort
Algorithm
The heapsort begins by building a heap out of the data set, and then removing the largest item and placing it at the end of the sorted array. After removing the largest item, it reconstructs the heap and removes the largest remaining item and places it in the next open position from the end of the sorted array.
This is repeated until there are no items left in the heap and the sorted array is full. Elementary implementations require two arrays — one to hold the heap and the other to hold the sorted elements. In an advanced implementation, however, we have an efficient method for representing a heap (complete binary tree) in an array and thus do not need an extra data structure to hold the heap.
Implementation:
let len; // Use in multiply scopes, declare as global variablefunction buildMaxHeap(arr) { // Build a heaplen = arr.length;for (var i = Math.floor(len/2); i >= 0; i--) {heapify(arr, i);}}function heapify(arr, i) {let left = 2 * i + 1,right = 2 * i + 2,largest = i;if (left < len && arr[left] > arr[largest]) {largest = left;}if (right < len && arr[right] > arr[largest]) {largest = right;}if (largest != i) {swap(arr, i, largest);heapify(arr, largest);}}function swap(arr, i, j) {let temp = arr[i];arr[i] = arr[j];arr[j] = temp;}function heapSort(arr) {buildMaxHeap(arr);for (var i = arr.length - 1; i > 0; i--) {swap(arr, 0, i);len--;heapify(arr, 0);}return arr;}
7. Counting Sort
Algorithm
The basic idea of Counting sort is to determine, for each input elements x, the number of elements less than x. This information can be used to place directly into its correct position. For example, if there are17 elements less than x, then x belongs in output position 18.
Implementation:
function countingSort(arr, maxValue) {let bucket =new Array(maxValue + 1),sortedIndex = 0;arrLen = arr.length,bucketLen = maxValue + 1;for (var i = 0; i < arrLen; i++) {if (!bucket[arr[i]]) {bucket[arr[i]] = 0;}bucket[arr[i]]++;}for (var j = 0; j < bucketLen; j++) {while(bucket[j] > 0) {arr[sortedIndex++] = j;bucket[j]--;}}return arr;}
8.Radix Sort (LSD)
Algorithm
1. Sort by the least significant digit of the key, usually with CountingSort or BucketSort.
2. Repeat for the rest of the digits, working up to the MSD. Because it’s stable, the ordering from the previous iterations remain. The end result will be sorted.
Implementation:
// LSD Radix Sortlet counter = [];function radixSort(arr, maxDigit) {let mod = 10;let dev = 1;for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {for(var j = 0; j < arr.length; j++) {let bucket = parseInt((arr[j] % mod) / dev);if(counter[bucket]==null) {counter[bucket] = [];}counter[bucket].push(arr[j]);}let pos = 0;for(var j = 0; j < counter.length; j++) {let value =null;if(counter[j]!=null) {while ((value = counter[j].shift()) !=null) {arr[pos++] = value;}}}}return arr;}
Summary:
There are a variety of sorting algorithms, for instance, Radix Sort has another type called MSD. Hope this article could help you to better understand some basic sorting algorithms. Please contact me if you discover anything wrong in implementation.
