Sorting Algorithms - JAVA👽 

Sorting algorithms are used to arrange data into a specific pattern (ascending or descending).We mainly discuss 5 patterns in this blog.  We can use any of this methods to sort an array.

• Selection sort
• Insertion sort
• Bubble sort
• Merge sort
• Quick sort 

Selection sort ...

Selection sort is well perform for small arrays and doesn't require extra temporary storage.  It uses selection method. It is poor to deal with huge list of items. It simple and easy to implement. It's time complexity is O(n^2) and space complexity is O(1).

Here is the basic code for selection sort.

for (int i=0; i< array.length-1; i++){

            int curruntMinimum = i;

            for (int curruntItem=i+1; curruntItem<array.length;curruntItem++){

                if(array[curruntItem] < array[curruntMinimum]){

                    curruntMinimum = curruntItem;

                }

            }

            if(i != curruntMinimum){

                int temp = array[i];

                array[i] = array[curruntMinimum];

                array[curruntMinimum] = temp;

            }

 }

Insertion sort ...

Insertion sort is well perform for small arrays and minimal storage is required.  It  twice faster than bubble sort. It does not deal  well with huge list of items. It is also
simple and easy to implement. It's time complexity is O(n^2) and space complexity is O(1) or O(n).

Here is the base code for insertion sort.

for (int elementIndex = 1; elementIndex < array.length; elementIndex++) {  

            int tempElement = array[elementIndex];

            int previousElementIndex = elementIndex - 1;

            while (previousElementIndex > -1 && array[] > tempElement) {

                array[previousElementIndex + 1] = array[previousElementIndex];

                previousElementIndex--;

            }

            array[previousElementIndex + 1] = tempElemnt;

}

Bubble sort ...

Insertion sort is well perform for small arrays and minimal storage is required.  It  twice faster than bubble sort. It does not deal  well with huge list of items. It is also
simple and easy to implement. It's time complexity is O(n^2) and space complexity is O(1) or O(n).

Here is the base code for bubble sort.

public static void sort(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 elements 

int temp = arr[j]; 

arr[j] = arr[j + 1]; 

arr[j + 1] = temp; 

}

  }

}

}

Merge sort ...

Merge sort can be applied to files of any size and extra storage is required.  Merge sort follows divide and conquer approach in which, the list is first divided into the sets of equal elements and then each half of the list is sorted by using merge sort. The sorted list is combined again to from an elementary sorted array. It's time complexity is O(n log (n)) and space complexity is O(n).

Here is the base code for merge sort.

public static void sort(int[] arr, int left, int right) {

    if (left < right) {

      // Find the middle point

      int mid = left + (right - left) / 2;

      // Sort first and second halves

      sort(arr, left, mid);

      sort(arr, mid + 1, right);

      // Merge the sorted halves

      merge(arr, left, mid, right);

    }

  }

  private static void merge(int[] arr, int left, int mid, int right) {

    // Sizes of two subarrays

    int n1 = mid - left + 1;

    int n2 = right - mid;

    // Create temporary arrays

    int[] leftArr = new int[n1];

    int[] rightArr = new int[n2];

    // Copy data to temporary arrays

    for (int i = 0; i < n1; i++) {

      leftArr[i] = arr[left + i];

    }

    for (int j = 0; j < n2; j++) {

      rightArr[j] = arr[mid + 1 + j];

    }

    // Merge the temporary arrays back into arr[left..right]

    int i = 0, j = 0, k = left;

    while (i < n1 && j < n2) {

      if (leftArr[i] <= rightArr[j]) {

        arr[k] = leftArr[i];

        i++;

      } else {

        arr[k] = rightArr[j];

        j++;

      }

      k++;

    }

    // Copy the remaining elements of leftArr[] if there are any

    while (i < n1) {

      arr[k] = leftArr[i];

      i++;

      k++;

    }

    // Copy the remaining elements of rightArr[] if there are any

    while (j < n2) {

      arr[k] = rightArr[j];

      j++;

      k++;

    }

  }

Quick sort ...

Merge sort deals very well with large lists and extra storage is required. Quick sort is the most optimized sort algorithms which performs sorting in O(n log n) comparisons . Like Merge and Quick sort also work using divide and conquer approach. 

Here is the base code for quick sort.

static void quicksort(int[] arr, int start, int end ){

        int mid = (start+end)/2;

        int i = start;

        int j = end;

        int pivot = arr[mid];

        while (i<=j){

            while (arr[i] < pivot){

                i++;

            }

            while (arr[j]>pivot){

                j--;

            }

            if(i<=j){

                int temp = arr[i];

                arr[i] = arr[j];

                arr[j] = temp;

                i++;

                j--;

            }

        }

        if(start < j){

            quicksort(arr,start,j);

        }

        if(end>i){

            quicksort(arr,i,end);

        }

}