Sort the following numbers using the quicksort algorithm discussed in class and described in the book. As an example, see the following:
15 9 25 18 6 1 13
At each pass, show the look of the array and indicate where the pivot number is after the iteration is complete:
Pass 1: 1 9 6 13 25 15 18
Pass 2: 1 6 9 13 25 15 18
Pass 3: 1 6 9 13 25 15 18
Pass 4: 1 6 9 13 25 15 18
Pass 5: 1 6 9 13 15 18 25
Pass 6: 1 6 9 13 15 18 25
Pass 7: 1 6 9 13 15 18 25
When is the item considered as sorted?
There are two cases:
1. When "partition" is done.
The sorted item is pointed by the index number returned by "partition".
2. When it goes to the base case of "sort".
The sorted item is pointed by the "left" pointer.
A snippet for sort and partition is shown below.
The complete source codes are shown after the diagram.
The diagrams below show step by step how Quicksort sort the list.
This version has three separete files; javascript, html, and css. In this version, the javascript is written with "use strict".
HTML File:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<title></title>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<link rel ="stylesheet" type = "text/css" href = "style.css" />
<script type ="text/javascript" src ="quicksort.js"></script>
</head>
<body>
<div id="wrapper">
<div id ="innerWrapper">
<h2>This is a QuickSort project in JavaScript</h2>
<div id="qsDataOrg">
<p> The list of numbers to be sorted </p>
</div>
<div id="qsDataAns">
<p> Here is the sorted list</p>
</div>
</div>
</div>
</body>
</html>
CSS File
body {
text-align:center;
font-family:"arial",verdana,sans-serif;
color: gray; /* gray */
background-color: #f2f2f2;
}
#wrapper{
margin: 0 auto;
width: 900px;
text-align: left;
/*outline-style: solid;*/
/*outline-color: blueviolet;*/
background: white /*#f2f2f2;*/
}
#innerWrapper{
/*outline-style: solid;*/
/*outline-color: blueviolet;*/
margin-left: 20px;
}
/* quicksort style */
#qsDataOrg, #qsDataAns{
color: gray;
}
JavaScript File
"use strict"
function QuickSort() {
this.qsData = [];
this.nElem = 0;
}
QuickSort.prototype.insert = function(val) {
this.qsData[this.nElem] = val;
this.nElem++;
};
QuickSort.prototype.numOfElement = function() {
return this.nElem;
}
QuickSort.prototype.display = function(id) {
var qsdOrg = document.getElementById(id);
for (var i = 0; i < this.nElem; i++ ) {
qsdOrg.appendChild(document.createTextNode(this.qsData[i]));
qsdOrg.appendChild(document.createTextNode(" "));
}
};
QuickSort.prototype.sort = function (left, right) {
// base case is: (right-left <= 0), omitted in code
if ((right - left) > 0) {
var pivot = this.qsData[right];
var px = this.partition(left, right, pivot);
this.sort(left, px - 1);
this.sort(px + 1, right);
return;
}
};
QuickSort.prototype.partition = function(left, right, pivot) {
var temp = right;
var flag = true;
while (flag) {
while (this.qsData[left] < pivot) {
left++;
}
while ((right > 0) && (this.qsData[--right] > pivot)) {
}
if (left < right) {
this.swap(left, right);
left++;
} else {
flag = false;
}
}
this.swap(left, temp);
return left;
};
QuickSort.prototype.swap = function(x , y) {
var temp = this.qsData[x];
this.qsData[x] = this.qsData[y];
this.qsData[y] = temp;
};
// becuase the document has to be loaded, before script runs,
// need window.onload. otherwise getElementBy stuff will return null
window.onload = function(){
var a = [2,41,15,93,23,5,63,10,4,43];
var qs = new QuickSort();
for (var i = 0; i < a.length; i++) {
qs.insert(a[i]);
}
//document.write("<br />"); <<< this wipes out display
// including "qsDataOrg" and gave me the null error for qsDataOrg.
qs.display("qsDataOrg");
qs.sort(0, qs.numOfElement() - 1);
qs.display("qsDataAns");
}
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<title></title>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<style type="text/css">
body {
text-align:center;
font-family:"arial",verdana,sans-serif;
background-color: #f2f2f2;
}
#wrapper{
margin: 0 auto;
width: 900px;
text-align: left;
background: white;
}
#innerWrapper{
margin-left: 20px;
}
#qsDataOrg, #qsDataAns{
color: gray;
}
</style>
<script type="text/javascript">
function QuickSort() {
this.qsData = [];
this.nElem = 0;
}
QuickSort.prototype.insert = function(val) {
this.qsData[this.nElem] = val;
this.nElem++;
};
QuickSort.prototype.numOfElement = function() {
return this.nElem;
}
QuickSort.prototype.display = function(id) {
var qsdOrg = document.getElementById(id);
for (i = 0; i < this.nElem; i++ ) {
qsdOrg.appendChild(document.createTextNode(this.qsData[i]));
qsdOrg.appendChild(document.createTextNode(" "));
}
};
QuickSort.prototype.sort = function (left, right) {
// base case is: (right-left <= 0), omitted in code
if ((right - left) > 0) {
var pivot = this.qsData[right];
var px = this.partition(left, right, pivot);
this.sort(left, px - 1);
this.sort(px + 1, right);
return;
}
};
QuickSort.prototype.partition = function(left, right, pivot) {
var temp = right;
var flag = true;
while (flag) {
while (this.qsData[left] < pivot) {
left++;
}
while ((right > 0) && (this.qsData[--right] > pivot)) {
}
if (left < right) {
this.swap(left, right);
left++;
} else {
flag = false;
}
}
this.swap(left, temp);
return left;
};
QuickSort.prototype.swap = function(x , y) {
var temp = this.qsData[x];
this.qsData[x] = this.qsData[y];
this.qsData[y] = temp;
};
// becuase the document has to be loaded, before script runs,
// need window.onload. otherwise getElementBy stuff will return null
window.onload = function(){
var a = [2,41,15,93,23,5,63,10,4,43];
var qs = new QuickSort();
for (i = 0; i < a.length; i++) {
qs.insert(a[i]);
}
//document.write("<br />"); <<< this wipes out display
// including "qsDataOrg" and gave me the null error for qsDataOrg.
qs.display("qsDataOrg");
qs.sort(0, qs.numOfElement() - 1);
qs.display("qsDataAns");
}
</script>
</head>
<body>
<div id="wrapper">
<div id ="innerWrapper">
<h2>This is a QuickSort project in JavaScript</h2>
<div id="qsDataOrg">
<p> The list of numbers to be sorted </p>
</div>
<div id="qsDataAns">
<p> Here is the sorted list</p>
</div>
</div>
</div>
</body>
</html>
Ref: Listing 7.3 in text book.
The book's code is, well, kind of messy.
Cannot stand the while-loop desined with break statements.
So, I fixed it!
///// quicksort /////
package cis55_quicksort03;
/**
* CIS-55 Data Structure
* Project: QuickSort
* Date: 2011-04-08
* @author tetsuro
*/
public class QuickSort {
private long[] qsData;
private int nElem;
public QuickSort(int max) {
qsData = new long[max];
nElem = 0;
}
public void insert(long value) {
qsData[nElem] = value;
nElem++;
}
public int size() {
return nElem;
}
public void display() {
System.out.print("Data = ");
for (int i = 0; i < nElem; i++) {
System.out.printf("%3d ",qsData[i]);
}
System.out.println("");
}
//
// I removed
// public void quickSort()
// because don't need this extra stuff
// Instead, use this
// public void sort(int left, int right)
// When call this in main, do this:
// arr.sort(0, arr.size()-1);
//
public void sort(int left, int right) {
// base case is: (right-left <= 0), which is omitted in code
if (right-left > 0) {
long pivot = qsData[right];
int px = partition(left, right, pivot);
sort(left, px - 1);
sort(px + 1, right);
}
}
//
// Along with removing break s statement,
// I removed the stuff like left-- and left+1.
// If nothing holds me back, I would say that's really stupid.
// The reason for that was, I think, to have
// a one-line while-loop for "left".
// Just have "left++" in the while loop.
//
private int partition(int left, int right, long pivot) {
int temp = right;
boolean flag = true;
while (flag) {
while (qsData[left] < pivot) {
left++;
}
while ((right > 0) && (qsData[--right] > pivot)) {
}
if (left < right) {
swap(left, right);
left++;
} else {
flag = false;
}
}
swap(left, temp);
return left;
}
public void swap(int x, int y) {
long temp;
temp = qsData[x];
qsData[x] = qsData[y];
qsData[y] = temp;
}
}
///// main /////
package cis55_quicksort03;
/**
* CIS-55 Data Structure
* Project: QuickSort
* Date: 2011-04-08
* @author tetsuro
*/
public class QuickSortApp {
public static void main(String[] args) {
int maxSize = 16;
QuickSort arr;
arr = new QuickSort(maxSize);
for (int i = 0; i < maxSize; i++) {
long n = (int)(java.lang.Math.random()*199);
arr.insert(n);
}
arr.display();
arr.sort(0, arr.size()-1);
arr.display();
}
}
