Share:- Whatsapp Facebook Facebook

------------------------------------- Welcome to Developerhelpway Q&A, where you can ask questions and receive answers from other members of the community.

Categories

0 votes
104 views
Java quicksort sorting algorithm with running code and example
in Data Structure And Algorithm by

1 Answer

0 votes
I am providing a very simple code for quicksort. See the following steps for quicksort sorting algorithm.
Step 1 − Choose the first value as pivot
Step 2 − Take two variables which points left and right excluding pivot
Step 3 − left point having low index
Step 4 − right points having high index
Step 5 − While value at left is less than pivot move into right
Step 6 − While value at right is greater than pivot move into left
Step 7 − If 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

See the running code of quicksort:-

public class QuickSort {

    public static void main(String[] args) {
        int arr[] = {14, 17, 13, 15, 19, 10, 3, 16, 9, 12};
        QuickSort qs = new QuickSort();
        System.out.print("Unsorted Array:");
        System.out.print("[");
        for(int i=0; i<arr.length-1;i++){
            System.out.print(" "+arr[i]);
        }
        System.out.println("]");
        qs.doQuickSort(arr,0,arr.length-1);
        System.out.print("\nSorted Array:");
        System.out.print("[");
        for(int i=0; i<arr.length-1;i++){
            System.out.print(" "+arr[i]);
        }
        System.out.println("]");
    }
    private void doQuickSort(int[] arr, int first, int last) {
        if(first <= last){
            int pivotLine = partition(arr,first,last);   
            doQuickSort(arr, first, pivotLine-1);
            doQuickSort(arr, pivotLine+1, last);
        }
    }
    private int partition(int[] arr, int first, int last) {
        boolean done = false;
        int pivotVal = arr[first];
        int leftMarker = first+1;
        int rightMarker = last;
        while(!done){
            while(leftMarker <= rightMarker && arr[leftMarker] < pivotVal)
                leftMarker++;
            while(rightMarker >= leftMarker && arr[rightMarker] > pivotVal)
                rightMarker--;
            if(rightMarker < leftMarker){
                done = true;
            }else{
                doSwap(arr, leftMarker, rightMarker);
            }
        }
        doSwap(arr, first, rightMarker);
        return rightMarker;
    }
    private void doSwap(int[] arr, int leftMarker, int rightMarker) {
        int temp;
        temp = arr[leftMarker];
        arr[leftMarker] = arr[rightMarker];
        arr[rightMarker] = temp;
    }
}
Output:-
Unsorted Array:[ 14 17 13 15 19 10 3 16 9]
Sorted Array:[ 3 9 10 12 13 14 15 16 17]
by (3.1k points)
...