Question

. Consider QuickSort on the array A[1:n] and assume that the pivot element x (used to split the array A[lo:hi] into two portions such that all elements in the left portion A[lo:m] are ≤x and all elements in the right portion A[m:hi] are ≥x) is the second element of the array to be split (i. e., A[lo+1]).

For a specific value of n at least 13 (your choice), construct an assignment of the numbers 1...n to the n array elements that causes QuickSort, with the stated choice of pivot, to

(a) execute optimally (that is A[lo:m] and A[m:hi] are always of equal size)

(b) execute in the slowest possible way.

Answer 1

class QuickSort {

  int partition(int arr[], int low, int high) {

    int pivot = arr[high];

    int i = (low - 1);

    for (int j = low; j < high; j++) {

      if (arr[j] <= pivot) {

        i++;

        int temp = arr[i];

        arr[i] = arr[j];

        arr[j] = temp;

      }

    }

    int temp = arr[i + 1];

    arr[i + 1] = arr[high];

    arr[high] = temp;

    return i + 1;

  }

  void sort(int arr[], int low, int high) {

    if (low < high) {

      int pi = partition(arr, low, high);

      sort(arr, low, pi - 1);

      sort(arr, pi + 1, high);

    }

  }

  static void printArray(int arr[]) {

    int n = arr.length;

    for (int i = 0; i < n; ++i) System.out.print(arr[i] + " ");

    System.out.println();

  }

  public static void main(String args[]) {

    int arr[] = { 8, 3, 25, 6, 10, 17, 1, 2, 18, 5 };

    int n = arr.length;

    QuickSort ob = new QuickSort();

    ob.sort(arr, 0, n - 1);

    System.out.println("sorted array");

    printArray(arr);

  }

}

******************************************************************************************
PLEASE LIKE IT RAISE YOUR THUMBS UP
IF YOU ARE HAVING ANY DOUBT FEEL FREE TO ASK IN COMMENT SECTION
******************************************************************************************