So here is another sorting algorithm, “Quick Sort” which I have implemented it using ArrayList which is inplace sorting algorithm.
Worst case for quick sort to run is O (n^2).
Implementing Quick Sort using divide & conquer technique.
Our divide part will have partitioning of array into 2 array where each element from left side of array will be smaller then the each element from the right side of array. This partitioning will be based on one element that we choose in each iteration is called PIVOT element.
Our conquer part takes care of moving all element less than pivot at left and greater than pivot at right half of array and continue doing it recursively.
Below is the source code given with the project structure. And I have kept many System.out statement which is just for the understanding purpose. You may find it tedious but some time, for some people it might save time to understand the flow.
Project Structure:
QuickSort.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
package daa; import java.util.ArrayList; import java.util.Random; public class QuickSort { private static ArrayList<Integer> inputArray = new ArrayList<Integer>(); public QuickSort(ArrayList<Integer> inputArray){ QuickSort.inputArray = inputArray; } public void startQuickStart(int start,int end){ int q; if(start<end){ q = partition(start, end); startQuickStart(start, q); startQuickStart(q+1, end); } } public ArrayList<Integer> getSortedArray(){ return QuickSort.inputArray; } int partition(int start,int end){ System.out.println("\n---------Iteration Starts----------"); System.out.println("\nSorting Window from index number:"+start+" to "+end); int init = start; int length = end; Random r = new Random(); int pivotIndex = nextIntInRange(start,end,r); int pivot = inputArray.get(pivotIndex); System.out.println("Pivot Element "+pivot+" at index:"+pivotIndex); while(true){ while(inputArray.get(length)>pivot && length>start){ length--; } while(inputArray.get(init)<pivot && init<end){ init++; } if(init<length){ int temp; temp = inputArray.get(init); inputArray.set(init,inputArray.get(length)); inputArray.set(length,temp); length--; init++; System.out.println("\nAfter Swapping"); for(int i=start;i<=end;i++){ System.out.print(inputArray.get(i)+" "); } }else{ System.out.println("\n---------Iteration Ends---------"); return length; } } } // Below method is to just find random integer from given range static int nextIntInRange(int min, int max, Random rng) { if (min > max) { throw new IllegalArgumentException("Cannot draw random int from invalid range [" + min + ", " + max + "]."); } int diff = max - min; if (diff >= 0 && diff != Integer.MAX_VALUE) { return (min + rng.nextInt(diff + 1)); } int i; do { i = rng.nextInt(); } while (i < min || i > max); return i; } } |
MainPractise.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
import java.util.ArrayList; import daa.QuickSort; public class MainPractise implements Cloneable { public static void main(String[] args) { ArrayList<Integer> unsortedArray = new ArrayList<Integer>(); unsortedArray.add(2); unsortedArray.add(8); unsortedArray.add(6); unsortedArray.add(3); unsortedArray.add(12); unsortedArray.add(4); unsortedArray.add(7); QuickSort qsu = new QuickSort(unsortedArray); System.out.println("---------Initial Unsorted Array---------"); for(int i:qsu.getSortedArray()){ System.out.print(i+" "); } qsu.startQuickStart(0, unsortedArray.size()-1); System.out.println("\n\n---------Processed sorted Array---------"); for(int i:qsu.getSortedArray()){ System.out.print(i+" "); } } } |
Output:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
---------Initial Unsorted Array--------- 2 8 6 3 12 4 7 ---------Iteration Starts---------- Sorting Window from index number:0 to 6 Pivot Element 12 at index:4 After Swapping 2 8 6 3 7 4 12 ---------Iteration Ends--------- ---------Iteration Starts---------- Sorting Window from index number:0 to 5 Pivot Element 8 at index:1 After Swapping 2 4 6 3 7 8 ---------Iteration Ends--------- ---------Iteration Starts---------- Sorting Window from index number:0 to 4 Pivot Element 3 at index:3 After Swapping 2 3 6 4 7 ---------Iteration Ends--------- ---------Iteration Starts---------- Sorting Window from index number:0 to 1 Pivot Element 3 at index:1 ---------Iteration Ends--------- ---------Iteration Starts---------- Sorting Window from index number:0 to 1 Pivot Element 3 at index:1 ---------Iteration Ends--------- ---------Iteration Starts---------- Sorting Window from index number:0 to 1 Pivot Element 2 at index:0 ---------Iteration Ends--------- ---------Iteration Starts---------- Sorting Window from index number:2 to 4 Pivot Element 7 at index:4 ---------Iteration Ends--------- ---------Iteration Starts---------- Sorting Window from index number:2 to 4 Pivot Element 4 at index:3 After Swapping 4 6 7 ---------Iteration Ends--------- ---------Iteration Starts---------- Sorting Window from index number:3 to 4 Pivot Element 6 at index:3 ---------Iteration Ends--------- ---------Processed sorted Array--------- 2 3 4 6 7 8 12 |
You can have above code from GIT.
https://github.com/Niravkumar-Patel/SnippetExampleRepo.git