Question

We are going to derive the average number of moves for quicksort using a somewhatunusual partitioning algorithm. We partition on the first element. Take it out. Look for theright most element that is smaller and place it in the first position (which is the newly openedposition on the left side). Look for the left most element that is larger and place it in the newlyopened position on the right side. Starting from there look for the right most element that issmaller and place it in the the newly opened position on the left side. Starting from there lookfor the left most element that is larger and place it in the newly opened position on the rightside. Continue in this fashion until the pointers cross. Finally, put the partition element intothe hole, which is its final position in the sorted array.(a) Assume that the partition element ends up in positionq.i. What is the probability that an element originally to the left (of positionq) went tothe right (of positionq)?ii. What is the expected number of elements originally to the left that go to the right?iii. What is the probability that an element originally to the right went to the left?iv. What is the expected number of elements originally to the right that go to the left?v. What is the total expected number of moves (for partition)?(b) Write a recurrence for the expected number of moves (for quicksort).(c) Simplify the recurrence, but do not solve it.

Answer 1

main.cpp:

#include <iostream>

using namespace std;

void swap(int* a, int* b)

{

int temp = *a;

*a = *b;

*b = temp;

}

int partition (int arr[], int LOW, int HIGH)

{

int i = (LOW - 1);

int pivot = arr[HIGH];

for (int j = LOW; j <= HIGH- 1; j++)

{

if (arr[j] <= pivot)

{

i++;

swap(&arr[i], &arr[j]);

}

}

swap(&arr[i + 1], &arr[HIGH]);

return (i + 1);

}

int AverageMoves (int arr[], int LOW, int HIGH)

{

int i = (LOW - 1);

int pivot = arr[HIGH];

int AvgMoves = 0;

for (int j = LOW; j <= HIGH- 1; j++)

{

if (arr[j] <= pivot)

{

i++;

swap(&arr[i], &arr[j]);

AvgMoves++;

}

}

return AvgMoves;

}

void quickSort(int arr[], int LOW, int HIGH)

{

if (LOW < HIGH)

{

int pivot = partition(arr, LOW, HIGH);

quickSort(arr, LOW, pivot - 1);

quickSort(arr, pivot + 1, HIGH);

}

}

void displayArray(int arr[], int size)

{

int i;

for (i=0; i < size; i++)

cout<<arr[i]<<"\t";

}

int main()

{

int arr[] = {6,9,8,4,3,12,23,43,51};

int n = sizeof(arr)/sizeof(arr[0]);

cout<<"Input array "<<endl;

displayArray(arr,n);

cout<<endl;

quickSort(arr, 0, n-1);

cout<<"\n";

cout<<"Array after sorted with quick sort: "<<endl << "\n";

displayArray(arr,n);

cout<<"\n";

cout<<"Average number of moves: ";

cout<<AverageMoves(arr, 0, n-1);

return 0;

}

Output:

Input array
6   9   8   4   3   12   23   43   51  

Array after sorted with quick sort:

3   4   6   8   9   12   23   43   51  
Average number of moves: 8