Thread: Sorting Algorithms

Hello, today I will try to give a quick overview of sorting algorithms that we can use.

Note: To keep it simple I will use lists that are made of integers (for sorting).

Introduction

First I will show you how to implement Selection sort and Insertion sort algorithms, they both are O(n^2) algorithms and should be used only for small lists (lets say less than 6-10 numbers).
Then we will get on with better ways to sort big integer lists by using Merge Sort, Heap Sort and Quick Sort. All of them have an average case performance of O(nlogn).
At the end we will discuss algorithms that can sort lists in O(n) time, such as Bucket Sort, Counting Sort and Radix sort.

If you see any spelling errors or want to add information that might be usefull, please send me a PM and I will try to fix it. I know I am not the best at explaining things, so I would appreciate if people would help me out here!

Practical Example

To give you a simple example lets say we have two computers (A and B).
Computer A can execute 10^9 instructions per second.
Computer B can execute 10^7 instructions per second.
So computer A is 100 times faster than computer B in raw computing power.
Both computers must sort an array of one million numbers.
Computer A (faster one) will run Insertion Sort.
Computer B (slower one) will run Merge Sort.
To make the difference even more dramatic, suppose that the world's craftiest programmer codes insertion sort in machine language for computer A, and the resulting code requires 2n^2 instructions to sort n numbers (So the constant c = 2).
While Merge Sort is programmed by an average programmer using a high-level language with an inefficient compiler, with the resulting code taking 50n logn instructions (So the constant c = 50).

To sort one million numbers computer A takes: 2 * (10^6)^2 / 10^9 = 2000 seconds.
while computer B takes 50 * 10^6 log(10^6) / 10^7 ≈ 100 seconds.

If we try to sort 10 million numbers, the difference between two will increase even more
insertion sort will take 2.3 days, while merge sort will do it under 20 minutes.

