Content-Type: multipart/related; start=; boundary=----------Oru4nNvTFJzVTCsqEmKXj2 Content-Location: http://java2novice.com/java-sorting-algorithms/quick-sort/ Subject: =?utf-8?Q?Implement=20quick=20sort=20in=20java.=20-=20Java=20sorting=20algorithm=20programs?= MIME-Version: 1.0 ------------Oru4nNvTFJzVTCsqEmKXj2 Content-Disposition: inline; filename=default.htm Content-Type: text/html; charset=utf-8; name=default.htm Content-ID: Content-Location: http://java2novice.com/java-sorting-algorithms/quick-sort/ Content-Transfer-Encoding: Quoted-Printable Implement quick sort in java. - Java sorting algorithm programs= = = = # Program: Implement quick sort in java.

Quicksort or partition-exchange sort, is a fast s= orting algorithm, which is using divide and conquer algorithm. Quicksor= t first divides a large list = into two smaller sub-lists: the low elements and the high elements. = Quicksort can then recursively sort the sub-lists.

Steps to implement Quick sort:

1) Choose an element, called pivot, from the list. Generally pivot c= an be the middle index element.
2) Reorder the list so that all elements with values less than the p= ivot come before the pivot, while all elements with values = greater than the pivot come after it (equal values can go either way= ). After this partitioning, the pivot is in its final position. = This is called the partition operation.
3) Recursively apply the above steps to the sub-list of elements wit= h smaller values and separately the sub-list of elements with greater va= lues.

= The complexity of quick sort in the average case = is =CE=98(n log(n)) and in the worst case is =CE=98(n2).

 ```package com.java2novice.sorting; public class MyQuickSort { = private int array[]; private int length; public void sort(int[] inputArr) { = if (inputArr =3D=3D null || inputArr.length =3D=3D 0) { return; } this.array =3D inputArr; length =3D inputArr.length; quickSort(0, length - 1); } private void quickSort(int lowerIndex, int higherIndex) { = int i =3D lowerIndex; int j =3D higherIndex; // calculate pivot number, I am taking pivot as middle index number int pivot =3D array[lowerIndex+(higherIndex-lowerIndex)/2]; // Divide into two arrays while (i <=3D 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 numbe= r = * from right side which is less then the pivot value. Once the searc= h = * is done, then we exchange both numbers. */ while (array[i] < pivot) { i++; } while (array[j] > pivot) { j--; } if (i <=3D j) { exchangeNumbers(i, j); //move index to next position on both sides i++; j--; } } // call quickSort() method recursively if (lowerIndex < j) quickSort(lowerIndex, j); if (i < higherIndex) quickSort(i, higherIndex); } private void exchangeNumbers(int i, int j) { int temp =3D array[i]; array[i] =3D array[j]; array[j] =3D temp; } = public static void main(String a[]){ = MyQuickSort sorter =3D new MyQuickSort(); int[] input =3D {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: `2 2 12 20 24 45 53 56 56 75 99 `

#### Java Sorting Algorithms Examples

Knowledge Centre
Inner class and Anonymous class
Inner class: classes defined in other classes, including those de= fined in methods are called inner classes. An inner class can have any accessibility including private.

Anonymous class: Anonymous class is a class defined inside a meth= od without a name and is instantiated and declared in the same place and cannot have explicit constructors.