Sorting algorithms

Sorting algorithms are used to sort a data structure according to a specific order relationship, such as numerical order or lexicographical order.
This operation is one of the most important and widespread in computer science. For a long time, new methods have been developed to make this procedure faster and faster.
There are currently hundreds of different sorting algorithms, each with its own specific characteristics. They are classified according to two metrics: space complexity and time complexity.
Those two kinds of complexity are represented with asymptotic notations, mainly with the symbols O, Θ, Ω, representing respectively the upper bound, the tight bound, and the lower bound of the algorithm's complexity, specifying in brackets an expression in terms of n, the number of the elements of the data structure.
Most of them fall into two categories:
1. Logarithmic The complexity is proportional to the binary logarithm (i.e to the base 2) of n. An example of a logarithmic sorting algorithm is Quick sort, with space and time complexity O(n × log n).
2. Quadratic The complexity is proportional to the square of n. An example of a quadratic sorting algorithm is Bubble sort, with a time complexity of O(n2).
Sorting algorithms can be difficult to understand and it's easy to get confused. We believe visualizing sorting algorithms can be a great way to better understand their functioning while having fun!

Selection Sort

The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.
1) The subarray which is already sorted.
2) Remaining subarray which is unsorted.
In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.
Best, Worst and Average Case Time Complexity: O(n*n).
Visualization

Bubble Sort

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.
Just like the movement of air bubbles in the water that rise up to the surface, each element of the array move to the end in each iteration. Therefore, it is called a bubble sort.
Although it is simple to use, it is primarily used as an educational tool because the performance of bubble sort is poor in the real world. It is not suitable for large data sets.
Worst and Average Case Time Complexity: O(n*n). Best Case Time Complexity: O(n).
Visualization

Insertioin Sort

Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.
Algorithm :
To sort an array of size n in ascending order:
1). Iterate from arr[1] to arr[n] over the array.
2). Compare the current element (key) to its predecessor. If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.
Worst and Average Case Time Complexity: O(n*n). Best Case Time Complexity: O(n).
Visualization

Merge Sort

Merge Sort is a Divide and Conquer algorithm. It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves.
The merge() function is used for merging two halves. The merge(arr, l, m, r) is a key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one.
The MergeSort function repeatedly divides the array into two halves until we reach a stage where we try to perform MergeSort on a subarray of size 1. After that, the merge function comes into play and combines the sorted arrays into larger arrays until the whole array is merged.
Best, Worst and Average Case Time Complexity: O(n log(n))
Visualization

Quick Sort

QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.
The key process in quickSort is partition(). Target of partitions is, given an array and an element x of array as pivot, put x at its correct position in sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x. All this should be done in linear time.
Best and Average Case Time Complexity : O(n logn) and Worst Case Time Complexity : O(n^2).
Visualization