1) Selection Sort
2) Quick Sort
3) Merge Sort
Selection Sort
The algorithm of the selection sort is pretty simple and straightforward compared to other sorting algorithms. The first thing that happens is that it splits the list of elements into two; sorted and unsorted. The sorted goes to the right side and unsorted comes to the left. The goal of each iteration of the algorithm is to place the smallest element in the collection (of the unsorted part) to its correct position. In other words, the algorithm compares the first element in the unsorted part to the remaining elements (in the unsorted part as well) and keeps track of the smallest element found. Once there are no elements to check, the first element is swapped with the smallest element found (if necessary). This same operation is performed n times, where n is the number of elements in the collection. After this operation is performed for every position in the collection, the given collection becomes sorted.
Quick Sort
This sorting algorithm uses a different approach. It first chooses one element from the collection that should be sorted, so called pivot. Different quick sort implementations choose the pivot differently. Some take the first element, some take the last and some choose the pivot randomly. Once the pivot is chosen, it's placed in its correct position in the collection. This is done by putting all the elements smaller than the pivot to the left of the pivot and putting all the elements larger than the pivot to the right of the pivot. After this, the pivot may occur in any position in the collection. It may became the first element (if it's the smallest), the last element (if it's the largest) or may be placed somewhere in between other elements. The key thing is that the algorithms guarantees that the pivot is placed in its final position in the sorted collection. Once the pivot is placed, the same technique is applied (in a recursive way) to the other two (or less) unsorted parts of the collection until the collection is sorted.
Merge Sort
The key point of the merge sort is that this algorithm can easily make a sorted collection given two other sorted collections. It does so by comparing the smallest elements of each collection (if such exist) and placing the smaller one into a new collection until one of the collections becomes empty. Once one of the collections becomes empty, the remaining elements of the other collection are simply placed into the new collection. But this is just part of the merge sort algorithm. When we are given an unsorted collection of items that we want to sort, we don't have a pair of sorted collections to merge. So the other part of the merge sort creates such a condition. Since a collection of a single element is always sorted, the algorithm breaks down the given unsorted list into pieces/smaller collections of a single element. Then it merges them using the algorithm described above until the collection is sorted.
Efficiency
Efficiency is a very important aspect of programming to consider when developing an algorithm to solve a particular problem. An inefficient solution to a problem will do more work (calculations, memorization and so on) than is required. Or in other words such a solution will use more resources than it should, such as memory space and processing time. To conclude the idea of efficiency we can say that whenever we have two algorithms that solve the same problem we always should prefer the one that is more efficient even if it's longer and more complex.
The efficiency of any algorithm can be expressed in terms of the size of the input (usually denoted by n). Even thought we can express the precise growth function of an algorithm, in most cases we are only interested in the dominant term or the Big-O value which provides an accurate estimate for a large input size.
If n is the size of the collection to be sorted, then the following are the efficiencies of the sorting algorithms described above:
Selection sort: O(n2) in any case.
Quick sort: nlog(n) in the best and average case and O(n2) in the worst case.
Merge sort: nlog(n) in any case.
To see a graph on efficiency, check http://csc148h1.blogspot.ca/2014/03/week-9-run-time-analysis.html
So if we had to choose one of the given three sorting algorithms to sort large collections of items, then we should choose the merge sort, because it is the most efficient one in every situation.
So anyways, this is my last blog for this course that I will be writing. Every part of this course was an amazing experience and I hope that you had fun reading my blog. Thank you and good night!