Sorting
The selection and insertion, are relatively simple, but they are inefficient sequential sorts that use a pair of nested loops and require roughly n^2 comparisons to sort a list of n elements.
More efficient sorts are algorithms that lend themselves to a recursive implementation.
In addtion, the Quicksort is a divide and conquer algorithm. Quicksort first divides a large array into two smaller sub-arrays: the low elements and the high elements. Quicksort can then recursively sort the sub-arrays.
Quick Sort
The quick sort algorithm sorts a list by partitioning the list using an arbitrary chosen partition element and then recursively sorting the sublists on either side of the partition element.
General Strategy:
• First, choose one element of the list to act as a partition element.
• Next, partition the list so that all elements less than the partition element are to the left of that element and all elements greater than the partition element are to the right.
• Finally, apply this quick sort strategy recursively to both partitions.
• The choice of the partition element is arbitrary, we will use the first element in the list.
• For efficiency reasons, it would be nice if the partition element divided the list roughly in half, but the algorithm will work no matter what element is chosen as a partition
Example:
90 65 7 305 120 110 8
we would choose 90 as our partition element.
We would then rearrange the list, swapping the elements that are less than 90 to the left side and those that are greater than 90 to the right side, yielding:
8 65 7 90 120 110 305
We would then apply the quick sort algorithm separately to both partitions. This process continues until a partition contains only one element, which is inherently sorted. Once the initial partition element is determined and placed, it is never considered or moved again.
Here is the book version of the quicksort code:
//-----------------------------------------------------------------
// Sorts the specified array of integers using quick sort.
//-----------------------------------------------------------------
public static void quickSort (int[] numbers)
{
doQuickSort(numbers, 0, numbers.length - 1);
}
//-----------------------------------------------------------------
// Recursively sorts the portion of the given array beginning
// at start and ending at end.
//-----------------------------------------------------------------
private static void doQuickSort (int[] numbers, int start, int end)
{
if (start < end)
{
int middle = partition(numbers, start, end);
doQuickSort(numbers, start, middle);
doQuickSort(numbers, middle + 1, end);
}
}
//-----------------------------------------------------------------
// Partitions the array such that each value in [start, middle]
// is less than or equal to each value in [middle + 1, end].
// The index middle is determined in the procedure and returned.
//-----------------------------------------------------------------
private static int partition (int[] numbers, int start, int end)
{
int pivot = numbers[start];
int i = start - 1;
int j = end + 1;
// As the loop progresses, the indices i and j move towards each other.
// Elements at i and j that are on the wrong side of the partition are
// exchanged. When i and j pass each other, the loop ends and j is
// returned as the index at which the elements are partitioned around.
while (true)
{
i = i + 1;
while (numbers[i] < pivot)
i = i + 1;
j = j - 1;
while (numbers[j] > pivot)
j = j - 1;
if (i < j)
{
int tmp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = tmp;
}
else
{
return j;
}
}
}
Classwork:
1. Trace the quick sort using the data above using the code.
[90, 65, 7, 305, 120, 110, 8]
2. Write the pseudocode looking at the code.
Homework:
4. Under what conditions you have the worse case?
5. What data would yield to a best case and average case?
6. What is the big O notation for this sort for each case?
7. Can you think of a non-recursive QuickSort?
8. Write code for QuickSorting objects. Include compareTo() and toString() methods of the object’s class.
NOTE: WHAT FOLLOWS IS FOR YOUR ENRICHMENT ONLY
It is not part of the AP curriculum.
import java.util.Arrays;
// When we partition data we are dividing it into
// two parts. All items with data above a defined value
// will go in one part and the rest will go in the other
// The value that defines in which group data will go
// is known as the pivot value
public class Partitioning {
private static int[] theArray;
private static int arraySize;
public static void main(String[] args) {
Partitioning partitionArray = new Partitioning(10);
partitionArray.generateRandomArray();
System.out.println(Arrays.toString(Partitioning.theArray));
// Every item smaller than 35 will be on the left and
// everything bigger will be on the right
partitionArray.partitionArray(35);
System.out.println(Arrays.toString(Partitioning.theArray));
}
public void partitionArray(int pivot) {
// If leftPointer finds an item that is greater
// than pivot it stops and waits for the rightPointer
// to find a value less than pivot. Then the items
// are switched
// Starts at the left side of array before index 0
int leftPointer = -1;
// Starts at the right side of the array after the last index
int rightPointer = arraySize;
while (true) {
// Cycle through array until the end is reached
// or an item bigger than pivot is found. Then
// wait for rightPointer to finish cycling
while (leftPointer < (arraySize - 1)
&& theArray[++leftPointer] < pivot)
;
printHorzArray(leftPointer, rightPointer);
System.out.println(theArray[leftPointer] + " in index "
+ leftPointer + " is bigger than the pivot value " + pivot);
// Cycle through array until the beginning is reached
// or an item smaller than pivot is found.
while (rightPointer > 0 && theArray[--rightPointer] > pivot)
;
printHorzArray(leftPointer, rightPointer);
System.out.println(theArray[rightPointer] + " in index "
+ rightPointer + " is smaller than the pivot value "
+ pivot);
printHorzArray(leftPointer, rightPointer);
// When the 2 pointers meet at the middle break
// out of the while loop
if (leftPointer >= rightPointer)
break;
else {
// Swap the values in the pointers
swapValues(leftPointer, rightPointer);
System.out.println(theArray[leftPointer] + " was swapped for "
+ theArray[rightPointer]);
}
}
}
public void swapValues(int indexOne, int indexTwo) {
int temp = theArray[indexOne];
theArray[indexOne] = theArray[indexTwo];
theArray[indexTwo] = temp;
}
Partitioning(int newArraySize) {
arraySize = newArraySize;
theArray = new int[arraySize];
generateRandomArray();
}
public void generateRandomArray() {
for (int i = 0; i < arraySize; i++) {
// Generate a random array with values between
// 10 and 59
theArray[i] = (int) (Math.random() * 50) + 10;
}
}
static void printHorzArray(int i, int j) {
for (int n = 0; n < 61; n++)
System.out.print("-");
System.out.println();
for (int n = 0; n < arraySize; n++) {
System.out.format("| %2s " + " ", n);
}
System.out.println("|");
for (int n = 0; n < 61; n++)
System.out.print("-");
System.out.println();
for (int n = 0; n < arraySize; n++) {
System.out.print(String.format("| %2s " + " ", theArray[n]));
}
System.out.println("|");
for (int n = 0; n < 61; n++)
System.out.print("-");
System.out.println();
if (i != -1) {
// Number of spaces to put before the F
int spacesBeforeFront = 5 * i + 1;
for (int k = 0; k < spacesBeforeFront; k++)
System.out.print(" ");
System.out.print("L");
// Number of spaces to put before the R
int spacesBeforeRear = (5 * j + 1 - 1) - spacesBeforeFront;
for (int l = 0; l < spacesBeforeRear; l++)
System.out.print(" ");
System.out.print("H");
System.out.println("\n");
}
}
}
import java.util.Arrays;
// The Quick Sort is normally the fastest sorting algorithm
public class QuickSort {
private static int[] theArray;
private static int arraySize;
public static void main(String[] args) {
QuickSort theSort = new QuickSort(10);
theSort.generateRandomArray();
System.out.println(Arrays.toString(QuickSort.theArray));
theSort.quickSort(0, 9);
System.out.println(Arrays.toString(QuickSort.theArray));
}
QuickSort(int newArraySize) {
arraySize = newArraySize;
theArray = new int[arraySize];
generateRandomArray();
}
public void quickSort(int left, int right) {
if (right - left <= 0)
return; // Everything is sorted
else {
// It doesn't matter what the pivot is, but it must
// be a value in the array
int pivot = theArray[right];
System.out.println("Value in right " + theArray[right]
+ " is made the pivot");
System.out.println("left = " + left + " right= " + right
+ " pivot= " + pivot + " sent to be partitioned");
int pivotLocation = partitionArray(left, right, pivot);
System.out.println("Value in left " + theArray[left]
+ " is made the pivot");
quickSort(left, pivotLocation - 1); // Sorts the left side
quickSort(pivotLocation + 1, right);
}
}
public int partitionArray(int left, int right, int pivot) {
int leftPointer = left - 1;
int rightPointer = right;
while (true) {
while (theArray[++leftPointer] < pivot)
;
printHorzArray(leftPointer, rightPointer);
System.out.println(theArray[leftPointer] + " in index "
+ leftPointer + " is bigger than the pivot value " + pivot);
while (rightPointer > 0 && theArray[--rightPointer] > pivot)
;
printHorzArray(leftPointer, rightPointer);
System.out.println(theArray[rightPointer] + " in index "
+ rightPointer + " is smaller than the pivot value "
+ pivot);
printHorzArray(leftPointer, rightPointer);
if (leftPointer >= rightPointer) {
System.out.println("left is >= right so start again");
break;
}
else {
swapValues(leftPointer, rightPointer);
System.out.println(theArray[leftPointer] + " was swapped for "
+ theArray[rightPointer]);
}
}
swapValues(leftPointer, right);
return leftPointer;
}
public void swapValues(int indexOne, int indexTwo) {
int temp = theArray[indexOne];
theArray[indexOne] = theArray[indexTwo];
theArray[indexTwo] = temp;
}
public void generateRandomArray() {
for (int i = 0; i < arraySize; i++) {
// Generate a random array with values between
// 10 and 59
theArray[i] = (int) (Math.random() * 50) + 10;
}
}
static void printHorzArray(int i, int j) {
for (int n = 0; n < 61; n++)
System.out.print("-");
System.out.println();
for (int n = 0; n < arraySize; n++) {
System.out.format("| %2s " + " ", n);
}
System.out.println("|");
for (int n = 0; n < 61; n++)
System.out.print("-");
System.out.println();
for (int n = 0; n < arraySize; n++) {
System.out.print(String.format("| %2s " + " ", theArray[n]));
}
System.out.println("|");
for (int n = 0; n < 61; n++)
System.out.print("-");
System.out.println();
if (i != -1) {
// Number of spaces to put before the F
int spacesBeforeFront = 6 * (i + 1) - 5;
for (int k = 0; k < spacesBeforeFront; k++)
System.out.print(" ");
System.out.print("L" + i);
// Number of spaces to put before the R
int spacesBeforeRear = 5 * (j + 1) - spacesBeforeFront;
for (int l = 0; l < spacesBeforeRear; l++)
System.out.print(" ");
System.out.print("R" + j);
System.out.println("\n");
}
}
}
Looking beyond java and more mathematical: