As we saw, the randomized version of Quicksort is a wonderfully efficient and pr

Question

As we saw, the randomized version of Quicksort is a wonderfully efficient and practical sorting algorithm. Indeed the expected number of comparisons it performs is within a small constant factor of best possible (although we've not yet seen the proof of the lower bound on the complexity of randomized sorting algorithms). Nonetheless, in this exercise we'll see an algorithm that is even a bit better. Quickersort works like this: Pick three out of the n inputs, uniformly but without repetition. Determine the median of the three elements, then use it as the pivot. I.e., compare all elements against the pivot, then recursively run Quickersort on the two resulting sets of inputs. Performing an exact time analysis of the algorithm is a bit complicated but a "continuum limit" is not too bad and that's what you are to do in this exercise. (a) Letting xn denote the rank of the pivot, show that in the limit of large n, x is distributed according to the probability density 6x(1 - x) on [0, 1]. That is to say, for all 0 lessthanorequalto t lessthanorequalto 1, Pr[x

Explanation / Answer

import java.util.Scanner;

/** Class QuickSort **/
public class QuickSort
{
/** Quick Sort function **/
public static void sort(int[] arr)
{
quickSort(arr, 0, arr.length - 1);
}
/** Quick sort function **/
public static void quickSort(int arr[], int low, int high)
{
int i = low, j = high;
int temp;
int pivot = arr[(low + high) / 2];

/** partition **/
while (i <= j)
{
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j)
{
/** swap **/
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;

i++;
j--;
}
}

/** recursively sort lower half **/
if (low < j)
quickSort(arr, low, j);
/** recursively sort upper half **/
if (i < high)
quickSort(arr, i, high);
}
/** Main method **/
public static void main(String[] args)
{
Scanner scan = new Scanner( System.in );
System.out.println("Quick Sort Test ");
int n, i;
/** Accept number of elements **/
System.out.println("Enter number of integer elements");
n = scan.nextInt();
/** Create array of n elements **/
int arr[] = new int[ n ];
/** Accept elements **/
System.out.println(" Enter "+ n +" integer elements");
for (i = 0; i < n; i++)
arr[i] = scan.nextInt();
/** Call method sort **/
sort(arr);
/** Print sorted Array **/
System.out.println(" Elements after sorting ");
for (i = 0; i < n; i++)
System.out.print(arr[i]+" ");
System.out.println();
}
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.