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();
}
}
This comment has been removed by the author.
ReplyDelete