Join the social network of Tech Nerds, increase skill rank, get work, manage projects...
 
  • Quick Sort Implementation in Java

    • 0
    • 0
    • 0
    • 0
    • 1
    • 0
    • 0
    • 0
    • 492
    Comment on it

    In this blog I am going to explain Quick Sort and also implement it using Java.

    Quick Sort is an efficient sorting algorithm. It is also known as partition-exchange sort. Quick sort shows an average time complexity of O(nlogn). Quick Sort is based on divide and conquer concept in which we divide our range and perform operation on the divided ranges.

    In Quick Sort array is divided into two sub arrays on the basis of pivot element. The position of pivot element remains fixed in this process. 

    One of the array elements is selected as a pivot value. Values smaller than the pivot value are placed to the left of the pivot, while larger values are placed to the right.

    For example

    here mid of array is chosen as pivot element with value 3.

    now value at index 0 is 4 which is greater then 3 and value at index 4 is 1 which is lower then 3 so we swap the values at their respective indices.

    Recursive Implementation for Quick Sort in Java

    package com.tech.blog;
    
    public class QuickSort {
    	private static int partition(int arr[], int l, int h) {
    		
    		int x = arr[h]; // initially the last value is chosen as pivot value
    		int i = (l - 1);
    
    		for (int j = l; j <= h - 1; j++) {
    			if (arr[j] <= x) {
    				i++;
    				swap(arr, i, j);
    			}
    		}
    		swap(arr, i + 1, h);
    		return (i + 1); // here updated pivot value index is returned 
    	}
    
    	private static void swap(int[] arr, int a, int b) {
    		int tmp = arr[a];
    		arr[a] = arr[b];
    		arr[b] = tmp;
    	}
    
    	private static void quickSort(int A[], int l, int h) {
    		if (l < h) {
    			/* Partitioning index */
    			int p = partition(A, l, h); // finding the pivot element
    			quickSort(A, l, p - 1); // quickSort on left subarray
    			quickSort(A, p + 1, h); // quickSort on right subarray
    		}
    	}
    
    	public static void main(String[] args) {
    		int[] arr = { 4, 2, 6, 5, 3, 9 };
    		
    		System.out.print("Elements in array before sort : ");
    		for (int a : arr)
    			System.out.print(a + " ");
    		System.out.println();
    		
    		quickSort(arr, 0, 5); //quickSort on array arr
    		
    		System.out.print("Elements in array after sort  : ");
    		for (int a : arr)
    			System.out.print(a + " ");
    		System.out.println();
    	}
    }
    

    Output of the above code is

    Elements in array before sort : 4 2 6 5 3 9 
    Elements in array after sort  : 2 3 4 5 6 9 
    

     

 1 Comment(s)

Sign In
                           OR                           
                           OR                           
Register

Sign up using

                           OR                           
Forgot Password
Fill out the form below and instructions to reset your password will be emailed to you:
Reset Password
Fill out the form below and reset your password: