Sorting in Data Structure: Categories & Types

Data Sorting
Data Sorting

Sorting is an arrangement of data in a particular fashion/order. But if we talk about sorting in Data Structure then it’s more relevant to rearrange the data/element in ascending/descending order which can be lexicographical, numerical, or maybe user-defined. For example, Consider you have five siblings and you want to arrange them according to height.

Now if you wish to arrange them in increasing or decreasing order of height and then algorithm, you’ll perform to do this task is sorting. But more interestingly in How much time, you can do it? Suppose if you do it in five sec and when your brother is given a chance and he does it in three sec then his idea
would be best among both of you. That’s the complexity of your algorithm.

In other words, you can say that sorting is also used to represent data in a more readable format. Some real-life examples of sorting are:-

  • Contact List in Your Mobile Phone also contains all contacts arranged alphabetically (lexicographically). So if you look for contact then you don’t have to look randomly and can be searched easily and many others like Apps on your phone.
  • Keywords in Your book are also in a lexicographical manner and you can find it according to Chapter.

Why Study Sorting?

  1. When you perform sorting on an array/elements, many problems become easy (e.g. min/max, kth smallest/largest).
  2. Performing Sorting also gives no. of algorithmic solutions that contain many other ideas such as:
  • Iterative
  • Divide-and-conquer
  • Comparison vs non-comparison based
  • Recursive

The main advantage of sorting is time complexity and that’s the most important thing when you solve a problem because it’s not enough you’re able to solve a problem but you should be able to solve it in the minimum time possible. Sometimes problems can be solved easily and quickly based on sorting which can prevent you from every Coder’s Nightmare i.e. TLE (Time Limit Exceeded).

Types of Sorting algorithms:

Although there is no. of sorting algorithms best algorithm is which can solve a problem in minimum time and minimum space required to do so. Some types of the Sorting algorithm are:

  • Bubble Sort: It’s one of the simplest algorithms which repeatedly iterates through the list, compares the elements next to each other and swaps according to the condition passed to them. Confusing isn’t it? It would be right to say this Sorting as an idea or approach to solving a problem what we people usually do (Brute force Solution).

Suppose, You are given an array, arr [8] = {2, 4, 1, 6, 5, 3, 7, 8} and you have to sort it in increasing order then Steps followed would be as:

  • Here two loops would be required in sorting, the first loop for iterating and the second loop for comparing.
  • As first you’ll check if the previous element is greater than the next element then swap it otherwise increase the counter.
    First Pass:
    { 2 4 1 6 5 3 7 8 }  { 2 4 1 6 5 3 7 8 } , Since these elements
    are already sorted (2 < 2) , no swapping required
    { 2 4 1 6 5 3 7 8 }  { 2 1 4 6 5 3 7 8 }, Here compares the
    elements and found (4 > 1), so swaps them.
    { 2 1 4 6 5 3 7 8 }  { 2 1 4 6 5 3 7 8 }, No swapping (4 < 6)
    { 2 1 4 6 5 3 7 8 }  { 2 1 4 5 6 3 7 8 }, Swapping (6 > 5)
    { 2 1 4 5 6 3 7 8 }  { 2 1 4 5 3 6 7 8 }, Swapping (6 > 3)
    { 2 1 4 5 3 6 7 8 }  { 2 1 4 5 3 6 7 8 }, No swapping (6 < 7)
    { 2 1 4 5 3 6 7 8 }  { 2 1 4 5 3 6 7 8 }, No swapping (7 < 8)

Second Pass:
{ 2 1 4 5 3 6 7 8 }  { 1 2 4 5 3 6 7 8 }, Swapping (2 > 1)
{ 1 2 4 5 3 6 7 8 }  { 1 2 4 5 3 6 7 8 }, No swapping (2 < 4)
{ 1 2 4 5 3 6 7 8 }  { 1 2 4 5 3 6 7 8 }, No swapping (4 < 5)
{ 1 2 4 5 3 6 7 8 }  { 1 2 4 3 5 6 7 8 }, Swapping (5 > 3)
{ 1 2 4 3 5 6 7 8 }  {1 2 4 3 5 6 7 8 }, No swapping ( 5 < 6)
{ 1 2 4 3 5 6 7 8 }  { 1 2 4 3 5 6 7 8 }, No swapping (6 < 7)
{ 1 2 4 3 5 6 7 8 }  { 1 2 4 3 5 6 7 8 }, No swapping (7 < 8)

