way this algorithm solution :
it's an in place recursive implementation of QuickSort encapsulated in this class.
this method quickSort(int low , int high) called recursivly to sort it's array .
Steps to implement Quick sort in place :
1- chose an element called pivot from array or list. generally is middle element pivot .
2- reorder the list , so that all element with the values is less than the pivot come before the pivot , and element with values is greater than the pivote come after the pivot . is also known as partitioning after partitioning .
3- recursively apply the above steps to the sub-list of elements with the smaller
values and saperatly the sub-list , of elements with greater values.
4- if array its contain one element and zero element the array is sorted .
5- in this example we have array of integers is not sorted , and we need to sort array in ascending order.
6- our array is {6 , 5 , 3 , 1 , 8 , 4 , 2 , 7} and we first choose 3 as pivot .
7- now partitioning is starts and we pick 6 on left side of side because its greater than 3 , now in right side we leave 4 because its greater than 3 and pick 2 for swaping to 6 .
8- our array look like {2 , 5 , 3 , 1 , 8 , 7 , 6 , 4} .
9- now we pick 5 on left side because its greater than 3 and on right side pick 1 and swap with 5 .
10 - now our array look like is {2 , 1 , 3 , 5 , 8 , 7 , 6 , 4} and after we done with all elements respect to 3 as pivot .
11 - we can take sub-array at left side of 3 and applying swap 1 with 2
12- our array look like {1 , 2 , 3 , 5 , 8 , 7 , 6 , 4} this will sort the left sub-array .
13 - now we take the right side sub-array and we choose 4 as pivot and pick 5 because its greater than pivot and come after it , and swap them .
14- our array look like {1 , 2 , 3 , 4 , 8 , 7 , 6 , 5} and we choose 6 as pivot and choose 5 on right side 6 and pick 8 on right side 6 swap them , swap 5 against 8 .
15- now our array is {1 , 2 , 3 , 4 , 5 , 7 , 6 , 8 } and apply the same procedure.
16- finally our array sorted is {1 , 2 , 3 , 4 , 5 , 6 , 7 , 8}
/**
* java class to sort array of integers using QuickSort Algorithm
*
*/
public class QuickSortDemo {
public static void main(String args[]) {
int unsorted[] = {6 , 5 , 3 , 1 , 8 ,7 , 2 , 4} ;
System.out.println("the original array : " + Arrays.toString(unsorted));
// sort this array using quicksort algorithm.
QuickSort algorithm = new QuickSort();
algorithm.sort(unsorted);
//printing the sorted array.
System.out.println("the sorted array : " + Arrays.toString(unsorted));
}
}
/** java program to sort numbers using QickSort Algorithm , this
* quicksort is divide and conquer algorithm ,which divide the
* original list and merge it and sort it to created sorted output .
*/
class QuickSort() {
int input[];
int length;
public void sort(int [] numbers) {
if(numbers == null || numbers.length == 0) {
return;
}
this.input= numbers;
lenght = numbers.length;
quickSort(0 , lenght - 1);
}
//this method implements in-place QuickSort algorithm recursivly
private void quickSort(int low , int high) {
int i = low;
int j = high;
// this pivot it's in mid element.
int pivot = input [low + (high - low) / 2];
//then we divide into tow arrays .
while(i <= j) {
/** in above elaboration , in each iteration we will identify the
* numbers of left side which is greater than pivot ,
* and then we identify the right number side which is less than pivot,
*/ once the search is complete we can swap both numbers.
while(input[i] < pivot) {
i++;
} while(input[j] < pivot) {
j--;
}
if(i <= j) {
swap(i , j);
i++;
j--;
//move the index to next position to both sides.
}
}
// call qickSort() method recursively
if(i <= high) {
quickSort (i , high);
}
if(low <= j) {
quickSort(low , j);
}
}
private void swap(int i , int j) {
int temp = input[i];
input[i] = input[j];
input[j] = temp;
}
}
