Various Sorting Algorithm in Java

Bubble Sort in Java

We can create a java program to sort array elements using bubble sort. Bubble sort algorithm is known as the simple sorting algorithm. bubble sort algorithm, array is traversed from first element to last element. Here, present element is compared with the next element. If present element is greater than the next element, it is swapped.

// Program to SORT the Array elements using BUBBLE SORT

class  BubbleSort
{
public static void main( String args[ ] )
{
int i, j, t;
int  a[ ] = { 40, 20, 50, 10, 30 };

System.out.print( "\n Unorted Numbers  are = " );
for( i=0 ; i<5 ; i++ )
{
System.out.print( a[ i ] + "  " );
}

for( i=0 ; i<5-1 ; i++ )
{
for( j=0 ; j < (5-1-i) ; j++ )
{
if( a[ j ] > a[j+1] )
{
t = a[ j ];
a[ j ] = a[j+1];
a[j+1] = t;
}
}
}

System.out.print( "\n Sorted Numbers  are  = " );
for( i=0 ; i<5 ; i++ )
{
System.out.print( a[ i ] + "  " );
}
}
}

Output:

Unsorted Numbers  are =  40  20  50  10  30
Sorted Numbers  are  =  10  20  30  40  50

*****INSERTION  SORT ******

//  Program to SORT the Array elements using INSERTION SORT

class  InsertionSort
{
public static void main( String args[ ] )
{
int  a[ ] = { 0, 20, 40, 10, 50, 30 };
int i, n = 5;

System.out.print( " The Unsorted Array is = " );
for( i=1 ; i<=n ; i++ )
{
System.out.print( a[ i ] + " " );
}

int  tmp, j;
a[0] = -2147483648;
for( i=1 ; i<=n ; i++ )
{
tmp = a[ i ];
j = i - 1;
while( tmp < a[ j ] )
{
a[ j +1] = a[ j ];
j--;
}
a[ j +1] = tmp;
}

System.out.print( "\n The Sorted Array is   = " );
for( i=1 ; i<=n ; i++ )
{
System.out.print( a[ i ] + " " );
}
}
}

Output:

Unorted Numbers  are =  20  40  10  50  30
Sorted Numbers  are  =  10  20  30  40  50

********QUICK SORT*********

/ Java Program to Implement Quick Sort

import java.util.Scanner;

public class QuickSort
{
    /** Quick Sort function **/
    public static void sort(int[] arr)
    {
        quickSort(arr, 0, arr.length - 1);
    }
    /** Quick sort function **/
    public static void quickSort(int arr[], int low, int high)
    {
        int i = low, j = high;
        int temp;
        int pivot = arr[(low + high) / 2];

        /** partition **/
        while (i <= j)
        {
            while (arr[i] < pivot)
                i++;
            while (arr[j] > pivot)
                j--;
            if (i <= j)
            {

                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;

                i++;
                j--;
            }
        }

        /** recursively sort lower half **/
        if (low < j)
            quickSort(arr, low, j);

        /** recursively sort upper half **/
        if (i < high)
            quickSort(arr, i, high);
    }

    public static void main(String[] args)
    {
        Scanner scan = new Scanner( System.in );       

        int n, i;

        System.out.println("Enter number of integer elements");
        n = scan.nextInt();

        int arr[] = new int[ n ];

        System.out.println("\nEnter "+ n +" integer elements");
        for (i = 0; i < n; i++)
            arr[i] = scan.nextInt();

        sort(arr);

        System.out.println("\nElements after sorting ");       
        for (i = 0; i < n; i++)
            System.out.print(arr[i]+" ");           
        System.out.println();           
    }   
}

Output:

Enter number of integer elements
10

Enter 10 integer elements
877 567 3456 876 467 26 934 9876 1 4567

Elements after sorting
1 26 467 567 876 877 934 3456 4567 9876

************Merge Sort *****************

// Program to Implement Merge Sort

import java.util.Scanner;

public class MergeSort
{
    /* Merge Sort function */
    public static void sort(int[] a, int low, int high)
    {
        int N = high - low;        
        if (N <= 1)
            return;
        int mid = low + N/2;

        // recursively sort
        sort(a, low, mid);
        sort(a, mid, high);

        // merge two sorted subarrays
        int[] temp = new int[N];
        int i = low, j = mid;
        for (int k = 0; k < N; k++)
        {
            if (i == mid) 
                temp[k] = a[j++];
            else if (j == high)
                temp[k] = a[i++];
            else if (a[j]<a[i])
                temp[k] = a[j++];
            else
                temp[k] = a[i++];
        }   
        for (int k = 0; k < N; k++)
            a[low + k] = temp[k];        
    }

    public static void main(String[] args)
    {
        Scanner scan = new Scanner( System.in );       
      
        int n, i;

        System.out.println("Enter number of integer elements");
        n = scan.nextInt();

        int arr[] = new int[ n ];

        System.out.println("\nEnter "+ n +" integer elements");

        for (i = 0; i < n; i++)
            arr[i] = scan.nextInt();

        sort(arr, 0, n);

        System.out.println("\nElements after sorting ");       
        for (i = 0; i < n; i++)
            System.out.print(arr[i]+" ");           
        System.out.println();           
    }   
}

Output:

Merge Sort Test

Enter number of integer elements
20

Enter 20 integer elements
605 514 864 711 232 664 674 357 161 695 111 508 262 879 832 849 457 357 185 974

Elements after sorting
111 161 185 232 262 357 357 457 508 514 605 664 674 695 711 832 849 864 879 974