Insertion sort takes each element an inserts it into the already-sorted part of the array at the bottom of it.
function insertionSort(arr) {
let n = arr.length;
for (let i = 1; i < n; i++) {
let key = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
The idea of quicksort is to partition the array around a pivot i such that all the elements from 0 to i are less than the element at i, and all the elements after i are greater than it. Then, it does this to the left half and the right half recursively, until the array is sorted.
function partition(arr,l,h) {
let i = l - 1;
let x = arr[h];
let temp;
for (let j = l; j < h; j ++) {
if (arr[j] <= x) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, h);
return i + 1;
}
function quickSort(arr, low = 0, high = arr.length - 1) {
if (low < high) {
let pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
Selection sort selects the minimum element in the unsorted part of the array, and swaps it so it goes to the end of the sorted part.
function selectionSort(arr) {
for (let i = 0; i < arr.length; i++) {
let min = i
for (let j = i + 1; j < arr.length; j++)
if (arr[j] < arr[min])
min = j
if (min !== i)
swap(arr, min, i);
}
return arr
}
Shell sort compares and swaps far-apart elements in early stages, so that later stages don't have as much work to do sorting.
function shellSort(data) {
let gap = data.length;
while ((gap = Math.floor(gap / 2)) > 0) {
for (let i = gap; i !== data_size; ++i) {
for (let j = i - gap; j >= 0 && data[j] > data[j + gap]; j -= gap) {
swap(data, j, j + gap);
}
}
}
}
An array of length 1 is sorted by definition. Merge sort merges these into one array of length 2; then, it merges 2 arrays of length 2 into one array of length 4; and so on.
function mergeSort(arr) {
let n = arr.length;
let temp = new Array(arr.length);
for (let size = 1; size < n; size *= 2) {
for (let left = 0; left < n - size; left += 2 * size) {
let mid = left + size - 1;
let right = Math.min(left + 2 * size - 1, n - 1);
merge(arr, temp, left, mid, right);
}
}
}
function merge(data, temp, start, mid, end) {
let left = start;
let right = mid;
let tmpIdx = start;
while (left < mid && right < end)
temp[tmpIdx++] = data[data[left] <= data[right]? left++: right++];
while (left < mid)
temp[tmpIdx++] = data[left++];
while (right < end)
temp[tmpIdx++] = data[right++];
for (let i = start; i < end; i++)
data[i] = temp[i];
}