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).
To date we've found the Shell Sort algorithm to be more efficient with small-ish datasets - the kind of data displayed on websites.
Working Demonstration
| id | colour | random |
|---|---|---|
| 1 | purple | 120 |
| 2 | yellow | 760 |
| 3 | green | 614 |
| 4 | blue | 396 |
| 5 | yellow | 377 |
| 6 | yellow | 300 |
| 7 | red | 712 |
| 8 | red | 276 |
| 9 | yellow | 7 |
| 10 | yellow | 490 |
| 11 | purple | 641 |
| 12 | blue | 745 |
| 13 | yellow | 560 |
| 14 | orange | 59 |
| 15 | orange | 867 |
| 16 | red | 876 |
| 17 | blue | 16 |
| 18 | orange | 59 |
| 19 | yellow | 584 |
| 20 | yellow | 37 |
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;
var quicksort = function(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);
}
};
var sortTable = function(tableid, n, desc) {
parent = document.getElementById(tableid);
col = n;
if(parent.nodeName == "TABLE") {
parent = parent.getElementsByTagName("TBODY")[0];
}
if(parent.nodeName != "TBODY") {
return false;
}
items = parent.getElementsByTagName("TR");
N = items.length;
/* quick sort */
quicksort(0, N, desc);
};
Th quick sort algorithm makes use of the get and compare functions presented previously in the Bubble Sort demonstration combined with the exchange function introduced in the Shell Sort demonstration for swapping non-adjacent elements.
All four methods (using OOP) are now available as external javascript files which you can find linked in the article DHTML Sorting Using OOP.
References
Related Articles - Sorting Algorithms
- JavaScript DHTML Sorting Using OOP - Example 1
- JavaScript Sorting Algorithm Comparison
- JavaScript DHTML Bubble Sort
- JavaScript DHTML Shell Sort
- JavaScript DHTML Insertion Sort
- JavaScript DHTML Sorting Algorithms
- JavaScript DHTML Quick Sort
- PHP Sorting Arrays of Arrays
- PHP Sorting SimpleXMLElement Object arrays