Skip to content

#2 Sorting Algorithms

Sorting data means arranging it in a certain order, often in an array-like data structure. You can use various ordering criteria, common ones being sorting numbers from least to greatest or vice-versa

Our target by the end of this article is to get an understanding of how various algorithms work and what is the time complexity difference b/w them.

  • Bubble Sort
  • Insertion Sort
  • Selection Sort
  • Merge Sort
  • Heap Sort
  • Quick Sort

Bubble Sort

It works by swapping adjacent elements if they are not in the desired order. This could be done from left to right or right to left.

Time Complexity would be O(n^2)

4 2 1 5 3 //given array sort in ascending order
2 4 1 5 3 //first 2 numbers are compared and swapped
2 1 4 5 3 //number 1 & 4 are compared and swapped
2 1 4 5 3 //number 4 & 5 are compared loop moves
2 1 4 3 5 //number 5 & 3 are compared and swapped
this is the result in one iteration and we would need to do it until no swaps are made.
public static void bubbleSort(int arr[])
{
    int n = arr.length;
    for (int i = 0; i < n-1; i++)
        for (int j = 0; j < n-i-1; j++)
            if (arr[j] > arr[j+1])
            {
                // swap arr[j+1] and arr[j]
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
}

Insertion Sort

Divide the array into the sorted and unsorted subarrays. The sorted part is of length 1 at the beginning and is moved to the first element in the array. During each iteration sorted portion of the array is increased by one element. Upon expanding we place the element into its proper place within the sorted subarray. we do this by shifting all of the elements to the right until we encounter the first element we don’t have to shift.

Time complexity is of O(n^2)

12, 11, 13, 5, 6 //given array lets start the loop from 11 and key be 12
11, 12, 13, 5, 6 //swap as 11 is smaller than 12
11, 12, 13, 5, 6 //now 13 will not change as 13 is larger
5, 11, 12, 13, 6 //now 5 will move to begin and all elements move to the right
5, 6, 11, 12, 13 //now 5 will move to begin and all elements move to the right
public static int[] InsertionSort(int[] arr)
{
    int n = arr.length;
    for(int i=1; i<n; i++)
    {
        int key = arr[i];
        int j = i-1;

        while(j>=0 && arr[j] >key)
        {
            arr[j+1] = arr[j];
            j=j-1;
        }
        arr[j+1] = key;
    }
}

Selection Sort

It divides the array into a sorted and unsorted subarray. Then takes the current element and exchanges it with the smallest element on the right-hand side of the current element

Similar to Insertion Sort Time Complexity is O(n^2).

    public static int[] selectionSort (int[] arr)
    {
        for(int i=0; i< arr.length;i++)
        {
            int minID = i;
            for(int j=i+1; j<arr.length; j++)
            {
                if(arr[j]<arr[minID])
                {
                    minID= j;
                }
            }
            
            int temp = arr[i];
            arr[i] = arr[minID];
            arr[minID] = temp;
        }
    }
Published inData Structures

Be First to Comment

Leave a Reply

Your email address will not be published. Required fields are marked *