Next up in Algorithms and Data Structures is Sorting. There are a number of ways you can sort the data you are given. Depending on the complexity, type of data and how much of it you have, will depend on the most efficient sorting technique used.
The first element is compared to the next element in the array. If the first element is greater than the second element, they get swapped. If the first element is smaller than the second element, you move onto the next element. And then you start again, until you reach the end of the array.
const bubbleSort = (arr) => {
let n = arr.length;
for (let i = 0; i < n; i++) {
let swapped = false;
for (let j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) {
break;
}
}
return;
};Uses the ‘divide and conquer’ concept. You divide the array into two and then sort each array. Once both sides are sorted, you merge them together.
const mergeArrays = (a, b) => {
const sortArr = [];
while (a.length && b.length) {
sortArr.push(a[0] > b[0] ? b.shift() : a.shift());
}
while (a.length) {
sortArr.push(a.shift());
}
while (b.length) {
sortArr.push(b.shift());
}
return sortArr;
};
const mergeSort = (arr) => {
if (arr.length < 2) return arr;
const middle = Math.floor(arr.length / 2);
const arrLeft = arr.slice(0, middle);
const arrRight = arr.slice(middle, arr.length);
const sortedLeft = mergeSort(arrLeft);
const sortedRight = mergeSort(arrRight);
return mergeArrays(sortedLeft, sortedRight);
};The array is split into sorted and unsorted. Values from the unsorted part are picked and place in the correct position in the sorted part of the array.
const insertionSort = (arr) => {
for (let i = 1; i < arr.length; i++) {
let currVal = arr[i];
let j;
for (j = i - 1; j >= 0 && arr[j] > currval; j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = currVal;
}
return arr;
};The array is divided into a sorted sunlist, which is built up from left to right of sorted values, with the sublist of the unsorted values filling the rest of the array.
const selectionSort = (arr) => {
for (let i = 0; i < arr.length - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < array.length; j++) {
if (array[j] < arr[minIndex]) {
minIndex = j;
}
}
[array[i], array[minIndex]] = [array[minIndex], array[i]];
}
return array;
};Keep dividing the array into smaller parts until each part is sorted.
const partition = (arr, start, end) => {
const pivot = arr[start]
let swapIndex = start
for (let i = start + 1; i <= end; i++) {
if (pivot > arr[i]) {
swapIndex++
}
if (i !== swapIndex) {
[arr[i], arr[swapIndex]] == [arr[swapIndex], arr[i]]
}
}
}
if (swapIndex !== start) {
[arr[swapIndex], arr[start]] = [arr[start], arr[swapIndex]]
}
return swapIndex
}
function quickSort (arr, start = 0, end = arr.length - 1) {
if (start >= end) return
let pivot = partition(arr, start, end)
// left
quickSort(arr, start, pivotIndex - 1)
// right
quickSort(arr, pivot + 1, end)
return arr
}
You have a subarray for each type of data that needs to be compared. You compare the first char or digit in each item, add the whole item to the subarray and then put it back into the array.
const getNum = (num, index) => {
const strNum = String(num);
let end = strNum.length - 1;
const foundNum = strNum[end - index];
if (foundNum === undefined) return 0;
else return foundNum;
};
const largestNum = (arr) => {
let largest = "0";
arr.forEach((num) => {
const strNum = String(num);
if (strNum.length > largest.length) largest = strNum;
});
return largest.length;
};
const radixSort = (arr) => {
let maxLen = largestNum(arr);
for (let i = 0; i < maxLength; i++) {
let buckets = Array.from({ length: 10 }, () => []);
for (let j = 0; j < arr.length; j++) {
let num = getNum(arr[j], i);
if (num !== undefined) buckets[num].push(arr[j]);
}
arr = buckets.flat();
}
return arr;
};worst-case: O(n2)
O(1)
O(nlogn)
O(n)
O(n)
O(1)
O(n^2)
O(1)
O(n log(n))
O(1)
O(nd)
O(1)
Write a function that takes in an array of integers and returns a sorted version of that array. Use the insertion Sort algorithm to sort the array.
array = [8, 5, 2, 6, 2][2, 2, 5, 6, 8]function insertionSort(array) {}function insertionSort(array) {
for (let i = 1; i < array.length; i++) {
let j = i - 1;
let temp = array[i];
while (j >= 0 && array[j] > temp) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = temp;
}
return array;
}You are given an array of integers and another array of three distinct integers. The first array is guaranteed to only contain integers that are in the second array, and the second array represents a desired order for the integers in the first array.
Write a function that sorts the first array according to the desired order in the second array.
The function should perform this in place.
array = [1, 0, 0, -1, -1, 0, 1, 1]
order = [0, 1, -1][0, 0, 0, 1, 1, 1, -1, -1]function threeNumberSort(array, order) {}function threeNumberSort(array, order) {
for (const item of order) {
let count = 0;
for (let i = 0; i < array.length; i++) {
let num = array[i];
if (num === item) {
array.splice(i, 1);
i--;
count++;
}
}
for (let i = 0; i < count; i++) {
array.push(item);
}
}
return array;
}Write a function that takes in an array of non-negative integers and returns a sorted version of that array. Use the Radix Sort algorithm to sort the array.
array = [8762m 654m 3008, 345, 87, 65, 234, 12, 2][2, 12, 65, 87, 234, 345, 654, 3009, 8762]function radixSort(array) {
// Write your code here.
return [];
}function getDigits(num, place) {
return Math.floor(Math.abs(num) / Math.pow(10, place)) % 10;
}
function digitCount(num) {
if (num === 0) return -1;
return Math.floor(Math.log10(Math.abs(num))) + 1;
}
function mostdigits(nums) {
let maxDigits = 0;
for (let i = 0; i < nums.length; i++) {
maxDigits = Math.max(maxDigits, digitCount(nums[i]));
}
return maxDigits;
}
function radixSort(array) {
let maxDigitCount = mostDigits(array);
for (let k = 0; k < maxdigitCount; k++) {
let digitBuckets = Array.from({ length: 10 }, () => []);
for (let i = 0; i < array.length; i++) {
let digit = getDigit(array[i], k);
digitBuckets[digit].push(array[i]);
}
array = [].concat(...digitBuckets);
}
return array;
}