L21.5 (makeup class) - Quicksort

#ece244

recursion example 2: sum of an array

Given an array of $n$ integers, find the sum of the elements of the array through recursion.

• recursive step: return first element of array + sumArr(array_with_one_less_item)
• base case: if array size is $1$, then return the value in the array.

Implementation:

#include <iostream>
using namespace std;
int sumArr(int arr[], int sizeArr) {
	int* newArr = new int[sizeArr - 1];
	for (int i = 1; i < sizeArr; i++) {
		newArr[i-1] = arr[i];
	}
	int total_sum;
	if (sizeArr > 1) {
		total_sum = arr[0] + sumArr(newArr, sizeArr - 1);
	} else {
		total_sum = arr[0];
	}
	
	delete [] newArr;
	return total_sum;
}

int main(void) {
	int* new_array = new int[4];
	new_array[0] = 1;
	new_array[1] = 2;
	new_array[2] = 3;
	new_array[3] = 4;
	cout << "sum of the array is " << sumArr(new_array, 4) << endl;
	return 0;
}

recursion example 2: lecture implementation

which is much more efficient than what I wrote; instead of creating a whole new array each time, just feed in the same array, along with left, which is basically the index that you're working at.

• recursive step: return value of the array at left index + sumArr(left + 1, arr, right)
• base case: if left == right then return arr[left]

#include <iostream>
using namespace std;

int sumArr(int left, int arr[], int right) {
	if (left == right) {
		return arr[left];
	} else {
		return arr[left] + sumArr(left + 1, arr, right);
	}
}

int main(void) {
	int* new_array = new int[4];
	new_array[0] = 1;
	new_array[1] = 2;
	new_array[2] = 3;
	new_array[3] = 4;
	cout << "sum of the array is " << sumArr(0, new_array, 3) << endl;
	return 0;
}

quicksort

Quicksort is a highly efficient sorting algorithm. it works by using the "divide and conquer" ideology

divide and conquer strategy

1. divide the problem into smaller, independent sub-problems
2. conquer (solve) each problem
3. combine solutions of sub-problems to get the final solution

Quicksort does this by:

1. divide:
   • choose one element from array to be a "pivot"
   • rearrange array so all elements smaller than pivot are on the left, and all elements larger are on the right
   • after this, pivot is in the correct, final sorted position
2. conquer
   • on either side of the pivot, we have two smaller, unsorted arrays
   • we call quicksort to recursively sort the smaller arrays
     • i.e., we choose an element from left array, move all elements smaller than it to LHS, and all elements larger to RHS
3. Combine
   • we don't have to do anything here because after all of this is done we have already sorted the array

quicksort general example

• We let $pivot=10$.
• Place a pointer at the right most index, and a pointer at the left most
• We then perform the following operation:
  • Move R leftwards until we reach a value that is less than pivot
    • In this case, we don't need to move it because 4 < 10
  • Move L rightwards until we reach a value that is greater than pivot
    • In this case, we don't need to move it because 14 > 10
  • Then, swap the values at R and L

Notes:

• the pivot always has its correct, sorted index
• we can now do this recursively on the two partitions we've just created

quicksort: partition()

First we make a function that:

• works on an array from index left and index right
• chooses a pivot and makes all numbers before it < pivot and all numbers after it > pivot (what we did in the example above)
• function returns final index of pivot

Implementation:

int partition(int a[], int low, int high) {
	bool done = false;
	int pivotIndex = low, left = low + 1, right = high;
	while (!done) {
		while (left <= high && left <= right && a[pivotIndex] >= a[left]) {
			left++;
			// add 1 to left until we reach a point where the value at left is
			// either no longer smaller than the pivot, left crosses right end of
			// array, or left and right cross
		}
		while (right >= low && left <= right && a[pivotIndex] <= a[right]) {
			right--;
			// minus 1 from right until we reach a point where the value at right is
			// either no longer larger than pivot, the index right reaches left end of
			// array, or left and right cross
		}
		if (left <= right) {
			// if the pointers haven't crossed yet, swap them
			// since they are already moved to the swapping position
			swap(a[left], a[right]);
		} else {
			// if pointers HAVE crossed then move the pivot to the rightmost pointer
			swap(a[right], a[pivotIndex]);
			done = true;
		}
	}
	return right;
}

Notes:

• We swap the pivot index with the right index because, after the pointers have crossed, the right pointer will be to the left of the left pointer
• this gives us the following situation (same with even and odd sized arrays):
  • R | L
  • where R < pivot, and L > pivot, so logically you want to move the pivot pointer to be in between
  • but that would require shifting the entire LHS 1 index down, which is unnecessarily complex and time consuming
  • the next best thing is to just swap R and pivot, since the partition on LHS will remain all < pivot, and the partition on RHS will remain all > pivot
• swap() is a function that we define ourselves. See: swap()

quicksort: swap()

This is just a simple function that the swaps the values at given indices.

Implementation:

void swap(int &left, int &right) {
	int temp = a;
	a = b;
	b = a;
}

quicksort: quicksort() and quickSortHelper()

This is the recursive function that

void quickSort(int list[], int length) {
	quickSortHelper(list, 0, length - 1);
}
void quickSortHelper(int list[], int low, int high) {
	// recursive step
	// we only do work if sub-array has 2 or more elements
	if (low < high) {
		// partition list; pivotIndex is correct final index of pivot value
		int pivotIndex = partition(list, low, high);
		quickSortHelper(list, low, pivotIndex - 1); // sorts the left sub array
		quickSortHelper(list, pivotIndex + 1, high); // sorts the right sub array
	}
	
}