xonecas.io
2620
Ja

js-algos / files

js-algos / lib / algos.js

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}