Algorithms and Data Structures Lab 5

Description

Notes:

• Implement the algorithm and analyze the results using the give input files

• Deliverables: Report.pdf file and your code file (please do not send a zip file. If you have more than one class in your code, then submit each file separately through Canvas.)

• Homework report must follow the guidelines provided in the sample report uploaded in Canvas

Objectives:

• Implement basic quick sort algorithm

• Implement quick sort using median of 3 partitioning

• Compare the performance of insertion sort, merge sort, heap sort, and quick sort.

Problems

1. Implement a method to sort a given array using the basic quicksort algorithm. Use the algorithm from the textbook (see page 2)

2. Write a driver program to test the quicksort algorithm for the file uploaded in the canvas.

3. Compare the performance of the quicksort algorithm with 3 cases of input files: sorted, reversed sorted, and random. These files are provided in Canvas in the Quicksort Input Files folder.

4. Use the median of 3 partitioning algorithm (given in the next page) to implement quick sort. This algorithm chooses the pivot element as the median of the 3 elements namely: A[p], A[r], and A[(p+r)/2].

5. Compare the performance of the quicksort using median of 3 partitioning with the basic quicksort algorithm using the input files located on Canvas in Quicksort Input Files folder.

6. Compare the execution time of quicksort with the execution time of insertion sort, merge sort, heap sort. Make sure you use the same array to compare the performance. Use a table or plot to summarize the results and document your observations and analysis in the report. You can use the input files ranging from 100 to 500,000 or the input files ranging from 16 to 8192.

Submission:

• You are required to submit a written report (.pdf) and your project file (.zip) to the Canvas

• Homework report must follow the guidelines provided in the sample report uploaded in Canvas. Please include the screenshot of your code and outputs of your code at the end of your report.

• Do not forget to submit Independent Completion Form

• When you create the code to read the file use relative path instead of absolute path

DATA

16,32,64,128,256,512,1024,2048,4096,8192, random, reverseSorted, sorted