Quicksort Algorithm in Javascript

Here’s a basic Quicksort algorithm. You can call this code using Node.js

1
2
3
4
5
6
7
8
9
10
11
var Sort = require('./quicksort.js');
list = [3, 4, 5,2, 5];
var sorted = Sort(list, function(a, b) {
  if (a > b) {
      return 1;
  } else if (a === b) {
      return 0;
  } else {
      return -1;
  }
});

have fun and hope this proves useful to somebody!

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
//quicksort.js
module.exports = function(list1, compareFunction) {
    var list = list1;
    var cmp = compareFunction;

    var swap = function(i, j) {
        /* swaps the indexer A[i] and A[j] */
        var _i = list[i];
        var _j = list[j];
        list[j] = _i;
        list[i] = _j;
    }

    var partition = function(p, r) {
        /* the partition function goes through the array
         *  list[
         */
        var r = r;
        var i = p; //on intiial pass, p is 0

        /* for each entry i where A[i] is less than A[r-1]
         * where r-1 is the index of the Penultimate item
         */
        //from j = 0 to j = r-1
        //exchange A[i] and A[j] if A[j] > A[r]
        for (var j = p; j < r; j++) {
            //console.log("lets try this ", list);
            //console.log("i : " + i + " j : " + j);
            if (cmp(list[j],list[r]) <= 0 ) {
                //swap them!! and then increment i
                swap(i, j);
                i++;
            }
        }

        swap(i, r);
        return i;


    }

    var quickSort = function(p, r) {
        if (p < r) {
            q = partition(p, r);
            quickSort(p, q - 1);
            quickSort(q + 1, r)

        }

    }

    var initialize = function() {
        quickSort(0, list1.length-1);

    }
    //compute the sorted value
    initialize();

    return list1;

}

Sorting Algorithms in Python - Part 1

I’m in a couple of weeks into Robert Sedgewick’s class on algorithms currently running on coursera. To round off the weekend I decided to reimpliment some of the classic sortting algorithms in python.

The compare function

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
    def cmp(a, b):
        if (a == b):
            return 0
        elif (a > b):
            return 1
        else:
            return -1

  def swap(i, j, array):
      swapv = array[i]
      array[i] = array[j]
      array[j] = swapv
      return array

  def biggest(array):
      i = 0
      biggest_val = array[0]
      biggest_index = i
      while(i < len(array)):
          if (array[i] > biggest_val):
              biggest_val = array[i]
              biggest_index = i
          i = i + 1
      return (biggest_index, biggest_val)

  def minv(array, start_index):
      i = start_index
      min_val = array[start_index]
      min_index = i
      while(i < len(array)):
          if (array[i] < min_val):
              min_val = array[i]
              min_index = i
          i = i + 1
      return (min_index, min_val)

  def min(array):
      return minv(array, 0)

Selection Sort

1
2
3
4
5
6
7
   def selectionSort(array):
      i = 0
      array1 = array
      while (i < len(array1)):
          array1 = swap(i, minv(array1, i)[0], array1)
          i = i + 1
      return array1

Insertion sort is just a specialized case of shellsort so I created a base composite function that encapsulates the core of both algorithms.

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
   def gapSort(array, gap):
      """helper function to aid insertion sort and shell sort"""
      i = 0
      array1 = array
      while (i < len(array)):
          if (i > 0):
              j = i
              while ((cmp(array1[j], array1[j-gap]) < 0) and (j != 0 ) ):
                  #while object at i is less than the one before it
                  swap(j, j-gap, array1)
                  j = j - 1
          i = i + 1
      return array1

  def insertionSort(array):
      return gapSort(array, 1)



  def shellSort(array):
      """sorts using the shellsort algorithm"""
      vals = [3*h+1 for h in range(len(array)/3)][::-1]
      for val in vals:
          array = gapSort(array, val)
      return array

Finally, Merge sort; Running in N log(N), it is the only algorithms other than Quicksort worth using on large datasets.

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
   def merge(array, p, q, r):
  """The merge function"""
      if ((r - p) > 1):
          left = array[p:q+1]
          loggr("left" + str(left))
          right = array[q+1:r+1]
          loggr("right"+ str(right))
          left.append('c')
          right.append('c')
          i = 0
          j = 0
          for k in range(p, r+1):
              if left[i] <= right[j]:
                  array[k] = left[i]
                  i = i + 1
              else:
                  array[k] = right[j]
                  j = j + 1
      elif ((r - p) == 1 ):
          if (array[r] < array[p]):
              i = array[p]
              j = array[r]
              array[p] = j
              array[r] = i



  def mergeSort(array):
      def sort(p, r, msg):
          if p < r:
              q = (p+r)/2
              if (r - p) > 1:
                  sort(p, q, "in left array")
                  sort(q+1, r, "right array")
              merge(array, p, q, r)
      sort(0, len(array)-1, "root")
      return array

Quick sort and its probabilistic guarantee of fast enough run time strikes me as the most mathematically perverse form of black magic. Beautiful in the inherent underlying fabric of its utility. I’ll cover that when I get to part 2.

Comments