Hi! As I mentioned earlier, I decided to recall some fundamental knowledge.
In this article, I'd like to share with you the difference between sorting algorithms. I know, that it can be very simple, but how many times do you think about it? We all use it very often (for example, the
sort method in ruby), but not everyone takes a look under the hood.
So, here I want to describe the most popular sorting algorithms (again 🙂).
Selection sort is an algorithm that is based on scanning an array from left to right.
a) None entries situated on the right part of the sorted data are smaller than any entries from the left part
b) The left-side entries of the sorted data part are in ascending order
So, we start from the first element of the data with the index
i and go through the data from left to right. If we find the smaller element, we need to change it with an element with an index
i. In the next iteration, we move the pointer (index
i) to the right by 1 and repeat searching smaller elements from the right part of the data.
The time complexity of the algorithm is
Insertion sort is another simple sorting algorithm.
The main steps are:
a) Split the data into 2 parts: sorted and unsorted
b) Start from the first element of the data with the index
i and put it into the sorted part
c) Increment the index
i by 1, and select the next element
d) Find a new index for the selected element. Go through the sorted part of the data from right to left unless a smaller element is found
e) Insert the selected element into the sorted part of the data using a new index
f) Go to
c until the data is sorted
The time complexity of this algorithm is the same as for the selection sort:
shellsort algorithm is an improved version of the insertion sort.
This method is based on sorting pairs of elements that are situated far apart from each other.
Shellsort splits data into some parts using an
interval is calculated by the formula that was introduced by Shell:
d = f l o o r ( g a p / 2 )
gap — is an
interval with the initial value
N (count of elements).
The main steps of this algorithm are:
a) Initialize the value of
b) Divide the list into smaller sublists using an interval
c) Sort these sublists using the insertion sort algorithm
d) Repeat until the complete list is sorted
The time complexity of the algorithm depends on the interval
In the worst case:
In the best case:
Mergesort is one of the
divide-and-conquer algorithms which is built on top of recursion.
Conceptually, the merge sort works as follows:
a) Divide the unsorted list into
n sublists, each containing 1 element (a list of 1 element is considered as a sorted one).
b) Repeatedly merge sublists to produce new sorted sublists until there is only 1 remaining sublist. This will be the sorted list.
The time complexity of the algorithm in the worst case is
The quick sort algorithm is a highly efficient algorithm that is also recursion-based.
The steps of the algorithm are:
a) Pick an element (
pivot) from the initial array.
b) Partitioning: reorder the array so all elements with values less than the
pivot will be placed before the
pivot, while all the elements with values greater than the
pivot will be placed after it (equal values can go either way).
After this partitioning, the
pivot is in its final position. This is called the
c) Recursively apply the above steps to the sub-array of elements with smaller values and to the sub-array of elements with greater values.
divide-and-conquer technique makes this algorithm a great parallel execution candidate.
The time complexity of the algorithm depends on
pivot element and can be:
In the worst case:
In the best case:
|Algorithm||Complexity (the worst case)||Complexity (the best case)|
For small data sets, it is better to use the
selection sort or
insertion sort algorithms.
For other cases, it is better to prefer
Bonus: here is a great data structures and algorithms tutorial.