[BlakeJustBlake]

Table of Contents

• Introduction
  
• Bubble sort
  
• Selection Sort
  
• Insertion Sort
  
• Merge Sort
  
• Quick Sort
  
• Conclusion

Introduction

I was just formally taught all of the sorting algorithms in a Computer Science class, so to better understand them I decided to go in depth with all of the sorting algorithms to further my understanding and provide a good reference for all of the popular, and a few of the more obscure, sorting algorithms.

To fully understand these explanations you should understand basic C++ Syntax, pointers and Recursion.

To help in describing each sorting algorithm I've included the average efficiency (using big-O notation), the number of operations used, and whether it is in place or not. Explaining these characteristics is out of the scope of this tutorial and will be left to Wikipedia.

Bubble Sort

Average Case Efficiency: O(n^2)
In Place Sorting? Yes
Stable? Yes
Best Case: All cases are the same.
Worst Case: All cases are the same.

Introduction

Bubble sort is the simplest, most intuitive sorting algorithm. If you asked someone with no knowledge of sorting algorithms to sort an array, they would probably make up some version of Bubble Sort. Though it's simple to implement, it is the least efficient, and should only be used when you need to quickly write out a function to sort small amounts of data.

Description

Bubble Sort works by iterating through a list for every element in it, for every iteration you compare every element to the element next to it, if the element next to it is smaller (or larger depending on how you're sorting) then you swap them. Every iteration you decrease the number of elements you compare because one will be in the right order.

Here's a visual representation:

Quote

Our list L = {9, 7, 6, 2, 1}. n = |L| = 5. We'll be sorting low->high.

1st iteration
9 > 7? 6 2 1 -> 7 9 6 2 1
7 9 > 6? 2 1 -> 7 6 9 2 1
7 6 9 > 2? 1 -> 7 6 2 9 1
7 6 2 9 > 1? -> 7 6 2 1 9

In the first iteration 9 is "floated like a bubble" all the way to the end. During the next iteration, since 9 is the largest number and already in place it doesn't need to be compared, so the number of comparisons to be made is reduced by 1.

2nd iteration
7 > 6? 2 1 9 -> 6 7 2 1 9
6 7 > 2? 1 9 -> 6 2 7 1 9
6 2 7 > 1? 9 -> 6 2 1 7 9

As you can see, 7 has also floated to the end with 9, and the smaller numbers are slowly floating to the beginning of the list. The number of comparisons can be reduced again.

3rd iteration
6 > 2? 1 7 9 -> 2 6 1 7 9
2 6 > 1? 7 9 -> 2 1 6 7 9

etc.
4th iteration
2 > 1? 6 7 9 -> 1 2 6 7 9

and so we get the final sorted list:

1 2 6 7 9

Implementation

Here is one way to implement Bubble Sort in C++:

//We assume sorting integers, but it could be anything.
void BubbleSort(int array[], int size) {
       int tmp; //a temporary int is needed for swapping
       /*Iterates by the size of the list minus 1 because it doesn't need to sort
        *the last time because it will only have one value to compare. It decrements
        *so that the every time a smaller list will be compared, effectively leaving out
        *whatever value was put into place by the last iteration.
        */
       for(int i = size - 1;i>=0;i--) {
            /*For every element in the list that hasn't been finalized..*/
            for(int j = 1;j<=i;j++) {
                 /*Check if the element before it is larger, then swap if so*/
                 if(array[j-1]>array[j]) {
                     tmp = array[j-1];
                     array[j-1]=array[j];
                     array[j]=tmp;
                 }
            }
       }
}

Selection Sort


Average Case Efficiency: O(n^2)
In Place Sorting? Yes
Stable? No
Best Case: All cases are the same.
Worst Case: All cases are the same.

Introduction

Selection Sort is another fairly inefficient sorting algorithm along the same order as Bubble Sort, but is generally faster than it. However, it is not so much faster that it warrants using over Bubble Sort when it comes to simple sorting algorithms. Discussion of its use, like some of the more obscure sorting algorithms, is pretty much purely scholarly.

Description

Where Selection Sort lacks in usefulness, it makes up in being a little clever. In simplest terms, it works by first finding the smallest (or largest depending on how you're sorting) element in the list and swapping that with the first element in the list. Then it finds the second smallest element and swaps with the second element in the list. Thus it will have a similar loop structure to Bubble Sort, but different operations.

Here is a sample run through:

Quote

Our list L = {9, 7, 6, 2, 1}. n = |L| = 5. We'll be sorting low->high.

1st iteration:
lowest = 9
9 7 6 2 1
lowest > 7? -> lowest = 7
9 7 6 2 1
lowest > 6? -> lowest = 6
9 7 6 2 1
lowest > 2? -> lowest = 2
9 7 6 2 1
lowest > 1? -> lowest = 1
swap: 1 7 6 2 9

As you can see from the first iteration, the amount of operations needed is pretty similar to Bubble sort.

2nd Iteration:
lowest = 7
1 7 6 2 9
lowest > 6? -> lowest = 6
1 7 6 2 9
lowest > 2? -> lowest = 2
1 7 6 2 9
lowest > 9?
swap: 1 2 6 7 9

3rd Iteration:
lowest = 6
1 2 6 7 9
lowest > 7?
1 2 6 7 9
lowest > 9?
swap: 1 2 6 7 9

4th iteration:
lowest = 7
1 2 6 7 9
lowest > 9?
swap: 1 2 6 7 9

final result: 1 2 6 7 9

Something you'll probably notice is that even though the list was sorted in two iterations, the algorithm doesn't have a check for these sort of things.

Implementation

void SelectionSort(int array[], int size) {
	int tmp, min; //a temporary int is needed for swapping, and a min int is needed to store the current minimum, min defaults to 0
       /*Iterates by the size of the list minus 1 because it doesn't need to sort
        *the last time because it will only have one value to compare. It decrements
        *so that the every time a smaller list will be compared, effectively leaving out
        *whatever value was put into place by the last iteration.
        */
	for(int i = 0;i<=size;i++) {
		min = i;
		for(int j = i+1;j<=size-1;j++) {
			//if the currently held minimum is greater than the currently iterated element then set the index of min to the current index
			if(array[min]>array[j]) {
				min = j;
			}
		}
			tmp = array[i];
			array[i] = array[min];
			array[min] = tmp;
	}
}

Insertion Sort

Average Case Efficiency: O(n^2)
In Place Sorting? Yes
Stable? Yes
Best Case: Already sorted list. (A good case is a nearly sorted list.)
Worst Case: List sorted in reverse order.

Introduction

Though Insertion Sort has the same average efficiency as both Bubble Sort and Selection Sort, it is generally faster than both while still remaining relatively simple. It works with the same amount of memory space, still has two loops, but it has the possibility of exiting the second loop early and also requires less memory writes than Bubble Sort and Selection Sort. When you need to quickly write out a sort for small amounts of data, Insertion Sort is definitely the best choice.

Description

All of Insertion Sort's operations are on the array that's passed to the function, but it acts as if it is operating on two different lists. What Insertion Sort does is start off assuming that the first item in the list is a part of an already sorted list, then the next item in the list is inserted into that already sorted list in its proper position, if it goes at the end of the list then it is just added to the end moves on, but if it needs to be inserted at any other position then that element is stored in a temporary space and everything is moved over and the element inserted into its properly allocated space. The comparison steps are no different from Bubble Sort, going through one by one comparing every value, but the insertion step makes it so that the algorithm has a chance of not having to loop over every element in the list on every single iteration.

So let's look at a visual representation of Insertion Sort in action:
As usual L = {9, 4, 7, 8, 1}. n = |L| = 5. We'll be sorting low->high. (note that I changed the set we've been using since it was in reverse order before and that would be Insertion Sort's worst case, not really giving a good show of how Insertion Sort works)

Quote

1st Iteration:
9 4 7 8 1
9 > 4? true, end of list, insert at beginning
9 9 7 8 1
4 9 7 8 1

2nd iteration:
4 9 7 8 1
9 > 7? true, next
4 9 9 8 1
4 > 7? false, insert after 4
4 7 9 8 1

3rd iteration:
4 7 9 8 1
9 > 8? true, next
4 7 9 9 1
7 > 8? false, insert after 7
4 7 8 9 1

4th iteration:
4 7 8 9 1
9 > 1? true, next
4 7 8 9 9
8 > 1? true, next

4 7 8 8 9
7 > 1? true, next
4 7 7 8 9
4 > 1? true, end of list, insert at beginning
4 4 7 8 9

final result: 1 4 7 8 9

Implementation

void InsertionSort(int array[], int size) {
	int tmp; //a temporary int is needed for holding the value that's being check against
	/*Starting at the second element in the list, iterate through the list*/
	for(int i = 1;i<size;i++) {
		//Hold the value for later
		tmp = array[i];
		//Set the index value that will decrement through the already sorted list
		int j = i - 1;
		/*While the end of the already sorted list hasn't been reached, and the element
		 *to be inserted is still less than other elements in the already sorted list, move
		 *those elements over.
		 */
		while(j>=0&&tmp<array[j]) {
			array[j+1]=array[j];
			j--;
		}
		//Insert the element in its correct place.
		array[j+1]=tmp;
	}
}

Merge Sort

Average Case Efficiency: O(n*logn)
In Place Sorting? No
Stable? Yes
Best Case: All cases are roughly the same.
Worst Case: All cases are roughly the same.

Introduction


Merge sort is the first of the faster and more complex sorting algorithms to be discussed. It runs on the same order as the other fast sorting algorithms and is much more stable, but has drawbacks in memory usage. Since Merge Sort doesn't sort in place, it has to allocate memory for another list of the same size as the input list. Merge sort uses recursion to simplify sorting down to a minimum number of comparisons, to then be merged together with other comparisons. In this way, Merge Sort is a divide and conquer algorithm.

Description

Merge Sort is a simple sort to explain, simply: It divides the inputted list into two halves, sorts those halves, then merges them together. More difficultly: It divides the inputted list into two halves, then halves those halves, and continues doing this until it gets to a base case and starts working its way back up merging base cases together, sorting as it goes until the list is whole again. Merging works efficiently because it assumes that both of the lists that it will merge together are going to be sorted already, so the first items in both lists will be the lowest items, and so it only needs to compare first values until there are no more values in one of the lists, then it just has to add the remaining items to the end of the merged sorted list. In the beginning it creates an empty list of the same size as the inputted list where it will write to. It is usually visualized like this:

Lets say you have our trusty set L = {9, 4, 7, 8, 1}. n = |L| = 5 then it would sort like this:

		 9 4 7 8 1
		   /	\
		9 4	7 8 1		Split the initial list into two parts, odd number handling shouldn't be too hard
	   /   \	/   \
	  9	4  7	8 1	  Continue to split until you only reach one item, this item is sorted
	   \   /   |	/   \
		4 9   7  8	 1	Start to merge sorted single items together into sorted double items
		  |	 |   \   /
		4 9   7	1 8	  ...
		  |	 \	/
		4 9	 1 7 8	   Continue merging
		   \	 /
		  1 4 7 8 9		 Merge all together

Implementation

void MergeSort(int array[], int size) {
	//Declare an auxilary list to sort items in before transferring them back to the original list.
	int aux_array[size];
	m_sort(array, aux_array, 0, size-1);
}

void m_sort(int toSort[], int sortInto[], int left, int right) {
	int mid;
	//If there is more than one element
	if(right>left) {
		//Calculate the middle
		mid= (right + left) / 2;
		//Divide and sort left half
		m_sort(toSort, sortInto, left, mid);
		//Divide and sort right half
		m_sort(toSort, sortInto, mid+1, right);
		//Merge left and right halves
		merge(toSort, sortInto, left, mid+1, right);
	}
}

void merge(int toMerge[], int mergeInto[], int left, int mid, int right) {
	//You need to take note of where the left side ends, the size of the list being merged, and a temporary index
	int left_end = mid-1;
	int num_of_elements = (right-left) + 1;
	int tmp = left;
	
	//While there are still numbers to merge in the left and right side
	while(left <= left_end && mid <= right) {
		/*If the first unmerged number on the left side is less than the first unmerged number on the right side,
		 *then add it to the merged sorted list.
		 */
		if(toMerge[left] <= toMerge[mid]) {
			mergeInto[tmp] = toMerge[left];
			left++;
		}
		//else add the first unmerged number on the right side to the merged sorted list
		else {
			mergeInto[tmp] = toMerge[mid];
			mid++;
		}
		//Move up in position on the merged sorted list
		tmp++;
	}
	
	//While there are any numbers remaining on the left side, add them to the merged sorted list
	while(left<=left_end) {
		mergeInto[tmp]=toMerge[left];
		left++;
		tmp++;
	}
	//Same with the right side
	while(mid<=right) {
		mergeInto[tmp]=toMerge[mid];
		mid++;
		tmp++;
	}
	//Move everything from the auxilary list to the actual list.
	for (int i = 0;i<num_of_elements;i++) {
		toMerge[right] = mergeInto[right];
		right--;
	}
}

Quick Sort

Average Case Efficiency: O(n*logn)
Worst Case Efficiency!: O(n^2)
In Place Sorting? Depends on Implementation
Stable? No
Best Case: Most lists.
Worst Case: Already sorted. When the pivot is the unique minimum or maximum in the list.

Introduction

Even if you know just a little about sorting algorithms, then chances are you know Quick Sort. And of course an algorithm can't just call itself Quick Sort without having some merit to it. Quick Sort is one of the faster sort algorithms, and it would be almost perfect if it weren't for its downfall of running O(n^2) time in its worst case. That may sound like a reason to use merge sort instead, but unlike Merge Sort, Quick Sort doesn't use a lot of memory. Also, Quick Sort's worst case doesn't come up too often, especially with proper watch over it. QuickSort is the best for most sets of data.

Description

You can think of Quick Sort as a modification of Bubble Sort. The way it works is by picking a pivot point in a way determined by the algorithm writer, for our purposes the pivot point will always be in the middle of the list, then it looks at every item in the list and moves it to a certain place depending on whether it's less than, greater than, or equal to the pivot point.

Implementation

void quickSort(int a[], int aSize) {
	q_sort(a, 0, aSize-1);
}

void q_sort(int a[], int left, int right) {
	//Generate a random seed and select the pivot at random.
	srand(time(0));
	int pivotIndex = left+(int)((right-left)*rand()/(RAND_MAX + 1.0));
	int pivot = a[pivotIndex];
	//remember starting values of left and right
	int leftHold = left;
	int rightHold = right;
	//iterate through every element of the array
	while(left<right) {
		//if the numbers on the right are larger than the pivot, they're in the right place
		while((a[right]>=pivot)&&(left<right)) {
			--right;
		}
		//If not then move them over
		if (left != right) {
			a[left]=a[right];
			++left;
		}
		//If the numbers on the left are smaller than the pivot, they're in the right place
		while((a[left]<=pivot)&&(left<right)) {
			++left;
		}
		//if not then move them over
		if (left!=right) {
			a[right]=a[left];
			--right;
		}
	}
	//Sort the lefts and rights.
	a[left]=pivot;
	if(leftHold<left) 
		q_sort(a, leftHold, left-1);
	if(rightHold>right)
		q_sort(a, left+1, rightHold);
}

Conclusion

These are the only sorting methods to be discussed here, and are the ones you'll usually hear spoken of. But look for an accompanying article coming soon about alternative sorts. There are some other good sorts that aren't really talked about for one reason or another, but are very worthy of mentioning. If you find any errors or discrepancies in my code or what I've said here then please notify me so it can be fixed right away.