Implement Quick Sort Algorithm in Java

Exercise:

Write a Java Program to implement Quick Sort Algorithm.

Click Here to View the Solution!
import java.util.Arrays;

public class QuickSort {
      //partitioning the array according to pivot
      int partition(int array[], int low, int high) {

        //last element = pivot
        int pivot = array[high];
        int i = (low - 1);

        //Put the elements < pivot on left else right
        for (int j = low; j < high; j++) {

            // compare all elements with pivot and swap according to given condition
            // sort in ascending order
            if (array[j] <= pivot) {

                // increase the second pointer if
                // smaller element is swapped with greater
                i++;
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }

        // put pivot in position
        // so that element on left are smaller
        // element on right are greater than pivot
        int temp = array[i + 1];
        array[i + 1] = array[high];
        array[high] = temp;
        return (i + 1);
    }
    void quickSort(int array[], int low, int high) {
        if (low < high) {

            // Select pivot position and put all the elements smaller
            // than pivot on the left and greater than pivot on right
            int pi = partition(array, low, high);

            // sort the elements on the left of the pivot
            quickSort(array, low, pi - 1);

            // sort the elements on the right of pivot
            quickSort(array, pi + 1, high);
        }
    }
    //Driver code
    public static void main(String args[]) {
        int[] data = { -12,2,34,58,9,0,-456,-898,98,45};
        int size = data.length;

        // create an object of the Main class
        QuickSort qs = new QuickSort();
        qs.quickSort(data, 0, size - 1);
        System.out.println("Sorted Array: ");
        System.out.println(Arrays.toString(data));
    }

}
// to sort in descending order just put the condition as if (array[j] >= pivot)
Click Here to View the Output!
Sorted Array: 
 [-898, -456, -12, 0, 2, 9, 34, 45, 58, 98]
Click Here to View the Explanation!
  • This program is used to perform the implementation of the quick sort algorithm.
  • Initially, a partion() method is initialized that is used for dividing the array according to the variable pivot that holds the last element as pivot = array[high].
  • An if statement is used that arranges all the elements in ascending order thus holding the condition (array[j] <= pivot) i.e. place all the elements smaller than pivot on the left and all the elements greater than pivot on the right of pivot.
  • A quickSort() method is initialized that sorts the left side of the array first and then the right side by using the previous partition() method.
  • Finally, in the main method, an integer array data is initialized as { -12,2,34,58,9,0,-456,-898,98,45} over which the quicksort method is applied that will give the output [-898, -456, -12, 0, 2, 9, 34, 45, 58, 98].
  • The elements can also be sorted in descending order by changing the if statement as (array[j] >= pivot).

%d bloggers like this: