Quick Sort Algorithm

Sorting in the computer science basically is arranging elements in increasing or decreasing order.
Quick Sort (also called Partition exchange sort) is a sorting algorithm that follows the divide and conquer methodology. Here are the steps:

1. Choose a “pivot” element (any random element in array). I’ve chosen the first element of array.
2. Declare two variables l and h which mark beginning and end of array (or sub array) respectively
3. Our goal is to pivot element to it’s sorted position by sending smaller elements to it’s left and larger elements to it’s right
4. Declare two variables i (which will search for elements greater than pivot) and j (which will search for elements smaller than pivot). Start with i=l and j=h
5. So here we are doing the partitioning procedure
6. increment i till you find an element greater than pivot
7. decrement j till you find an element less than or equal to pivot
8. swap array[i] and array[j]
9. do steps 8,9,10 till i<j
10. swap array[j] and pivot
11. return value of pivot position
12. recursively sort the sub array to the left of pivot and the sub array to the right of pivot

Example:

Sample: int [] array={20,50,10,30,60};
Output:

10
20
30
50
60

This video is supperr helpful to understand the logic! (LINK)

View/ Download Code: Github Link

package sort;

public class quick_sort {
	
	public static void main (String [] args){
		int [] array={20,50,10,30,60};
		quicksort(array, 0, array.length-1);
		
		for(int i=0; i<array.length; i++){
			System.out.println(array[i]);
		}
	}
	
	public static void quicksort(int [] array, int l, int h){
		if(l<h){
			int j=partition(array,l,h);
			quicksort(array, l,j);
			quicksort(array,j+1, h);
		}
	}
	
	public static int partition(int array[],int l, int h){
		int pivot= array[l];
		int i=l, j=h, temp1, temp2;
		while(i<j){
			do{
				i++;
			}while(array[i]<pivot);
			
			do{
				j--;
			}while(array[j]>pivot);
			
			if(i<j){
				temp1=array[i];
				array[i]=array[j];
				array[j]=temp1;
			}
		}
		
		temp2= array[l];
		array[l]=array[j];
		array[j]=temp2;
		
		return j;
	}

}

Happy Learning!!