So as you can see, even tho we had a more powerfull computer, and constants were very different, we could not beat O(nlogn) algorithm with an O(n^2) algorithm on big arrays. Also I hope that you understood why Insertion sort algorithm is better for sorting small lists, than merge sort. (because constant of insertion will always be smaller than merge sort's if we program on same computer with same programming language)

Selection sort: Selection sort - Wikipedia, the free encyclopedia

public class SelecionSort {
	/**
	 * Sorts the given list in place.
	 * Worst Case Performance O(n^2)
	 * Best Case Performance O(n^2)
	 * Average Case Performance O(n^2)
	 * Insertion sort can be- and usually is a much faster sorting algorithm, than selection sort.
	 * Selection sort is superior because it does less swaps.
	 * @param list - int array that you want to sort.
	 */
	public static void sortNumbers(Integer[] list){
		//go through the list
		for (int i=0; i<list.length;i++){
			//define min
			int min = i;
			//go through the remaining list and see if there is smaller number
			for (int j=i+1;j<list.length;j++){
				//if there is a smaller number
				if (list[j] < list[min]){
					//remember its place
					min = j;
				}
			}
			if (i != min){
				//swap the min element, moving it to its proper place in the list.
				int temp = list[min];
				list[min] = list[i];
				list[i] = temp;
			}
		}
	}
	/**
	 * Just for testing purposes.
	 */
	public static void main(String[] args){
		Integer[] list = new Integer[5];
		list[0] = 32;
		list[1] = 24;
		list[2] = 235;
		list[3] = 1;
		list[4] = 0;
		sortNumbers(list);
 
		for (int i = 0;i<list.length;i++){
			System.out.println(list[i]);
		}
	}
 
}

Insertion Sort: Insertion sort - Wikipedia, the free encyclopedia

public class InsertionSort {
 
	/**
	 * Sorts the given list in place.
	 * Worst Case Performance O(n^2)
	 * Best Case Performance O(n)
	 * Average Case Performance O(n^2)
	 * @param list - int array that you want to sort.
	 */
	public static void sortNumbers(int[] list){
		//go through the list of the numbers, starting with number two (we say that number one is already sorted)
		for (int i=1; i<list.length -1; i++){
			//store the value of the number we are dealing with (because it's place can be taken by other bigger numbers)
			int value = list[i];
			//define j (its a pointer to the already sorted list, starting at the largest number - back of the sorted list)
			int j = i-1;
			//as long as value is lower than the number in sorted list and we are still in the list
			while (j >= 0 && list[j] > value){
				// we are going to move the higher number(from the sorted list) one step to the right (so it will make space for the current value number - witch is lower)
				list[j+1] = list[j];
				//and we move our pointer in the list to next place - lower number
				j--;
			}
			//once we come to the right spot, we insert our value number in there and start with next i value.
			list[j+1] = value;
		}
	}
 
}

Those two algorithms (Selection and Insertion) are good for sorting small lists, but when lists start to become big you better use faster algorithms such as following:

Merge Sort: Merge sort - Wikipedia, the free encyclopedia

public class MergeSort {
 
	/**
	 * Merges two arrays into one.
	 * @param A array that contains the two arrays.
	 * @param temp temporary array that we will work with
	 * @param lo lowest index value in the array
	 * @param mid middle index value in the array (represents break between low and high values)
	 * @param hi highest index value in the array
	 */
	private static void Merge(int[] A, int[] temp, int lo, int mid, int hi){
		int i = lo;
		int j = mid;
 
		for (int k = lo; k < hi; k++){
			if (i == mid) temp[k] = A[j++]; //if lo-mid array is empty
			else if (j == hi) temp[k] = A[i++]; //if mid-hi array is empty
			else if (A[j] > A[i]) temp[k] = A[i++]; //i is lower so we put it in the array first
			else temp[k] = A[j++]; //j is lower or equal to i, so we put it in the array first.
		}
 
		//now we need to copy back temp array to its place in A array
		for (int k = lo; k < hi; k++)
			A[k] = temp[k]; //we are copying only the numbers we just merged.
 
	}
 
	private static void MergeSort(int[] A, int lo, int hi){
		if (hi - lo == 1) return; //only one element in the array, return.
		int mid = lo + (hi - lo) / 2; //find middle
		MergeSort(A, lo, mid); //sort first part
		MergeSort(A, mid, hi); //sort second part
		Merge(A, new int[A.length], lo, mid, hi); //merge both parts
	}
 
	/**
	 * Sorts the given list. (Not in place)
	 * Worst Case Performance O(nlogn)
	 * Best Case Performance O(nlogn)
	 * Average Case Performance O(nlogn)
	 * @param A list of int array.
	 */
	public static void sortNumbers(int[] A){
		MergeSort(A, 0, A.length);
	}
 
	/**
	 * Just for testing purposes.
	 */
	public static void main(String[] args){
		int[] list = {156,344,54,546,767,23,34,64,234,654,234,65,234,65,87,3,5,76,24,2,3,7,9,5,34,32,4525,345,0};
		sortNumbers(list);
 
		for (int i = 0;i<list.length;i++){
			System.out.println(list[i]);
		}
	}
 
}

Heap Sort: Heapsort - Wikipedia, the free encyclopedia

public class HeapSort {
 
	private static int heapSize; //this will help us to stop sorting list numbers that are already sorted.
 
 
	/**
	 * Sorts the given list in place.
	 * Worst Case Performance O(nlogn)
	 * Best Case Performance O(nlogn)
	 * Average Case Performance O(nlogn)
	 * @param A - list that needs to be sorted.
	 */
	public void sortNumbers(int[] A){
		HeapSort(A);
	}
 
	/**
	 * Read sortNumbers method description.
	 * @param A - list that needs to be sorted.
	 */
	private void HeapSort(int[] A){
		heapSize = A.length; //we need to sort all the list so heapSize == A.length
		BuildMaxHeap(A); //first we build max heap
 
		//now we have the biggest element in the heap on the top
		//we will exchange it with the last element in the list
		//reduce heapSize so this (biggest) element wont be sorted anymore
		//and we will call MaxHeapify once again to get new biggest element on the top
		//and once again we place it at the current end of the list, we do it all the way
		//til we will have only one element left in the heap (which will be the lowest number)
		//this way our array will get sorted, from smallest (at the start of the list) to biggest (at the end of the list).
 
		for (int i = A.length-1; i>0; i--){
 
			//exchange biggest number with the current last one
			int temp = A[0];
			A[0] = A[i];
			A[i] = temp;
			//reduce the heap size
			heapSize--;
			//find new biggest
			MaxHeapify(A,0);
		}
	}
 
	/**
	 * Builds MaxHeap (runs in linear time so: O(n) )
	 * if n = amount of numbers in the list, then n/2 = amount of leaves (nodes that have no children)
	 * We need to call MaxHeapify from bottom and up, but we can skip all leaves so we start at index = n/2 and go up.
	 * @param A - list that we will build MaxHeap of.
	 */
	private void BuildMaxHeap(int[] A){
		for(int i = A.length/2-1;i>=0;i--){
			MaxHeapify(A, i);
		}
	}
 
	/**
	 * Takes O(logn) or we can also say that if subtree with root at index i has height of h
	 * then running time of algorithm is O(h)  (note that a binary tree with n elements has height = logn)
	 * Sorts the array at the given index so that subtree meets heap requirements.
	 * @param A array list
	 * @param i index of the root of subtree that might be smaller than its children.
	 */
	private void MaxHeapify(int[] A, int i){
		int l = Left(i); //lets find left child of the given index.
		int r = Right(i);//lets find right child of the given index.
		int max;
		if (l < heapSize){ //lets check if left child is an existing child
 
			//if it is an existing child
			if (A[l] > A[i]){ //if left child is bigger than parent
				max = l; //left child becomes maximum
			}
			else {
				max = i; //otherwise parent is maximum
			}
		}
		else { //if this index does not have left child
			max = i;
		}
 
		if (r < heapSize){ //lets check if the right child is an existing child
 
			//if it is existing child
			if(A[r] > A[max]){ //if right child is bigger than our current maximum
				max = r; //right child becomes our new maximum
			}
		}
 
		if (max != i){ //if our parent is not maximum
			//we need to swap max with parent
			int temp = A[i];
			A[i] = A[max];
			A[max] = temp;
 
			//at the end we need to run MinHeapify on the child that was just swapped 
			//and see if it is supposed to go even further down the list
			MaxHeapify(A, max);
		}
	}
 
	/**
	 * Returns Left child index of the given parent index.
	 * @param i - parent index.
	 * @return - index of parents left child.
	 */
	private int Left(int i){
		return 2 * i;
	}
 
	/**
	 * Returns Right child index of the given parent index.
	 * @param i - parent index.
	 * @return - index of parents right child.
	 */
	private int Right(int i){
		return (2 * i) + 1;
	}
 
	/**
	 * Just for testing purposes.
	 */
	public static void main(String[] args){
		int[] list = {156,344,54,546,767,23,34,64,234,654,234,65,234,65,87,3,5,76,24,2,3,7,9,5,34,32,4525,345,0};
		HeapSort hs = new HeapSort();
		hs.sortNumbers(list);
 
		for (int i = 0;i<list.length;i++){
			System.out.println(list[i]);
		}
	}
 
}

Quick Sort: Quicksort - Wikipedia, the free encyclopedia

public class QuickSort {
 
	/**
	 * Sorts the given list in place.
	 * Worst Case Performance O(n^2)
	 * Best Case Performance O(nlogn)
	 * Average Case Performance O(nlogn)
	 * @param list - int array that you want to sort.
	 */
	public void sortNumbers(int[] list){
		Quicksort(list, 0,list.length-1);
	}
 
	public void Quicksort(int[] A, int start, int end){
		if (start < end){
			//we partition the list and get back two lists (lower than pivot, and bigger than pivot)
			int middle = Partition(A, start, end);
			//we then do a recursive call to sort out lower numbers than pivot
			Quicksort(A, start, middle-1);
			//and we do same with higher numbers than pivot
			Quicksort(A, middle+1, end);
			//NOTE: pivot is already in it's place, where he supposed to be (in a sorted list).
		}
	}
 
	public int Partition (int[] A, int start, int end){
		int pivot = A[end]; //we define pivot (the number we will be comparing other numbers to
		int lo = start-1; // we define low value index
 
		for (int hi = start; hi < end; hi++){ //we go throug the list, compare other numbers to pivot
			if (A[hi] <= pivot){ //if pivot is lower that the current number
				lo++; //we increase lo value
				//and exchange current lo with hi (so we will have all lower numbers than pivot on one side
				int temp = A[lo];
				A[lo] = A[hi];
				A[hi] = temp;
			}
		}
		//at the end we put in pivot right inbetween low and high values and we know that pivot element is in the right place.
		int temp = A[lo+1];
		A[lo+1] = A[end];
		A[end] = temp;
 
		return lo+1; //we return the pivot elements place
	}
 
	public static void main(String[] args){
		int[] list = {156,344,54,546,767,23,34,64,234,654,234,65,234,65,87,3,5,76,24,2,3,7,9,5,34,32,4525,345,0};
		QuickSort qs = new QuickSort();
		qs.sortNumbers(list);
 
		for (int i = 0;i<list.length;i++){
			System.out.println(list[i]);
		}
	}
 
}

Later on I will add algorithms that can sort lists in linear time. Yes, even faster algorithms, but they have quite big requirements on input and might not be so memory efficient.

Hope this will help someone.
-Dal.