QUICK SORT

Quicksort (also known as partition-exchange sort) is an efficient sorting algorithm, which is used for sorting array elements.It is based on divide and conquer algorithm. It is still a commonly used algorithm for sorting. When implemented well, it can be about two or three times faster than heap sort and merge sort. Quicksort first divides a large list into two smaller sub-lists using pivot element and then recursively sort the sub arrays.

Best case time complexity : The best case is when the pivot is the median of the array,
and then the left and the right part will have same size.O(n log n)

worst case time complexity: This happens when the pivot is the smallest (or the largest) element.
Then one of the partitions is empty, and we repeat recursively the procedure for N-1 elements.O(n²)

Average case time complexity: O(n log n)

Steps to implement Quick sort

1. Pick an element, called a pivot, from the array.
2. Partitioning: reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
3. Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

Quick Sorting

Quick sort example

import java.util.Scanner;

class SortUsingQuickSort {
    
    private int arr[];
    private int length;

    public void sort(int[] inputArr) {
        
        if (inputArr == null || inputArr.length == 0) {
            return;
        }
        this.arr = inputArr;
        length = inputArr.length;
        quickSort(0, length - 1);
    }

    private void quickSort(int lowerIndex, int higherIndex) {
        
        int i = lowerIndex;
        int j = higherIndex;
        //taking pivot as middle index number
        int pivot = arr[lowerIndex+(higherIndex-lowerIndex)/2];
        // Divide into two arrays
        while (i <= j) {        /* In each iteration, we'll check a number which is greater then the pivot from left side and also we'll check a number which is less then the pivot from right side.*/

            while (arr[i] < pivot) {
                i++;
            }
            while (arr[j] > pivot) {
                j--;
            }
            if (i <= j) {
                exchangeNumbers(i, j);
                //move index to next position on both sides
                i++;
                j--;
            }
        }
        // call quickSort() method recursively
        if (lowerIndex < j)
            quickSort(lowerIndex, j);
        if (i < higherIndex)
            quickSort(i, higherIndex);
    }

    private void exchangeNumbers(int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    public static void main(String a[]){
        
        SortUsingQuickSort sorting = new SortUsingQuickSort();
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the size of the array : ");
        int size = sc.nextInt();
        int[] input = new int[size];
        System.out.println("Enter the elements of the array : ");
        for(int i = 0; i < size; i++){
            input[i] = sc.nextInt();
        }
        System.out.print("\n Sorted array : ");
        sorting.sort(input);
        for(int i:input){
            System.out.print(i);
            System.out.print(" ");
        }
    }
}

Selection Sort

Selection Sort

In computer programming, selection sort is a sorting algorithm, which selects an elements and places it to its right place. It is inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is popular for its simplicity, and performance advantages over other complicated algorithms in certain situations.

The algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

64 25 12 22 11      ►    11 64 25 12 22     ►    11 12 64 25 22     ►    11 12 22 64 25      ► 11 12 22 25 64

Selection Sort Example

import java.util.Scanner;

public class Solution {

    public static void doSelectionSort(int[] arr){
       
        for (int i = 0; i < arr.length - 1; i++)
        {
            int index = i;
            for (int j = i + 1; j < arr.length; j++)
                if (arr[j] < arr[index])
                    index = j;
    
            int smaller = arr[index];
            arr[index] = arr[i];
            arr[i] = smaller;
        }
        printArray(arr);
    }

    public static void printArray(int[] arr){
        System.out.println();
        System.out.println("Final Sorted array..");
        for(int i : arr){
            System.out.print(i+", ");
        }
    }
   
    public static void main(String args[]){
       
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the size of Array.. ");
        int size = sc.nextInt();
        System.out.println("Enter array elements.. ");
        int arr[] = new int[size];
        for(int i = 0; i < size; i++){
            arr[i] = sc.nextInt();
        }
        Solution.doSelectionSort(arr);
    }
}

Insertion Sort

Insertion sort is one of the popular sorting algorithm that sorts the given array and builds the sorted array(list). It is much less efficient on large list than more advance algorithms like Quicksort, Heapsort, Mergesort. However there are sill some advantages of using Insertion Sort:

• Simple Implementation
• Efficient for small data set
• Faster than Quicksort for small data list.

Properties of Insertion Sort

• Best Case time complexity : Here the elements are already in sorted array so no shifting of elements takes place. So we only traverse through the elements of array so its time complexity is O(n)
• Worst Case time complexity : Here the elements are in reverse sorted order so for each element shifting takes place. So its time complexity is O(n²).

Insertion Sorting process(source: wikimedia.org)

Insertion Sort Example  

import java.io.*;

import java.util.*;

public class Solution {

    public static void insertionSort(int[] A){
        for(int i = 1; i < A.length; i++){
            int value = A[i];
            int j = i - 1;
            while(j >= 0 && A[j] > value){
                A[j + 1] = A[j];
                j = j - 1;
            }
            A[j + 1] = value;
        }

        printArray(A);
    }


    static void printArray(int[] ar) {
        for(int n: ar){
            System.out.print(n+" ");
        }
    }
    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();
        }
        insertionSort(ar);
    }
}