Sorting Algorithms

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

Selection sort is an algorithm that is based on scanning an array from left to right.
It means:

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 O(n2).

Insertion Sort

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: O(n2)

Shellsort

The 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. This interval is calculated by the formula that was introduced by Shell:

d = f l o o r ( g a p / 2 )
where the gap — is an interval with the initial value N (count of elements).

The main steps of this algorithm are:

a) Initialize the value of d
b) Divide the list into smaller sublists using an interval h
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 d.
In the worst case: O(n2).
In the best case: O(n∗log(n)).

Mergesort

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 O(n∗log(n)).

Quicksort

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 partition operation.
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.

The quicksort’s 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: O(n2)
In the best case: O(n∗log(n))

Summary

For small data sets, it is better to use the selection sort or insertion sort algorithms.
For other cases, it is better to prefer O(n∗log(n))algorithms.

Bonus: here is a great data structures and algorithms tutorial.