Subject: Analysis Of Algorithm

Topic: Divide Aqnd Conquer

Difficulty: Medium

Quick Sort : - It is a sorting method.

To Prove :- Worst case efficiency of quick sort is $o(n^2)$

Proof :- The partitioning step: at least, n − 1 comparisons.

• At each next step for n ≥ 1, the number of comparisons is one less, so that -

• T(n) = T(n − 1) + (n − 1); T(1) = 0.

• “Telescoping” T(n) − T(n − 1) = n − 1:

• T(n)+T(n − 1)+T(n − 2)+. . .+T(3)+T(2) −T(n − 1)−T(n − 2)−. . .−T(3)−T(2)− T(1)

• T(n) = (n − 1) + (n − 2) +. . .+ 2 + 1 − 0

• T(n) = (n − 1) + (n − 2) +. . .+ 2 + 1

• T(n) = $\frac{(n-1)n}{2}$

This yields that T(n) ∈ $o(n^2).$

Therefore, the worst case efficiency of quick sort is $o(n^2).$

Program Implementation of Quick Sort is : -

import java.util.Arrays;

class Quicksort {

  // method to find the partition position
  static int partition(int array[], int low, int high) {

    // choose the rightmost element as pivot
    int pivot = array[high];

    // pointer for greater element
    int i = (low - 1);

    // traverse through all elements
    // compare each element with pivot
    for (int j = low; j < high; j++) {
      if (array[j] <= pivot) {

        // if element smaller than pivot is found
        // swap it with the greatr element pointed by i
        i++;

        // swapping element at i with element at j
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
      }

    }

    // swapt the pivot element with the greater element specified by i
    int temp = array[i + 1];
    array[i + 1] = array[high];
    array[high] = temp;

    // return the position from where partition is done
    return (i + 1);
  }

  static void quickSort(int array[], int low, int high) {
    if (low < high) {

      // find pivot element such that
      // elements smaller than pivot are on the left
      // elements greater than pivot are on the right
      int pi = partition(array, low, high);

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

      // recursive call on the right of pivot
      quickSort(array, pi + 1, high);
    }
  }
}

// Main class
class Main {
  public static void main(String args[]) {

    int[] data = { 8, 7, 2, 1, 0, 9, 6 };
    System.out.println("Unsorted Array");
    System.out.println(Arrays.toString(data));

    int size = data.length;

    // call quicksort() on array data
    Quicksort.quickSort(data, 0, size - 1);

    System.out.println("Sorted Array in Ascending Order: ");
    System.out.println(Arrays.toString(data));
  }
}