| Description: |
Based on our understanding of partitioning in quick sort, we will now try to write an algorithm for it, which is as follows.
Step 1 − Choose the highest index value has pivot Step 2 − Take two variables to point left and right of the list excluding pivot Step 3 − left points to the low index Step 4 − right points to the high Step 5 − while value at left is less than pivot move right Step 6 − while value at right is greater than pivot move left Step 7 − if both step 5 and step 6 does not match swap left and right Step 8 − if left ≥ right, the point where they met is new pivot  |
| Code 1: |
package com.kartik.sorting;
import com.kartik.sorting.tree.BTreePrinter;
/**
*
*
* @author MandalKC This method use First Divide method and after than Selection
* Sort algo
*
*/
public class QuickSort {
private int array[];
private int length;
/**
*
* @param inputArr
*/
public void sort(int[] inputArr) {
System.out.println("Before Quick Soring --->>");
printNumbers(inputArr);
System.out.println("After Quick Soring start--->>");
if (inputArr == null || inputArr.length == 0) {
return;
}
this.array = inputArr;
length = inputArr.length;
quickSort(0, length - 1);
}
/**
*
* @param lowerIndex
* @param higherIndex
*/
private void quickSort(int lowerIndex, int higherIndex) {
int i = lowerIndex;
int j = higherIndex;
// calculate pivot number, I am taking pivot as middle index number
int pivot = array[lowerIndex + (higherIndex - lowerIndex) / 2];
// Divide into two arrays
while (i <= j) {
/**
* In each iteration, we will identify a number from left side which
* is greater then the pivot value, and also we will identify a
* number from right side which is less then the pivot value. Once
* the search is done, then we exchange both numbers.
*/
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j--;
}
if (i <= j) {
exchangeNumbers(i, j);
// move index to next position on both sides
i++;
j--;
}
BTreePrinter.printNode(HeapSort.drawTree(array));
printNumbers(array);
}
// call quickSort() method recursively
if (lowerIndex < j)
quickSort(lowerIndex, j);
if (i < higherIndex)
quickSort(i, higherIndex);
}
/**
*
* @param i
* @param j
*/
private void exchangeNumbers(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
/**
*
* @param input
*/
private static void printNumbers(int[] input) {
for (int i = 0; i < input.length; i++) {
System.out.print(input[i] + ", ");
}
System.out.println("\n");
}
/**
*
* @param a
*/
public static void main(String a[]) {
QuickSort sorter = new QuickSort();
int[] input = { 10, 34, 2, 56, 7, 67, 88, 42 };
// int[] input = {24,2,45,20,56,75,2,56,99,53,12};
sorter.sort(input);
for (int i : input) {
System.out.print(i);
System.out.print(" ");
}
}
}
|
| Output: |
Before Quick Soring --->>
10, 34, 2, 56, 7, 67, 88, 42,
After Quick Soring start--->>
10 / \ / \ / \ / \ 34 2 / \ / \ / \ / \ 42 7 67 88 / 56 10, 34, 2, 42, 7, 67, 88, 56,
10
/ \ / \ / \ / \ 34 2 / \ / \ / \ / \ 42 7 67 88 / 56 10, 34, 2, 42, 7, 67, 88, 56,
2
/ \ / \ / \ / \ 34 10 / \ / \ / \ / \ 42 7 67 88 / 56 2, 34, 10, 42, 7, 67, 88, 56,
2
/ \ / \ / \ / \ 34 10 / \ / \ / \ / \ 42 7 67 88 / 56 2, 34, 10, 42, 7, 67, 88, 56,
2
/ \ / \ / \ / \ 7 10 / \ / \ / \ / \ 42 34 67 88 / 56 2, 7, 10, 42, 34, 67, 88, 56,
2
/ \ / \ / \ / \ 7 10 / \ / \ / \ / \ 42 34 67 88 / 56 2, 7, 10, 42, 34, 67, 88, 56,
2
/ \ / \ / \ / \ 7 10 / \ / \ / \ / \ 34 42 67 88 / 56 2, 7, 10, 34, 42, 67, 88, 56,
2
/ \ / \ / \ / \ 7 10 / \ / \ / \ / \ 34 42 67 56 / 88 2, 7, 10, 34, 42, 67, 56, 88,
2
/ \ / \ / \ / \ 7 10 / \ / \ / \ / \ 34 42 56 67 / 88 2, 7, 10, 34, 42, 56, 67, 88,
2 7 10 34 42 56 67 88
|
I am Kartik Chandra Mandal from Bangalore, India. Working as software engineer in Java technology. Have good knowledge of OWASP and CSRF in security for applications and it's implementation in Java technology.