Write a Java Program to Implement Quick Sort Algorithm

Quick sort is a widely used algorithm in computer science that sorts an array of elements in ascending or descending order.

It uses the divide-and-conquer strategy to recursively partition the array into smaller sub-arrays, sort them independently, and then combine them to produce the final sorted array.

In this tutorial, we will see how to implement Quick sort in Java.

The Quick sort algorithm has the following steps:

  1. Choose a pivot element from the array. The pivot element can be any element in the array. For simplicity, we will choose the first element in the array as the pivot.
  2. Partition the array into two sub-arrays such that all elements less than the pivot are in the left sub-array and all elements greater than or equal to the pivot are in the right sub-array.
  3. Recursively sort the left sub-array using Quick sort.
  4. Recursively sort the right sub-array using Quick sort.
  5. Combine the sorted left sub-array, pivot element, and sorted right sub-array to produce the final sorted array.

Here is the Java implementation of Quick sort:

public class QuickSort {
    public static void sort(int[] arr, int low, int high) {
        if (low < high) {
            int pivot = partition(arr, low, high);
            sort(arr, low, pivot - 1);
            sort(arr, pivot + 1, high);
        }
    }

    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[low];
        int i = low;
        int j = high;

        while (i < j) {
            while (arr[i] <= pivot && i < high) {
                i++;
            }
            while (arr[j] > pivot) {
                j--;
            }
            if (i < j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        arr[low] = arr[j];
        arr[j] = pivot;

        return j;
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 7, 3, 6, 1, 4};
        sort(arr, 0, arr.length - 1);

        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

In the sort method, we check if the low index is less than the high index.

If yes, we find the pivot index by calling the partition method and recursively call the sort method on the left and right sub-arrays.

In the partition method, we choose the pivot element as the first element in the array.

We then use two pointers, i and j, to scan the array from left to right and from right to left, respectively.

We swap elements at i and j if they are in the wrong sub-array.

We continue this process until i is greater than or equal to j. We then swap the pivot element with the element at j and return j.

In the main method, we create an array of integers, sort it using the sort method, and print the sorted array.

In conclusion, Quick sort is a fast and efficient sorting algorithm that uses the divide-and-conquer strategy to sort an array of elements.

The Java implementation of Quick sort is straightforward and easy to understand.

Tags

Related Posts