And So on n-1 passes i.e. seven passes it will check further. The one thing that makes this algorithm time consuming is even though the array is sorted in the second pass but it will continue going to check up to n-1 passes.

Not much clear Right? Alright, we’ll take a look at how this algorithm works which will give us a clear idea about this algorithm.

Insertion Sort: It is an algorithm that works the way we sort our money. Funny isn’t it? Consider you have some Rs.1, Rs.2, Rs.5 coins and some Rs.10, Rs.50, Rs.100, Rs.200, Rs.500 notes and they are already in sorted order(increasing) of their amount. If I give u another Rs.100 note and ask you to insert the note in the right position so that money in your hand should be sorted. How will you do it?

Well, you’ll have to go through each coin or note to check from starting for finding the right position of the new note. Once you find the right position, you’ll insert it. Let’s consider an array, arr[ ]={5, 1, 6, 2, 4, 3} So what will we do in this we will start from index 1 to n-1 and compare that element with all elements from beginning and will put it in its right place.

Selection Sort: Selection sort works by repeatedly finding the smallest element from the array and then putting it in the beginning and then again finding the smallest from the rest of the array other than the previous one and arranging it in beginning. So basically we can say that it has two subarrays in it one is Sorted and the other is unsorted. Let’s consider an array, arr[ ]= { 23, 78, 45, 8, 32, 56}

Merge Sort: It is one of the best sorting algorithms because of its time complexity. It is based on the divide-and-conquer paradigm. The basic concept of the merge sort divides the array into two smaller sub-array of approximately equal size and recursively repeats the procedure until one element is left in the sub-array. After this, various sorted sub-arrays are merged to form a sorted final array. As it is based on recursion so basically we have to deal with the base case and induction hypothesis rest recursion will do everything for us.

Let’s take an array consisting elements : 38, 16, 27, 39, 12, 27.

Quick Sort: It is based on partition. It is also known as partition exchange sorting. The basic concept of this algorithm is to pick one element from an array and rearranges the rest of elements around it and that element is known as pivot element and that element divides the main array into two sub-arrays. Once the pivot is fixed then it moves all the elements lesser than it to left and elements greater than it to right. This procedure is repeated recursively until there is one element left in the sub-array.

Let’s consider an array consisting of elements : 27, 38, 12, 39, 27, 16. Here 27 is chosen as pivot element and an array is divided into two sub-arrays consisting of all elements less than pivot to the left sub-array and greater than pivot to the right sub-array.

Although there is no. of sorting algorithms mostly used are discussed above and others are also important which is used in advanced Data Structure such as:

  • Heap Sort
  • Counting Sort
  • Bucket Sort
  • Radix Sort
  • Shell Sort
  • Comb Sort
  • Cycle Sort
  • Bitonic Sort
  • Tree Sort
  • Stooge Sort
  • Pancake Sorting

One thing that comes to our mind is why to study Sorting when we have already inbuilt sorting function in Python/C++/Java. But you should know that

  • Python and Java sorting function is based on TimSort(hybrid algorithm of mergeSort and insertion Sort).
  • C++ sort function(STL) is based on IntroSort (hybrid algorithm of quick Sort and heap Sort) and many more.
  • Overall these above-explained sorting algorithms are basics to understand any further advanced Sorting algorithms.

Some Coding Problems on Sorting:

  • Sort elements by frequency
  • Find an array is a subset of another array
  • Inversion Count
  • Overlapping intervals problem
  • Chocolate Distribution
  • Minimum number of swaps to make two arrays identical
  • Find missing elements of a range
  • Minimum difference between any two elements
  • Find pair with the greatest product in an array
  • Find all triplets with zero-sum

For more problems, you can also login to our practice platform and enhance your data structure and algorithm skills on CodeZen.

By Yogesh Kumar