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:

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).

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).

Space and time complexity can also be further subdivided into 3 different cases: best case, average case and worst case.

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!

The bigger bubbles reach the top faster than smaller bubbles, and this algorithm works in the same way. It iterates through the data structure and for each cycle compares the current element with the next one, swapping them if they are in the wrong order.

It's a simple algorithm to implement, but not much efficient: on average, quadratic sorting algorithms with the same time complexity such as Selection Sort or Insertion Sort perform better.

BUBBLE SORT

Bubble Sort is an iterative sorting algorithm that imitates the movement of bubbles in sparkling water. The bubbles represents the elements of the data structure.

The bigger bubbles reach the top faster than smaller bubbles, and this algorithm works in the same way. It iterates through the data structure and for each cycle compares the current element with the next one, swapping them if they are in the wrong order.

It's a simple algorithm to implement, but not much efficient: on average, quadratic sorting algorithms with the same time complexity such as Selection Sort or Insertion Sort perform better.

COMPLEXITY

Average Complexity 0(n2)

Best Complexity O(n2)

Worst Complexity 0(n2)

Space Complexity O(1)

SELECTION SORT

Selection Sort is an iterative and in-place sorting algorithm that divides the data structure in two sublists: the ordered one, and the unordered one. The algorithm loops for all the elements of the data structure and for every cycle picks the smallest element of the unordered sublist and adds it to the sorted sublist, progressively filling it.

It's a really simple and intuitive algorithm that does not require additional memory, but it's not really efficient on big data structures due to its quadratic time complexity.

COMPLEXITY

Average Complexity 0(n2)

Best Complexity O(n2)

Worst Complexity 0(n2)

Space Complexity O(1)

QUICK SORT

Quick Sort is a sorting algorithm based on splitting the data structure in smaller partitions and sort them recursively until the data structure is sorted.

This division in partitions is done based on an element, called pivot: all the elements bigger than the pivot get placed on the right side of the structure, the smaller ones to the left, creating two partitions. Next, this procedure gets applied recursively to the two partitions and so on.

COMPLEXITY

Average Complexity 0(n x log n)

Best Complexity O(n x log n)

Worst Complexity 0(n2)

Space Complexity O(n)

INSERTION SORT

Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. It's less performant than advanced sorting algorithms, but it can still have some advantages: it's really easy to implement and it's efficient on small data structures almost sorted.

The algorithm divides the data structure in two sublists: a sorted one, and one still to sort. Initially, the sorted sublist is made up of just one element and it gets progressively filled. For every iteration, the algorithm picks an element on the unsorted sublist and inserts it at the right place in the sorted sublist. It's available in several variants such as Gnome Sort.

COMPLEXITY

Average Complexity 0(n2)

Best Complexity O(n)

Worst Complexity 0(n2)

Space Complexity O(1)