Skip to main content

 

Related topic: Visualizing sorting algorithms.

But, How do we actually implement Sorting Algorithms – Using Visual representation.

Jan 18, 2022 – Babina Banjara


Sorting algorithms take lists of items as input data, perform specific operations on those lists and deliver ordered arrays as output.

Sorting algorithms can be difficult to understand and it’s easy to get confused. I believe visualizing sorting algorithms can be a great way to better understand their functioning while having fun.

Why is Sorting even needed?

Efficient sorting is important for canonicalizing data and for producing human-readable output. Furthermore, it is important for optimizing the efficiency of other algorithms that require input data to be in sorted lists.

 It is easier and faster to locate items in a sorted list than unsorted. Sorting algorithms can be used in a program to sort an array for later searching or writing out to an ordered file or report. When working with research data, sorting is a common method used for visualizing data in a form that makes it easier to comprehend the story the data is telling.

Let’s take a look at a few of the sorting algorithms.

Bubble Sort

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

In real practice, 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, and swaps them if they are in the wrong order.

Let us look at the complexity of bubble sort.


The major drawback of this sorting technique is that it requires a lot of time because of its worst case as O(n2). So, it can be used for only a small set of data and only when we require a handful of swaps.

Bubble Sort is a simple algorithm to implement but not much effective in real-world scenarios.

Insertion Sort

Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. 

The algorithm divides the data structure into two sublists: a sorted one, and (n-1) set of elements 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. 

Let us look at the complexity of insertion sort.


The average complexity being O(n2), the performance is directly proportional to the square of the input taken. In simple, the time taken for execution will take square times the input size.

It is really easy to implement and it’s efficient only on small data structures which are almost sorted. 

Selection Sort

Selection Sort is an iterative and in-place sorting algorithm that divides the data structure into two sublists: the ordered one, and the unordered one.

The selection sort algorithm sorts an array by repeatedly finding the minimum element from the unordered part and putting it at the beginning. In every iteration of selection sort, the minimum element from the unordered subarray is picked and moved to the ordered sublist. 

Let us look at the complexity of selection sort.


The main advantage of the selection sort is that it performs well on a small list. Furthermore, no additional temporary storage is required beyond what is needed to hold the original list.

It retains the first k smallest element in its first k iterations.  So, you don’t need to sort all the data to obtain the first kth sorted data.

Merge Sort

Merge Sort is a sorting algorithm based on the Divide and Conquer technique. Basically, it divided the data into different groups, sorts data into groups, and merges them to get complete sorted data. 

The first stage is where the list is split until it forms individual elements called sub-lists. After this, the ‘merge’ stage begins. Here the sub-lists are paired up and are arranged according to the order stated. These paired lists are paired again to form groups and are again arranged according to the intended order. This process happens until the sub-lists form one list. 

Let us look at the complexity of merge sort.


The complexity O(nxlogn) denotes the logarithmic time which makes this sorting technique faster than the other. But, because of space complexity of O(n), it requires more space.

It works perfectly well for a large set of data because of its low time complexity. But, it requires at least twice the memory than other sorts. 

Heap Sort

Heap Sort is an in-place iterative sorting algorithm based on auxiliary data structures called heap.

Heap sort can be thought of as an improved selection sort. Alike selection sort, heapsort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element from it and inserting it into the sorted region.

Heap sort works by transforming the list of items to be sorted into a heap data structure that is – a binary tree with heap properties. In a binary tree, every node has at most, two descendants. A node possesses the heap property when none of its descendants have greater values than itself. The largest element of the heap is removed and inserted into the sorted list. The remaining sub-tree is transformed into a heap again. This process is repeated until no elements remain. 

Let us look at the complexity of heap sort.


While other sorting algorithms may grow exponentially slower as the number of items to sort increases, the time required to perform Heap sort increases logarithmically. This suggests that Heap sort is particularly suitable for sorting a huge set of data.

The Heap sort algorithm is widely used because of its efficiency. 

Quick Sort

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

This division in partitions is done based on one element, called a pivot. All the elements bigger than the pivot get placed on the right side of the structure, and the smaller ones to the left.  This occurs recursively to the two partitions and so on.

This partition technique based on the pivot is called Divide and Conquer.

Let us look at the complexity of quick sort.


It has an efficient average case compared to any other sort algorithm. But, it is not a stable sort. That means the order of equal elements may not be preserved.

Quicksort is one of the most efficient sorting algorithms, and this makes it one of the most used as well. 

Now, let us see how arrays in the visualizer are generated?

Arrays of random size are generated with each click. It creates a div element using Math.random() function and appends each div with a certain margin to get a block of arrays.

This is the function to generate the array.

function generate_array()
{
    cont.innerHTML="";

    for(var i=0;i<array_size;i++)
    {
        div_sizes[i]=Math.floor(Math.random() * 0.5*(inp_as.max - inp_as.min) ) + 10;
        divs[i]=document.createElement("div");
        cont.appendChild(divs[i]);
        margin_size=0.1;
        divs[i].style=" margin:0% " + margin_size + "%; background-color:#658E9C; width:" + (100/array_size-(2*margin_size)) + "%; height:" + (div_sizes[i]) + "%;";
    }
}

Visualization of the algorithms.

The visualizer basically plays with colors to better understand what is happening in the algorithm. The data here is the bars that are generated randomly with arbitrary heights. 

When the algorithm runs, these bars or segments change to three different colors – yellow, red, and green, each holding its own function.

The yellow segment represents that the algorithm is looking at that particular segment. If it is changing a certain segment it will mark it as red. If the final position of the segment is where it is now that is in a sorted position, it will mark it as green.

Once the algorithm is running, it disables all the buttons so that sorting can be performed uninterruptedly. Color and height are changed accordingly while the algorithm is working. 


You can get much clear insights after visualizing on your own.

Visit the start of the blog to implement yourself.

Make sure you change the size and speed of the algorithm in the slider for better visualization. You can generate a new array by clicking the button.

Factors to be considered while choosing an efficient sorting algorithm.

Know what sorting algorithm is aligned with your problem space.


Thanks to the evolution of new technologies and huge amounts of data constantly being generated, the demand for faster and more efficient sorting algorithms always exists. If you look up sorting algorithms, you will be amazed by the sheer amounts of algorithms used. But it is equally important to figure out which algorithm works best for your data.

To choose the appropriate algorithm for different data, you need to know some properties of your input data.  The main factors to consider when choosing a sorting algorithm aligned with your needs are: 

Size of data:  How much data are you expecting to sort? This will help you know whether you need to look for an algorithm with very low time complexity. For a small set of data, bubble, insertion, and selection sort works best. While working for a large set of data, consider using merge, heap and quick sort.

Randomness of data: How sorted will your data be already? Will it be partly sorted? Randomly sorted? This can affect the time complexity of the sorting algorithm. Most algorithms will have worst and best cases – you want to make sure you’re not using an algorithm on a worst-case data set.

Time and space Complexity: Any algorithm design is often a trade-off between time and space, algorithms with a low space complexity may require more time, and algorithms with a low time complexity may require more space. Time complexity describes how the performance of an algorithm varies as the size of the data set increases in terms of time. Space complexity describes how much space an algorithm needs to run.

Stability: It is to retain the relative order of equal elements, which are present in my input data. If relative order is important for you, you can look for a stable algorithm.

“Sorting something that you will never search is a complete waste; searching something you never sorted is merely inefficient.”

                                                                                                                                                                                         –  Brian Christian