Sorting Algorithms
Before diving into different sorting algorithms. Let’s first get into what sorting is? It means to arrange items/data according to specified criteria.
In computer science, a sorting algorithm is used to arrange elements of a list or an array in order.
The importance of sorting is that data searching can be optimized to a very high level.
Now let’s start with different types of sorting algorithms. We will discuss bubble sort, selection sort, insertion sort, merge sort, and quick sort.
Bubble Sort :
Bubble Sort is the simplest sorting algorithm. It is a comparison-based algorithm in which each pair of adjacent elements is compared and the elements are swapped if they are not in order.
If the given array has to be sorted in ascending order, then bubble sort will start by comparing the first element of the array with the second element, if the first element is greater than the second element, it will swap both the elements, and then move on to compare the second and the third element, and so on.
Pseudocode for bubble sort :
n: the size of the array, arr: an array of elements
for (int i = 0; i < n-1; i++)
{
for (int j = 0; j < n-i-1; j++)
{
if (arr[j] > arr[j+1])
{
int temp = arr[j];
arr[j]= arr[j + 1];
arr[j+ 1] = temp;
} } }
The time complexity of bubble sort is O(N^2).
Selection Sort :
Selection Sort is also a comparison-based algorithm. In this, the list of elements of a given array is divided into two parts, the sorted part at the left end and the unsorted part at the right end. Initially, the sorted part is empty and the unsorted part is the entire list. Then the smallest element is selected from the unsorted array and swapped with the leftmost element and it becomes part of the sorted array. This process continues till our array is sorted.
Pseudo code for selection sort :
n:size of array, arr:array of elements
int i, j, min_idx;
for (i = 0; i < n-1; i++)
{
min_idx = i;
for (j = i+1; j < n; j++)
{
if (arr[j] < arr[min_idx])
min_idx = j;
int temp=arr[min_idx];
arr[min_idx]=arr[i];
arr[i]=temp;
}
}
The time complexity of the selection sort is O(N²).
Insertion Sort :
Insertion sort works similarly as we sort cards in our hand in a card game. It is assumed that the first card is already sorted then, we select an unsorted card. If the unsorted card is greater than the card in hand, it is placed on the right otherwise, to the left. In the same way, other unsorted cards are taken and put in the right place.
Pseudo code for insertion sort :
n:size of array, arr:array of elements
for(int i=1;i<n;i++){
int current=arr[i];
int j=i-1;
while(arr[j]>current && j>=0){
arr[j+1]=arr[j];
j=j-1;
}
arr[j+1]=current;
}
The time complexity of insertion sort is O(N²).
Merge Sort :
It works on the divide and conquer algorithm.
Divide and conquer is a strategy for solving a large problem by:
• Divide the problem into several sub-problems
– Similar sub-problems of smaller size
• Conquer the sub-problems
– Solve the sub-problems recursively
– Sub-problem size small enough solve the problems in a straight forward manner
• Combine the solutions of the sub-problems
– Obtain the solution for the original problem
Merge sort repeatedly breaks down an array into several sub-array until each sub-array consists of a single element
Merge the sub-problem solutions:
• Compare sub-array’s first elements.
• Remove the smallest element and put it into the result array.
• Continue the process until all elements have been put into the result array.
The time complexity of MergeSort is O(n*log n).
Quick Sort :
Like Merge Sort, QuickSort is a Divide and Conquer algorithm. It picks a pivot element from the array and divides the given array around the pivot element.
Given an array of n elements (e.g., integers):
• If the array contains only one element, return
• Else
– pick one element to use as the pivot.
– Partition elements into two sub-arrays:
•Left sub-array contains elements less than or equal to the pivot
•Right sub-array contains elements greater than the pivot
– Then repeatedly apply the above two steps on the two sub-arrays until the array
become sorted
– Return results
The time complexity of Quick Sort is O(n*log n). It also depends on the pivot being selected.
Different ways to select a pivot.
◼ First element
◼ Last element
◼ Median-of-three elements
◆ Pick three elements, and find the median x of these elements. Use that median as the pivot.
◼ Random element
◆ Randomly pick an element as a pivot.
