One of the fundamental problems of computer science is ordering a list of items. There's a plethora of solutions to this problem, known as sorting algorithms. Some sorting algorithms are simple and intuitive, such as the bubble sort. Others, such as the quick sort are extremely complicated, but produce lightening-fast results.
Sorting Algorithms
Bubble sort
Heap sort
Insertion sort
Merge sort
Quick sort
Selection sort
Shell sort
The bubble sort is the oldest and simplest sort in use. Unfortunately, it's also the slowest.
The bubble sort works by comparing each item in the list with the item next to it, and swapping them if required. The algorithm repeats this process until it makes a pass all the way through the list without swapping any items (in other words, all items are in the correct order). This causes larger values to "bubble" to the end of the list while smaller values "sink" towards the beginning of the list.
The bubble sort is generally considered to be the most inefficient sorting algorithm in common usage. Under best-case conditions (the list is already sorted), the bubble sort can approach a constant O(n) level of complexity. General-case is an abysmal O(n2).
Pros: Simplicity and ease of implementation.
Cons: Horribly inefficient.
The merge sort splits the list to be sorted into two equal halves, and places them in separate arrays. Each array is recursively sorted, and then merged back together to form the final sorted list. Like most recursive sorts, the merge sort has an algorithmic complexity of O(n log n).
Elementary implementations of the merge sort make use of three arrays - one for each half of the data set and one to store the sorted list in. The below algorithm merges the arrays in-place, so only two arrays are required. There are non-recursive versions of the merge sort, but they don't yield any significant performance enhancement over the recursive algorithm on most machines.
Pros: Marginally faster than the heap sort for larger sets.
Cons: At least twice the memory requirements of the other sorts; recursive.
- Implement Merge Sort.
- Compare the running time of Bubble Sort and Merge Sort for sorting 100, 1000, 10000, 20000, 40000, 60000, 80000, 100000 integers.
Download the code from here:
g++ -Wall -g bubblesort.cpp -o bubblesort
g++ -Wall -g mergesort.cpp -o mergesort