1. Rewrite the Quicksort routine so that it now calculates the Pivot value a cou

Question

1. Rewrite the Quicksort routine so that it now calculates the Pivot value a couple of different ways. First, make sure you keep the original version. Second, create another version by using the median of three method as we described it in class. Third method that chooses the middle value to use as the pivot. You are going to compare these three methods (for the second two, once you’ve determined the pivot value, switch it to the first position in the list so that you can then proceed with the algorithm as it is outlined in your text.) Once again, use the timing routine, create a driver program which will:

• Generate a random list of 100 numbers from 1000 possible values.

• Generate a random list of 1000 numbers from 10000 possible values.

• Generate a random list of 10000 numbers from 100000 possible values.

You need to show the time outputs in the work that you submit. In other words, once you have the programs running, capture your results and include the results in what you submit. You can use screen shots or you can write the results to a file from your python code. You are to show the results for FIVE sets of data – FIVE lists of 100 random numbers, FIVE lists of 1000 random numbers, etc. Make sure that you save the original list for each iteration so that you are passing the same list to each routines. You do not need to show the list of numbers. Make sure you comment on your conclusions regarding the pivot value selection (first position versus median of three versus middle position.)

QuickSort routine here:

def quickSort(alist):
quickSortHelper(alist,0,len(alist)-1)

def quickSortHelper(alist,first,last):
if first<last:

splitpoint = partition(alist,first,last)

quickSortHelper(alist,first,splitpoint-1)
quickSortHelper(alist,splitpoint+1,last)

def partition(alist,first,last):
pivotvalue = alist[first]

leftmark = first+1
rightmark = last

done = False
while not done:

while leftmark <= rightmark and
alist[leftmark] <= pivotvalue:
leftmark = leftmark + 1

while alist[rightmark] >= pivotvalue and
rightmark >= leftmark:
rightmark = rightmark -1

if rightmark < leftmark:
done = True
else:
temp = alist[leftmark]
alist[leftmark] = alist[rightmark]
alist[rightmark] = temp

temp = alist[first]
alist[first] = alist[rightmark]
alist[rightmark] = temp

return rightmark

Explanation / Answer

All the partition function is given below, rest of the function/program remains the same.

Method 1: Original Method

int partition(int arr[],int low,int high)
{
   int pivot=arr[high];
   int i=(low-1);
  
   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);
}

Method 2: Discusses something fro the class

(No resources to that)

Method 3: Choose the middle value

int partition(int arr[],int low,int high)
{
   int pivot=arr[(low+high)/2];
   int i=(low-1);
  
   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);
}

For generating numbers in a given range:

for ( int i = 0; i < N ; i++)

{

       arr [ i ] = rand()%lim ;

}

Choose N and lim appropriately.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

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