Quicksort Practice in Lab Exercises

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.

---

---

---

---

---

---

The Complete Source Code:

---

package cis55_quicksortassignment01;

/**

 * CIS-55 Data Structure

 * Project: QuickSort

 * Date:    2011-04-15

 * @author tee

 */

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("");
    }

    // When call this in main, do this: arr.sort(0, arr.size()-1);
    public void sort(int left, int right) {
        if (right <= left) {
            // base case
            System.out.printf("sorted: %2d\n", qsData[left]);   // debug
            display();
        } else {
            long pivot = qsData[right];
            int px = partition(left, right, pivot);
            System.out.printf("sorted: %2d\n", qsData[px]);     // debug
            display();
            sort(left, px - 1);
            sort(px + 1, right);
        }
    }
    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++;     // increment left after swap
            } 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;
    }
}

---

package cis55_quicksortassignment01;

/**
 * CIS-55 Data Structure
 * Project: QuickSort
 * Date:    2011-04-15
 * @author  tee
 */

public class Main {

    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.insert(15);
        arr.insert(9);
        arr.insert(25);
        arr.insert(18);
        arr.insert(6);
        arr.insert(1);
        arr.insert(13);

        System.out.println("Given un-sorted list: ");
        arr.display();
        System.out.println("");
        arr.sort(0, arr.size()-1);

        System.out.println("done!\n");
    }
}
 


.

---