Learn to Sort Algorithms

Learn to Sort Algorithms
Learn to Sort Algorithms

Concerning computer science, a sorting algorithm is used to arrange a given set of elements in a specific order. The most popularly used orders are numerical order like ascending and descending order or lexicographical order in case of strings and characters.

Sorting algorithms are widely used for the optimisation of other algorithms like searching and merging that require a sorted set of elements. Sorting reduces the worst-case complexity of a searching algorithm from O(n) to O(log n). It is also used for canonicalising data,i.e., changing it to an approved format and generating serial human and machine-readable outputs.

Following are some real-life examples of sorting:

  • Attendance Register: The list of the students is sorted in the ascending order of their roll number.
  • Dictionary: The dictionary stores words in lexicographical order, so that you may quickly find the required information.
  • Telephone Directory: To optimise search in a telephone directory, the names are sorted in the alphabetical order.
  • Rank Lists: While creating rank lists, the marks of the students are required to sort in descending order.

The output of any sorting algorithm should follow these requirements:

  • It should always be a permutation of the given input. Sorting algorithms are not allowed to remove any element from the given set or add any element; they can only re-arrange the input elements to form a sequential list.
  • It should follow a uniform pattern throughout. A sorting algorithm, if it is being to arrange elements in ascending order, should arrange all the elements; no exceptions are acceptable. However, in some cases, equalities are considered.

In-place sorting V/S Not-in-place sorting

Some sorting algorithms need additional memory for ad-hoc storage of elements or comparison. At the same time, some do not require any additional space and make the changes in the given array itself. The first method is known as not-in-place sorting, while the latter is known as in-place sorting. A popular example of in-place sorting is Bubble sort, while Merge-sort is an example of not-in-place sorting.

NOTE: All the algorithms are discussed with respect to arranging the elements in ascending order (smallest to greatest).

The most popular sorting algorithms are discussed below:

Bubble Sort

  • It is the easiest sorting algorithm.
  • In bubble sort, we compare each pair of adjacent elements and swap them if the prior element is greater than the latter. It is also addressed as the “sinking sort.”
  • After the first pass, the largest number is in its correct place; after the second pass, the second-largest element is in its correct position, and so on.
  • It is an in-place sorting algorithm.

Due to its high average-case time complexity and worst-case time complexity, it is not used for larger values of n. (where n is the number of elements in the input array).

Image Source: facePrep

// The implementation of Bubble Sort
void bubble_sort(int input[ ], int size) //Given an array of integers and its size
{
int i;
//To pick the first element of the list
for (i = 0; i < n-1; i++)
{

// Comparing it with the adjacent elements
for (int j = 0; j < size-i-1; j++) { if (input[j] > input[j+1])
{
swap(input[j],input[j+1]); // swap if the latter element is smaller
}
}
}
}

  • For the function given above:
  • Worst Case Time Complexity: O(n*n), Worst case is encountered when the given input array was sorted in descending order.
  • Average Case Time Complexity: O(n*n).
  • Best Case Time Complexity: O(n), the Best case is encountered when the given input array was already sorted in ascending order.
  • Auxiliary Space: O(1), for swapping the elements.

Selection Sort

  • In this algorithm, we find the minimum element of the array and place it in its correct place. After two or three iterations, the array gets divided into two halves, the sorted first half and the unsorted half consisting of the remaining elements.
  • In every subsequent iteration, we find the smallest element from the unsorted half and place it in its correct position, and increase the boundary by one.
  • After the first pass, the smallest number is in its correct place; after the second pass, the second element is in its proper position, and so on (Vice-versa of bubble sort).
  • It is also an in-place sorting algorithm.

Due to its high average-case time complexity and worst-case time complexity, it is not used for larger values of n. (where n is the number of elements in the input array).

Image Source: facePrep

// The implementation of Selection Sort
void selection_sort(int input[ ], int size) //Given an array of integers and its size
{
int i, j, min_idx;

// Increment the boundary of the unsorted array after each iteration
for (i = 0; i < size-1; i++)
{
// To find the position of the smallest element in the array
min_idx = i;
for (j = i+1; j < size; j++)
if (input[j] < input[min_idx])
min_idx = j;

          // switch the smallest element and the first element of the array

               swap(input[min_idx],input[i]);

}
}

