Quick sort implementation. a.Please implement the quick sort algorithm and sort
ID: 3571407 • Letter: Q
Question
Quick sort implementation.
a.Please implement the quick sort algorithm and sort all data stored in the file sort.txt. Print the sorted items to show that your program can work correctly.
b.Please analyze the complexity of the quick sort algorithm in the worst case (the selected pivot is minimum or maximum in each split step), the average case (the pivot is equally likely to end in any position of the sorted array) and the best case (the selected pivot can split the array into two equal halves in each split step).
c.Please indicate if the quick sort you implement is stable. How many auxiliary memory spaces are required during the quick sort algorithm?
Explanation / Answer
a. Here is the code for QuickSort:
#include <algorithm> // Provides swap
#include <cstdlib> // Provides EXIT_SUCCESS, size_t
#include <iostream> // Provides cout and cin
#include <fstream>
using namespace std;
// PROTOTYPES of the functions used in this test program:
void quicksort(int data[ ], size_t n);
// Precondition: data is an array with at least n components.
// Postcondition: The elements of data have been rearranged so
// that data[0] <= data[1] <= ... <= data[n-1].
void partition(int data[ ], size_t n, size_t& pivot_index);
// Precondition: n > 1, and data is an array (or subarray)
// with at least n elements.
// Postcondition: The function has selected some "pivot value"
// that occurs in data[0]..data[n-1]. The elements of data
// have then been rearranged, and the pivot index set so that:
// -- data[pivot_index] is equal to the pivot;
// -- Each item before data[pivot_index] is <= the pivot;
// -- Each item after data[pivot_index] is >= the pivot.
int main( )
{
const char BLANK = ' ';
const size_t ARRAY_SIZE = 10; // Number of elements in the array to be sorted
int data[ARRAY_SIZE]; // Array of integers to be sorted
int user_input; // Number typed by the user
size_t number_of_elements; // How much of the array is used
size_t i; // Array index
// Provide some instructions
string fileName;
cout<<"Enter the name of the file: ";
ifstream fin;
fin.open(fileName);
// Read the input numbers
number_of_elements = 0;
while(!fin.eof())
{
fin >> user_input;
data[number_of_elements] = user_input;
number_of_elements++;
}
// Sort the numbers and print the result with two blanks after each number
quicksort(data, number_of_elements);
cout << "In sorted order, your numbers are: " << endl;
for (i = 0; i < number_of_elements; i++)
cout << data[i] << BLANK << BLANK;
cout << endl;
return EXIT_SUCCESS;
}
void quicksort(int data[ ], size_t n)
// Library facilities used: cstdlib
{
size_t pivot_index; // Array index for the pivot element
size_t n1; // Number of elements before the pivot element
size_t n2; // Number of elements after the pivot element
const char BLANK = ' ';
if (n > 1)
{
// Partition the array, and set the pivot index.
partition(data, n, pivot_index);
for(int i = 0; i < n; i++)
cout << data[i] << BLANK << BLANK;
cout<<endl;
// Compute the sizes of the subarrays.
n1 = pivot_index;
n2 = n - n1 - 1;
// Recursive calls will now sort the subarrays.
quicksort(data, n1);
quicksort((data + pivot_index + 1), n2);
}
}
void partition(int data[ ], size_t n, size_t& pivot_index){
int pivot = 0;
int rb = n - 1;
int low = 0, high = n - 1;
while(low <=high)
{
while(data[pivot] >= data[low] && low <=rb)
low++;
while(data[pivot] < data[high])
high--;
if(pivot != high)
{
data[pivot] = data[pivot] + data[high];
data[high ] = data[pivot] - data[high];
data[pivot] = data[pivot] - data[high];
}
}
pivot_index = high;
}
b. In the worst case, the Quick sort takes O(n2) steps, where n is the number of elements in the file. And in both the average and best case, it takes O(nlogn) steps.
c. Quicksort is not a stable sort. The reason is, the element picked(pivot) can be placed anywhere based on the partition algorithm.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.