2620
Ja
js-algos / files
7.9 KB
1// Insertion sort, the stable sort. 2// ================================ 3// 4// resources: 5// https://www.khanacademy.org/science/computer-science/v/insertion-sort-algorithm 6// http://www.nczonline.net/blog/2012/09/17/computer-science-in-javascript-insertion-sort/ 7 8// Ok, so what on earth is this? it's quite simple to explain visually. Think of bunch of cups, 9// each one had a marble with a value written on it. To order the values on the balls we start 10// with the second cup from the left and take the ball out. Now compare the value of the loose 11// ball with the value of the ball in the cup to the left of the empty cup. If the value is 12// greater then we grab that ball and move it to the now empty cup. Continue to do this while the 13// values of the balls in the cups to the left are greater than the loose balls vlaue. Once you 14// reach the last cup on the left or a value that is lesser than the loose ball's value, just 15// place the loose ball in the empty cup and move right to the next cup. 16// By the time you reach the last cup on the right, you'll have sorted the balls per their values 17// in ascending order. 18export function insertionSort (list) { 19 const len = list.length 20 let val, i, hole 21 22 for (i = 1; i < len; i += 1) { 23 val = list[i] 24 hole = i 25 26 while (hole > 0 && val < list[hole - 1]) { 27 list[hole] = list[hole - 1] 28 hole -= 1 29 } 30 31 list[hole] = val 32 } 33 34 return list 35} 36 37// Let's try merge sort, seems cool. 38// ================================ 39 40// Join two sorted arrays together. 41// 42// Create two pointers, one for each list, point them both to the value 43// at index 0. Keep comparing the idexes values and keep the lowest in the 44// joined list, increment by 1 the respective index. Do this until one of 45// the indexes matches the length of it's list. 46// Simple pile up the remainder of the orther list at the end of the joined 47// result. Ta-Da! 48function join (a, b) { 49 let joined = [] 50 let ai = 0 51 let bi = 0 52 53 while (ai < a.length && bi < b.length) { 54 if (a[ai] < b[bi]) { 55 joined.push(a[ai]) 56 ai += 1 57 } else { 58 joined.push(b[bi]) 59 bi += 1 60 } 61 } 62 63 return joined.concat(a.slice(ai).concat(b.slice(bi))) 64} 65 66// Now for the cool part 67// 68// Don't you love recursion? Base case is a single item list, that needs no 69// sort and can be returned as is. The recursive step finds a middle to the 70// list and cuts it in half. 71// We return the recursive call, so that we keep on splitting smaller and 72// smaller lists until their are of a single item, and then we return them 73// as we pile them back up in order one by one. 74export function mergeSort (list) { 75 if (list.length <= 1) { 76 return list 77 } 78 79 let m = Math.floor(list.length / 2) 80 let a = list.slice(0, m) 81 let b = list.slice(m) 82 83 return join(mergeSort(a), mergeSort(b)) 84} 85 86// quick sort baby! 87// ================ 88// 89// Chome's V8 uses this for Array.sort() for larger arrays (length 20ish or more) 90// much more to be found about quicksort here http://www.nczonline.net/blog/2012/11/27/computer-science-in-javascript-quicksort/ 91 92// easy peasy swap function. 93// 94// think 3 glasses, a red one with beer, a blue one with wine, and a white empty one. 95// we want the beer in the blue glass and the wine in the red one. 96// pour the beer in the white one, 97// pour the wine in the red one, 98// pour the beer into the blue one. 99function swap (list, first, second) { 100 const tmp = list[first] 101 list[first] = list[second] 102 list[second] = tmp 103} 104 105// creates a smaller partition of the array 106// 107// starting with a middle point because if the array is sorted you'll get 108// the worst possible performance if you choose the first or last elements. 109// while the left pointer is smaller or equal to the right pointer 110// move the left pointer to the right while it's value is less than the middle's value. 111// after, move the right pointer to the left while it's value is greater than the middle's value. 112// if the left pointer is smaller or equal to the right pointer swap the pointers values. 113// move the pointers one more time in each direction so that we continue in the correct direction. 114// return the left pointer so it can be used as the starting point for the next partition. 115 116function partition (list, left, right) { 117 const pivot = list[Math.floor((left + right) / 2)] 118 119 while (left <= right) { 120 while (list[left] < pivot) { 121 left += 1 122 } 123 124 while (list[right] > pivot) { 125 right -= 1 126 } 127 128 if (left <= right) { 129 swap(list, left, right) 130 left += 1 131 right -= 1 132 } 133 } 134 135 return left 136} 137 138// Only operate on lists with 2 or more values. 139// use default values for left and right if they are undefined (first run). 140// partition the array. 141// if the left pointer can still be moved right towards the index, call quicksort again in that direction. 142// if the right pointer can be moved left, call quicksort from the current index. 143export function quickSort (list, left, right) { 144 let idx 145 146 if (list.length >= 2) { 147 left = left === undefined ? 0 : left 148 right = right === undefined ? list.length - 1 : right 149 150 idx = partition(list, left, right) 151 152 if (left < idx - 1) { 153 quickSort(list, left, idx - 1) 154 } 155 156 if (idx < right) { 157 quickSort(list, idx, right) 158 } 159 } 160 161 return list 162} 163 164// This version of partition and quick sort calculates the pivot at random, 165// since the probability of the randomizer finding an item in the list that divides 166// the list in a 25-75 split is superior. 167// The expected time requirement becomes O(n log n), and the worst-case O(n^2) is very 168// unlikely to happen 169 170// First the function to randomly partition the list 171function randomizedPartition (list, left, right) { 172 const pivot = list[Math.floor(Math.random() * (right - left) + left)] 173 174 while (left <= right) { 175 while (list[left] < pivot) { 176 left += 1 177 } 178 179 while (list[right] > pivot) { 180 right -= 1 181 } 182 183 if (left <= right) { 184 swap(list, left, right) 185 left += 1 186 right -= 1 187 } 188 } 189 190 return left 191} 192 193export function randomizedQuickSort (list, left, right) { 194 let idx 195 196 if (list.length >= 2) { 197 left = left === undefined ? 0 : left 198 right = right === undefined ? list.length - 1 : right 199 200 idx = randomizedPartition(list, left, right) 201 202 if (left < idx - 1) { 203 randomizedQuickSort(list, left, idx - 1) 204 } 205 206 if (idx < right) { 207 randomizedQuickSort(list, idx, right) 208 } 209 } 210 211 return list 212} 213 214// Bubble sort, aka blubbly 215// ======================== 216 217// As the name says, bubbly over here compares all the values in sequence, "bubbling" the 218// higher values to the top. VERY SLOW! n^2 slow... 219 220export function bubbleSort (list) { 221 const len = list.length 222 let i, j 223 224 for (i = 0; i < len; i += 1) { 225 for (j = 0; j < (len - i); j += 1) { 226 if (list[j] > list[j + 1]) { 227 swap(list, j, j + 1) 228 } 229 } 230 } 231 232 return list 233} 234 235// shuffle, make a mess of things... 236// ================================= 237 238// slow and compreensive? fast and simple? 239// for each item in the array, create a random number within the length and swap. 240 241export function shuffle (list) { 242 let len = list.length 243 const max = len - 1 244 245 while (len) { 246 len -= 1 247 swap(list, len, Math.floor(Math.random() * max)) 248 } 249 250 return list 251} 252 253// Levenshtein distance (fuzzy text matching) 254// ========================================== 255 256// Levenshtein distance is the number of edits to change one word into another. For example 257// `git` and `got` have a Levenshtein distance of 1, since only one edit needs to be made 258// to tranform them into equal strings. Levenshtein is not very efficient and for performance 259// concerns it should only be applied to small strings at a time, since checking a massive text 260// would take forever(ish). 261 262export function fuzzy (a, b) { 263 // base cases 264 if (a === b) { return 0 } 265 if (!a.length || !b.length) { return 0 } 266 267 return Math.min( 268 fuzzy(a.substring(1), b) + 1, 269 fuzzy(b.substring(1), a) + 1, 270 fuzzy(a.substring(1), b.substring(1)) + (a[0] !== b[0] ? 1 : 0) 271 ) 272}