For the function given above:

  • Worst Case Time Complexity: O(n*n), Worst case is encountered when the given input array was sorted in descending order.
  • Average Case Time Complexity: θ(n^2).
  • Best Case Time Complexity: Ω(n^2), the Best case is encountered when the given input array was already sorted in ascending order.
  • Auxiliary Space: O(1), for swapping the elements.

Insertion Sort

  • Insertion sort is an elementary sorting algorithm; analogous to sorting a pack of trump cards by your hands. The given array is hypothetically divided into a sorted and an unsorted part.
  • With each iteration, we bring elements from the unsorted section to the sorted section.
  • It is based on an incremental approach.
  • It is also an in-place sorting algorithm like the bubble sort and selection sort.
  • The current element is referred to as the key element in the insertion sort.
    Insertion is widely used if the number of elements is less in the input array.
    It ignores the pre-sorted values, hence works very efficiently for a nearly sorted array.
  • For arrays with a larger number of elements, insertion sort is only used if a few elements are out of the place.
Image Source: facePrep

//implementation of insertion sort
void insertion_sort(int input[], int size)
{
int i, key_element, j;
for (i = 1; i < size; i++)
{
key = arr[i]; //assign the key element
j = i – 1;

//Shift all the elements that are greater than the key by one position to make room for the swapped element

        while (j >= 0 && input[j] > key_element)  
        { 
             input[j + 1] = input[j]; 
             j = j - 1; 
        } 
   input[j + 1] = key_element;        //update the key element
} 

}

For the function given above:

  • Worst Case Time Complexity: O(n*n), Worst case is encountered when the given input array is sorted in descending order.
  • Average Case Time Complexity: O(n*n).
  • Best Case Time Complexity: O(n), the Best case is encountered when the given input array was already sorted in ascending order.
  • Auxiliary Space: O(1), for swapping the elements.

Quick Sort

  • It follows the Divide and Conquers algorithm strategy(the given problem is divided into a number of sub-problems, and their result is combined).
  • It is also an in-place sorting algorithm.
  • It selects one of the input elements as the “pivot” and splits the array across it.
    The pivot can be the first element of the input array, the last element of the input array, the median of the input array, or any random element from the input array; it depends on the version of the quicksort that you are using.
  • Quicksort uses a supplementary function called “partition” that places the “pivot” element in its correct position.
  • It sorts the entire array in linear time, contributing to its high demand.
Image Source: facePrep

//Implementation of Quick Sort
//low is the starting index and high is the ending index of the input array

void quick_sort(input[], low, high)
{
if (low < high)
{
//find the partitioning index using the partition function
partioning_index = partition(input, low, high);

   //recursive call for the elements before the partitioning index
   quick_sort(input, low, partioning_index - 1); 

   //recursive call for the elements after the partitioning index
  quick_sort(input, partioning_index + 1, high);     
}

}

For the function given above:

  • Worst Case Time Complexity: O(n log n)
  • Average Case Time Complexity: O(n log n)
  • Best Case Time Complexity: O(n*n)
  • Auxiliary Space: O(n)

Merge Sort

  • Analogous to the QuickSort, it also follows the Divide and Conquer strategy.
  • It is a not in-place sorting algorithm.
  • At each call of the function, we divide the array into two halves, and call the recursive function again, till there is only one element in the final sub-array.
  • It uses the supplementary function “merge” for combining the output from the two halves of the array at every division.
  • The array obtained after the merge operation is the desired sorted array.
Image Source: facePrep

//Implementation of Merge Sort
//low is the starting index and high is the ending index of the input array

void merge_sort(int input[], int low, int high)
{
if (low < high)
{

    int mid = (high + low) / 2;     //find the middle element

   //call the recursive function for the first half
    merge_sort(input, low, mid);    

   //call the recursive function for the second half
   merge_sort(input, mid + 1, high);     

     //call the merge function for combining the results
     merge(input, low, mid, high); 
 } 

}

For the function given above:

  • Worst Case Time Complexity: O(n log n)
  • Average Case Time Complexity: O(n log n)
  • Best Case Time Complexity: O(n log n)
  • Auxiliary Space: O(n)

The table given below summarises the time complexity and the space of the above mentioned algorithms:

Image Source: After Academy

To read more articles, click here.

By Vanshika Singolia