building menu...

JavaScript: DHTML Quick Sort

This page demonstrates the Quick Sort algorithm. This is the most advanced algorithm of the four presented, but has some problems w.r.t. speed and the fact that it is not a 'stable' sort (see link at bottom of page for details). At this stage we've found the Shell Sort algorithm to be more efficient with web data.

id	colour	random
1	orange	281
2	blue	652
3	orange	581
4	yellow	419
5	orange	146
6	blue	192
7	orange	197
8	orange	757
9	blue	450
10	purple	449
11	green	11
12	green	809
13	orange	653
14	orange	70
15	green	466
16	orange	826
17	yellow	928
18	green	736
19	yellow	100
20	green	800

[add rows to TABLE]

How does it work?

For a more detailed discussion on the sorting process, you can refer to the Bubble Sort page. The only difference between the two is the actual sorting algorithm, with the Quick Sort, in theory, being much faster:

  // global variables
  var col = 0;
  var parent = null;
  var items = new Array();
  var N = 0;

  function quicksort(m, n, desc)
  {
    if(n <= m+1) return;

    if((n - m) == 2) {
      if(compare(get(n-1), get(m), desc)) exchange(n-1, m);
      return;
    }

    i = m + 1;
    j = n - 1;

    if(compare(get(m), get(i), desc)) exchange(i, m);
    if(compare(get(j), get(m), desc)) exchange(m, j);
    if(compare(get(m), get(i), desc)) exchange(i, m);

    pivot = get(m);

    while(true) {
      j--;
      while(compare(pivot, get(j), desc)) j--;
      i++;
      while(compare(get(i), pivot, desc)) i++;
      if(j <= i) break;
      exchange(i, j);
    }

    exchange(m, j);

    if((j-m) < (n-j)) {
      quicksort(m, j, desc);
      quicksort(j+1, n, desc);
    } else {
      quicksort(j+1, n, desc);
      quicksort(m, j, desc);
    }
  }

  function sortTable(tableid, n, desc)
  {
    parent = document.getElementById(tableid);
    col = n;

    if(parent.nodeName != "TBODY")
      parent = parent.getElementsByTagName("TBODY")[0];
    if(parent.nodeName != "TBODY")
      return false;

    items = parent.getElementsByTagName("TR");
    N = items.length;

    // quick sort
    quicksort(0, N, desc);
  }

expand code box

This algorithm makes use of the get and compare function presented previously in the Bubble Sort demonstration, and the exchange function introduced in the Shell Sort demonstration.

The sorting functions presented so far have all been quite inefficient because they first have to read the DOM and then apply the various algorithms. To get around this limitation, each of the sorting algorithms has also been implemented using object-oriented (OOP) techniques.

All four methods (using OOP) are now available as external javascript files on the related page: DHTML Sorting Using OOP.

References

Quicksort is broken. Is it worth fixing?

DHTML Sorting Using OOP [JAVASCRIPT]
DHTML Quick Sort [JAVASCRIPT]
DHTML Sorting Using OOP - Example 1 [JAVASCRIPT]
DHTML Bubble Sort [JAVASCRIPT]
DHTML Insertion Sort [JAVASCRIPT]
DHTML Shell Sort [JAVASCRIPT]
Sorting Arrays of Arrays [PHP]
Sorting SimpleXMLElement Object arrays [PHP]

<JavaScript

Send a message to The Art of Web:

press <Esc> or click outside this box to close

Post your comment or question

JavaScript: DHTML Quick Sort

JavaScript: DHTML Quick Sort

How does it work?

References

Related Articles - Sorting Algorithms

Send a message to The Art of Web: