Sorting Algorithms - Quick Guide

What is Sorting Algorithm?

It is used to arrange items of an array in specific order. For example -

5 , 4 , 3 , 2 , 1 => After Sorting=> 1 , 2 , 3 , 4 ,5

There are various sorting algorithms -

• Bubble Sort
• Selection Sort
• Insertion Sort
• Cyclic Sort
• Merge Sort
• Quicksort
• Counting Sort
• Radix Sort
• Bucket Sort
• Heap Sort
• Shell Sort

Bubble Sort

It is the simplest algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order .

How Bubble Sort Works -

This algorithm starts with first two elements, compare & check which one is greater . Example - array = [ 3 , 1 , 5 , 4 , 2 ]

First Pass : In First Pass, largest element comes at last index!

• 3 , 1 , 5 , 4 , 2 // first two elements are 3 & 1 . Swap since 3>1
• 1 , 3 , 5 , 4 , 2 // swap since 5>4
• 1 , 3 , 4 , 5 , 2 //swap since 5>2
• 1 , 3 , 4 , 2 , 5 //largest element in the end & all the items in the array <5 . Through the first pass, the largest element in the entire array (here 5) came to the end

Second Pass : In Second Pass, second largest element comes at second from last index!

• 1 , 3 , 4 , 2 , 5 // swap since 4>2
• 1 , 3 , 2 , 4 , 5 // the right side elements of 4 is already sorted! so we don't need to compare again & again. the second largest element at second from last index (here 4 is the second largest element)

Third Pass :

• 1 , 3 , 2 , 4 , 5 // swap since 3>2
• 1 , 3 , 2 , 4 , 5 //sorted!!

Complexity -

Space Complexity : => O(1) => since here no extra space is required !

Time Complexity :

Best Case :

• => O(N)

• => When the array is sorted !

Worst Case :

• => O(N^2)

• => When we are sorting descending order array to ascending order.

• => Total No of Swaps = Total No of Comparisons

Advantages Of Bubble Sort :

It is a ..

• Stable
• Simple
• In-place Sorting Algorithm.

Java Program For Bubble Sort

package sorting;

import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr={5,4,3,2,1};
        sort(arr);
        System.out.println("The Sorted Array "+ Arrays.toString(arr));
    }
    static void sort(int[] arr){
        boolean isSwapped;
        int n= arr.length;
        for(int i=0;i<n;i++){
          isSwapped=false;
          for (int j=1;j<n-i;j++){

              if (arr[j]<arr[j-1]){
                  //swap 
                  swap(arr,j,j-1);
                  isSwapped=true;
              }
          }
          //if you did not swap for a particular value ,it means the array is sorted
          if(!isSwapped){
              break;
          }
        }
    }
    static void swap(int[]arr,int first , int sec){
        int temp   = arr[first];
        arr[first] = arr[sec];
        arr[sec]   = temp;
    }

}

Thank You For Reading This Article ! Please Like and Share If You Liked it & I will upload the part 2 soon..!!