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:
- Choose a “pivot” element (any random element in array). I’ve chosen the first element of array.
- Declare two variables l and h which mark beginning and end of array (or sub array) respectively
- 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
- 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
- So here we are doing the partitioning procedure
- increment i till you find an element greater than pivot
- decrement j till you find an element less than or equal to pivot
- swap array[i] and array[j]
- do steps 8,9,10 till i<j
- swap array[j] and pivot
- return value of pivot position
- 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!!