[Java] Quick Sort Algorithm

[Java] Quick Sort Algorithm

Quick sort is a very fast sort algorithm, which it’s used “divide and conquer strategy” to sort the data. On the average and best case, it has O(n log n) time complexity, on worst case, it has O(n^2) time complexity. And it is unstable sorting.


You can follow below step to make quick sort algorithm:

First, you can take the value of the leftmost elements as a pivot value, or you can take any value which is in range of sorted values.

Second, make all elements which lesser than the pivot go to the left part of the array, and all elements which greater than the pivot go to the right part of the array.

Third, apply quick sort algorithm recursively to the left and right parts.

Java Code:

public class QuickSort {
    static int partition(int arr[], int left, int right) {
        int i = left, j = right;
        int tmp;
        int pivot = arr[i];//take the value of the leftmost elements

        while (i <= j) {
            while (arr[i] < pivot)//when pivot is greater than arr[i],left index+1
                i++;
            while (arr[j] > pivot)//when arr[i] is greater than pivor, right index-1
                j--;
            if (i <= j) {
                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i++;
                j--;
            }
        }
        return i;
    }

    static int[] quickSort(int arr[], int left, int right) {
        int index = partition(arr, left, right);
        if (left < index - 1)
            quickSort(arr, left, index - 1);
        if (index < right)
            quickSort(arr, index, right);
        return arr;
    }

    public static void main(String[] args) {
        int x[] = { 12, 14, 29, 20, 22, 39, 41, 52, 1, 7, 10, 101, 93, 5 };
        int y[] = quickSort(x,0,x.length-1);

        for(int k = 0;k < y.length;k++){
            int element = y[k];
            System.out.print(element+",");
        }
    }
}

Example:
I need to sort 12,14,29,20,22,39,41,52,1,7,10,101,93,5
and take 12 to be pivot. From left side to right side to search the value of element greater than pivot, and search the value of element lesser than pivot from right to left.

12,14,29,20,22,39,41,52,1,7,10,101,93,5

swap them and recursive:
12,5,29,20,22,39,41,52,1,7,10,101,93,14
12,5,10,20,22,39,41,52,1,7,29,101,93,14
12,5,10,7,22,39,41,52,1,20,29,101,93,14
12,5,10,7,1,39,41,52,22,20,29,101,93,14

because the right index is left side of left index, swap pivot and right index:

1,5,10,7,12,39,41,52,22,20,29,101,93,14

stop partition, then sorting left side of pivot:

1,5,10,7,12,39,41,52,22,20,29,101,93,14
1,5,10,7,12,39,41,52,22,20,29,101,93,14
1,5,10,7,12,39,41,52,22,20,29,101,93,14
1,5,7,10,12,39,41,52,22,20,29,101,93,14
1,5,7,10,12,39,41,52,22,20,29,101,93,14
1,5,7,10,12,39,14,52,22,20,29,101,93,41
1,5,7,10,12,39,14,29,22,20,52,101,93,41

1,5,7,10,12,20,14,29,22,39,52,101,93,41
1,5,7,10,12,14,20,22,29,39,52,101,93,41
1,5,7,10,12,14,20,22,29,39,52,41,93,101
1,5,7,10,12,14,20,22,29,39,41,52,93,101

(Visited 13 times, 1 visits today)
Comments are closed.