Lecture 5

Lecture 5, Tue 04/14

Quadratic-time Sorting

Sorting

Sorting algorithms are useful in order to optimize certain functionality (such as using binary search, checking for duplicates, …)
There are MANY sorting algorithms in existence (even inefficient ones such as Bogosort).

Quadratic-time sorting algorithms

Sorting algorithms in O(n²) are known as quadratic time algorithms.
We’ll cover three quadratic sorting algorithms:
- Bubble sort, Insertion sort, and Selection sort

Bubble Sort

Bubble sort compares adjacent items in the array and swaps them if a[i] > a[i+1].
- This guarantees that the largest (or smallest depending on the direction the bubble is moving the item) will be in the proper place.
  - This needs to be done for each element in the collection.
  - O(n²) complexity.
  - A good illustration of how Bubble sort works is shown here.
Can be slightly optimized
- If a swap doesn’t occur in an iteration, we know the array is already sorted and no more comparisons need to be made.

Visualization of sorting algorithms

A good visualization tool for different sorting algorithms can be found here and here.

Example

//Makefile
CXX=g++

main: main.o sorts.o
	${CXX} -o main -std=c++11 main.o sorts.o

clean:
	rm -f *.o main

//sorts.h
void bubbleSort(int a[], size_t size);

//sorts.cpp
#include <iostream>

using namespace std;

void bubbleSort(int a[], size_t size) {
	int temp;
	bool swapped;

	for (int i = size - 1; i > 0; i--) {
		swapped = false;
		for (int j = 0; j < i; j++) {
			if (a[j] > a[j + 1]) {
				// swap
				temp = a[j];
				a[j] = a[j+1];
				a[j+1] = temp;
				swapped = true;
			}
		}
		if (!swapped) {
			// in order
			cout << "i = " << i << endl;
			cout << "already in order... returning" << endl;
			return;
		}
	}
}

//main.cpp
#include <iostream>
#include "sorts.h"

using namespace std;

void printArray(const int a[], size_t size) {
	for (int i = 0; i < size; i++) {
		cout << "[" << i << "] = " << a[i] << endl;
	}
}

int main() {
	int a[] = {1,2,3,4,5,6,7,8,9,10};
	int b[] = {1,10,2,9,3,8,4,7,5,6};
	int c[] = {2,9,4,7,6,5,8,3,10,1};
	int d[] = {10,9,8,7,6,5,4,3,2,1};
	int e[] = {1};

	bubbleSort(a, 10);
	printArray(a,10);
	cout << "---" << endl;
	bubbleSort(b, 10);
	printArray(b,10);
	cout << "---" << endl;
	bubbleSort(c,10);
	printArray(c,10);
	cout << "---" << endl;
	bubbleSort(d,10);
	printArray(d,10);
	cout << "---" << endl;
	bubbleSort(e,1);
	printArray(e,1);
}

Selection Sort

From top-down (or bottom-up), look through the array and find the largest (or smallest) element.
Swap a[i] with a[index_of_largest_value]
O(n²) complexity.
A good illustration of how Selection Sort works is shown here.

// Add to sorts.h

void selectionSort(int a[], size_t size);

// Add to sorts.cpp
void selectionSort(int a[], size_t size) {
	int temp;
	int largestIndex;
	int largest;
	for (int i = size - 1; i > 0; i--) {
		largestIndex = 0;
		largest = a[0];
		for (int j = 1; j <= i; j++) {
			if (a[j] > largest) {
				largest = a[j];
				largestIndex = j;
			}
		}
		temp = a[i];
		a[i] = a[largestIndex];
		a[largestIndex] = temp;
	}
}

Insertion Sort

Similar to sorting cards in a poker hand
For each item in the array, find where it should “belong” and insert the item in its proper place.
- Before insertion happens, shift all elements in order to to make an empty slot where the item should belong.
- Do this for each element, and by the end of the algorithm, all elements will be in their proper place.
- O(n²) complexity.
- O(n) complexity for elements that are mostly-sorted.

Example

// Add to sorts.h

void insertionSort(int a[], size_t size);

// Add to sorts.cpp

void insertionSort(int a[], size_t size) {

	int item;
	int shiftIndex;
	for (int i = 1; i < size; i++) {
		item = a[i];
		shiftIndex = i - 1;

		while (shiftIndex >= 0 && a[shiftIndex] > item) {
			a[shiftIndex + 1] = a[shiftIndex];
			shiftIndex -= 1;
		}
		a[shiftIndex + 1] = item;
	}	
}