xsnippet logotype

xsnippet

quickSort [ JavaScript ]

by Guest
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
const arrayOf100 = Array.from({ length: 100 }, () => Math.floor(Math.random() * 90));
const arrayOf1000 = Array.from({ length: 1000 }, () => Math.floor(Math.random() * 94));
const arrayOf10000 = Array.from({ length: 10000 }, () => Math.floor(Math.random() * 98));
const arrayOf100000 = Array.from({ length: 100000 }, () => Math.floor(Math.random() * 99));
const arrayOf1000000 = Array.from({ length: 1000000 }, () => Math.floor(Math.random() * 99));

function quickSort(array, s, e) {
  let start = s;
  let end = e;
  let pivot = array[Math.floor((start + end) / 2)];

  while (start <= end) {
    while (array[start] < pivot) {
      // checks whether elements before pivot on their place or should be moved to another side
      // if element on the right side increases start index
      start += 1;
    }
    while (array[end] > pivot) {
      // checks whether elements after pivot on their place or should be moved to another side
      // if element on the right side decrises end index
      end -= 1;
    }
    if (start <= end) {
      // if we are here this means taht we have found elements that need to be swapped
      // after swapping we need to update start and end positions to be able
      // to search further (we can use post increment and decrement to manipulate start and 
      // start values, but for readability I decided not to use them)
      [array[start], array[end]] = [array[end], array[start]];
      start += 1;
      end -= 1;
    }
  }

  if (s < end) {
    quickSort(array, s, end);
  }
  if (e > start) {
    quickSort(array, start, e);
  }
}

quickSort(arrayOf100, 0, arrayOf100.length-1);

console.time('quick100');
quickSort(arrayOf100, 0, arrayOf100.length-1);
console.timeEnd('quick100');

console.time('quick1000');
quickSort(arrayOf1000, 0, arrayOf1000.length-1);
console.timeEnd('quick1000');

console.time('quick10000');
quickSort(arrayOf10000, 0, arrayOf10000.length-1);
console.timeEnd('quick10000');

console.time('quick100000');
quickSort(arrayOf100000, 0, arrayOf100000.length-1);
console.timeEnd('quick100000');

console.time('quick 1m');
quickSort(arrayOf1000000, 0, arrayOf1000000.length-1);
console.timeEnd('quick 1m');