Quick Sort in java

QuickSort is a sorting algorithm which follows Divide and Conquer apporach. It picks an element as pivot and partitions the given array around the picked pivot. 

There are many different ways quickSort to pick pivot element.

  1. pick last element as pivot.
  2. pick first element as pivot (implemented below)
  3. Pick a random element as pivot.
  4. Pick median as pivot

Pseudo Code for QuickSort function :

quickSort(arr[], low, high)
{
    if (low < high)
    {
        
        pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);  // Before pi
        quickSort(arr, pi + 1, high); // After pi
    }
}

Pseudo code for partition()




partition (arr[], low, high)
{
    // pivot (Element to be placed at right position)
    pivot = arr[high];  
 
    i = (low - 1)  // Index of smaller element

    for (j = low; j <= high- 1; j++)
    {
        // If current element is smaller than the pivot
        if (arr[j] < pivot)
        {
            i++;    // increment index of smaller element
            swap arr[i] and arr[j]
        }
    }
    swap arr[i + 1] and arr[high])
    return (i + 1)
}

Quick Sort Program

class QuickSort 
{ 
    
    int partition(int arr[], int low, int high) 
    { 
        int pivot = arr[high];  //take last element as pivot
        int i = (low-1); // index of smaller element 
        for (int j=low; j<high; j++) 
        { 
             
            if (arr[j] < pivot) 
            { 
                i++; 
  
                // swap arr[i] and arr[j] 
                int temp = arr[i]; 
                arr[i] = arr[j]; 
                arr[j] = temp; 
            } 
        } 
  
        // swap arr[i+1] and  pivot 
        int temp = arr[i+1]; 
        arr[i+1] = arr[high]; 
        arr[high] = temp; 
  
        return i+1; 
    } 
  
  
   
    void sort(int arr[], int low, int high) 
    { 
        if (low < high) 
        { 
            /* here partiton function returns pivot element index so we 
                will collect it in integer variable
            int pi = partition(arr, low, high); 
  
            // Recursively sort elements before 
            // partition and after partition 
            sort(arr, low, pi-1); 
            sort(arr, pi+1, high); 
        } 
    } 
  
    //function to print array
    static void printArray(int arr[]) 
    { 
        int n = arr.length; 
        for (int i=0; i<n; ++i) 
            System.out.print(arr[i]+" "); 
        System.out.println(); 
    } 
  
   //main method
    public static void main(String args[]) 
    { 
        int arr[] = {50, 4, 7, 13, 1, 5}; 
        int n = arr.length; 
  
        QuickSort ob = new QuickSort(); 
        ob.sort(arr, 0, n-1); 
  
        System.out.println("sorted array"); 
        printArray(arr); 
    } 
} 

Output:

Sorted array:
1 4 5 7 13 50


Time Complexity :
1. Best Case O(N)
2. Worst case O(N^2)
3.Average Case O(N)

Hope you guys understand the concept of Quick Sort

Thank You, Happy Coding



Categories: JAVA

Tags: , , , , , , , , , ,

1 reply

Trackbacks

  1. Merge Sort in Java – THE NUCLEAR GEEKS

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: