Types of Sorting-IMPORTANT CONCEPTS

1) Bubble Sort
Algorithm: 
1.Traverse the array from i=0 to length-2
2. Inside it traverse the array from j=0 to length-2-i
2.1. If a[j]>a[j+1], swap them

Code:
import java.util.*;
import java.lang.*;
import java.io.*;

class GFG {
public static void main (String[] args) {
Scanner sc = new Scanner (System.in);
int m = sc.nextInt();
for(int mi=0;mi<m;mi++){
   int n = sc.nextInt();
   int a[]= new int [n];
   boolean swapped=false;
   for(int i1=0;i1<n;i1++){
       a[i1]=sc.nextInt();
   }
   for(int i=0;i<n-1;i++){
       for(int j=0;j<n-1-i;j++){
           if(a[j]>a[j+1]){
               int temp=a[j];
               a[j]=a[j+1];
               a[j+1]=temp;
               swapped=true;
           }
       }
  if(swapped==false){break;}     
   }
   for(int j=0;j<n;j++){
       System.out.print(a[j]+" ");
   }
   System.out.println();
}
}

}
Time complexity: O(n*n)

2. Selection sort:

Algorithm:
for i=0 to length-2
 minIndex=i;
  for j = i+1 to length-1
    if(data[j]<data[minIndex])
    minIndex=j;
 swap them

Code:

import java.util.*;
import java.lang.*;
import java.io.*;

class GFG {
public static void main (String[] args) {
Scanner sc = new Scanner (System.in);
int m = sc.nextInt();
for(int mi=0;mi<m;mi++){
   int n = sc.nextInt();
   int a[]= new int [n];
   
   for(int i1=0;i1<n;i1++){
       a[i1]=sc.nextInt();
   }
   for(int i=0;i<n-1;i++){
       int min=i;
       for(int j=i+1;j<n;j++){
           if(a[j]<a[i]){
               min=j;
               int temp=a[j];
               a[j]=a[i];
               a[i]=temp;
               
           }
       }
   
   }
   for(int j=0;j<n;j++){
       System.out.print(a[j]+" ");
   }
   System.out.println();
}
}

}

Time complexity: O(n*n)

3) Selection Sort:

Algorithm:

for i =0 to length-1
 current=a[i]
 j=i-1
 while j>=0 && a[j]>current
  a[j+1]=a[j];
  j=j-1;
a[j+1]=current;

Code: import java.util.*;
import java.lang.*;
import java.io.*;

class GFG {
public static void main (String[] args) {
Scanner sc = new Scanner (System.in);
int m = sc.nextInt();
for(int mi=0;mi<m;mi++){
   int n = sc.nextInt();
   int a[]= new int [n];
   
   for(int i1=0;i1<n;i1++){
       a[i1]=sc.nextInt();
   }
   for(int i=0;i<n;i++){
       int current=a[i];
       int j=i-1;
       while(j>=0 && current<a[j]){
           a[j+1]=a[j];
           j=j-1;
       }
       a[j+1]=current;
   }
   for(int k=0;k<n;k++){System.out.print(a[k]+" ");}
   System.out.println();
}
}
}

Execution Time: O(n*n)

4) Merge Sort

Algorithm: 
MergeSort(A,start,end)
  if start<end
  middle=floor(start+end)/2
  MergeSort(A,start,middle)
  MergeSort(A,middle+1,end)
  Merge(A,start,middle,end)
Merge Algorithm:
Merge(A,start,mid,end)
n1=mid-start+1
n2=end-mid
for i=0 to n1-1
left[i]=a[start+i]
for j=0 to n2-1
right[j]=a[mid+1+j]
i,j=0
for k=start to end
 if left[i]<=right[j]
 a[k]=left[i]
 i++
 else a[k]=right[j]
 j++

CODE:

class MergeSort
{
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
// Find sizes of two subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;

/* Create temp arrays */
int L[] = new int [n1];
int R[] = new int [n2];

/*Copy data to temp arrays*/
for (int i=0; i<n1; ++i)
L[i] = arr[l + i];
for (int j=0; j<n2; ++j)
R[j] = arr[m + 1+ j];


/* Merge the temp arrays */

// Initial indexes of first and second subarrays
int i = 0, j = 0;

// Initial index of merged subarry array
int k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}

/* Copy remaining elements of L[] if any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}

/* Copy remaining elements of R[] if any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}

// Main function that sorts arr[l..r] using
// merge()
void sort(int arr[], int l, int r)
{
if (l < r)
{
// Find the middle point
int m = (l+r)/2;

// Sort first and second halves
sort(arr, l, m);
sort(arr , m+1, r);

// Merge the sorted halves
merge(arr, l, m, r);
}
}

/* A utility function to print array of size n */
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}

// Driver method
public static void main(String args[])
{
int arr[] = {12, 11, 13, 5, 6, 7};

System.out.println("Given Array");
printArray(arr);

MergeSort ob = new MergeSort();
ob.sort(arr, 0, arr.length-1);

System.out.println("\nSorted array");
printArray(arr);
}

}

EXECUTION TIME: O(nlogn) (average case)

5) Quick Sort:

Algorithm:

QuickSort(a, start, end) 
 if start<end
 pivot=Partition(a,start,end)
 QuickSort(a,start,pivot- 1)
 QuickSort(a,pivot+1,end)

Partition Algorithm:

Partiton(a,start,end)
 pivot=a[end]
 i=start
  for j=i to end-1
   if a[j]<=pivot
      exchange a[i] with a[j]
      i++ 
  exchange a[i] with a[end]
return i

Code:

import java.util.*;
public class Solution {
       
static int partition(int[] a,int start,int end) {
        int pivot=a[end];
        int i=start;
       for(int j=start;j<end-1;j++){
           if(a[j]<=pivot){
               int temp=a[i];
               a[i]=a[j];
               a[j]=temp;
               i++;
           }
       }
       int temp1=a[i];
       a[i]=a[end];
       a[end]=temp1;
    return i;
       } 
 static void QuickSort(int [] a,int start, int end){
     if(start<end){
        int  pivot=partition(a,start,end);
         QuickSort(a,start,pivot-1);
         QuickSort(a,pivot+1,end);
          printArray(a)   ;  
     }
    
 }

 static void printArray(int[] ar) {
         for(int n: ar){
            System.out.print(n+" ");
         }
           System.out.println("");
      }
       
      public static void main(String[] args) {
           Scanner in = new Scanner(System.in);
           int n = in.nextInt();
           int[] ar = new int[n];
           for(int i=0;i<n;i++){
              ar[i]=in.nextInt(); 
           }
           QuickSort(ar,0,n-1);
       }    

   }

EXECUTION TIME: O(nlogn)