Quicksort

Quicksort is a special case of pivotsort. The difference is that at quicksort, the pivot element is a randomly chosen element of the sequence and that - in the case that the pivot element is equal to the current one - it is chosen by random to which sublist the current element goes.

This program sorts a list of random numbers. The numbers are stored in a variable with the name "fulllist" which is created by the random number generator:

      function randomlist(list)
        { var k;
          var h = window.prompt("How many Random Numbers should be sorted?");
          for (k=0;k<h;k=k+1)
           { list.push(Math.floor(100+900*Math.random())); } }
      .....
      var fulllist = new Array();
      randomlist(fulllist);

The list contains a h random numbers from 10 to 99 where h is given by the user. The sorting algorithm takes the unsorted elements out of the variable "fulllist" and stores afterwards the sorted elements into the same variable. The function "pivotsort" has a parameter a variable "list". If this variable has less than two entries, then "list" is already sorted and nothing is done. Otherwise, the first element of "list" is taken as pivot-element and the other elements of the list are processed one by one. Those smaller than the pivot-element go into the new sublist "lower" and the others into the new sublist "upper". At the end, the new values of the variable "list" are the elements in "lower" followed by the number in "pivot" followed by the elements in "upper". The implemented sorting algorithm is the following:

      function quicksort(list)
        { if (list.length < 2) { return; }
          var pivot = list[Math.floor(list.length*Math.random())];
          var current;
          var lower = new Array();
          var upper = new Array();
          while(list.length > 0)
            { current = list.shift();
              count = count+1;
              if ((current < pivot)||((current == pivot)&&(Math.random()>0.5)))
                   { lower.push(current); }
              else { upper.push(current); } }
          quicksort(lower); quicksort(upper);
          while (lower.length > 0) { list.push(lower.shift()); }
          while (upper.length > 0) { list.push(upper.shift()); }
          return; }

The variable "count" in the function is there to count the number of comparisons of elements to be sorted. Below a sample output of the algorithm.

Java Script starts here.

Java Script ends here.