Directions: Improve the efficiency and running time of the quick sort algorithm.

Question

Directions: Improve the efficiency and running time of the quick sort algorithm.

// QuickSort.cpp : Defines the entry point for the console application.
// QuickSort Algorithm - Divide and conquer algorithm
// Running time - Big O (n log n)

#include "stdafx.h"
#include <iostream>
#include <time.h>
using namespace std;
//to display the array/list values
const int SIZE = 10;
const int NEWSIZE = 100000;
//display output
void output(int a[], int size) {
    for (int i = 0; i < size; i++) {
        cout << a[i] << ' ';
    }
    cout << endl;
}
//generating a random array
void generate_array(int a[], int size) {
    for (int i = 0; i < size; i++)
        a[i] = rand() % 1000 + 1;

    cout << "unsorted: ";
    output(a, size);
}
//Partition funtion:
//swap based on pivot
//pivot chosen to be left-most element
//easiest choice but not always most efficient.
int partition(int *v, int left, int right) {
    int i = left + 1;    //swap index
    int p = v[left];    //set current pivot to left-most
    for (int j = left + 1; j < right + 1; j++) {
        if (v[j] < p) {            
            //compare with current p, if less then swap
            int temp = v[j];
            v[j] = v[i];
            v[i] = temp;            
            cout << v[j] << " ";
            i++;            
        }        
        cout << endl;
        cout << v[j] << " ";        
    }
    cout << endl;
    int pos = i - 1;
    int temp = v[left];
    v[left] = v[pos];
    v[pos] = temp;    
    output(v, right+1);
    return pos;    //return new midpoint with pivot in its final position
}
//operate recursively, into smaller and smaller left-right sub lists
void quick_sort(int * v, int left, int right) {    
    if (left < right) {
        int pos = partition(v, left, right);        
        quick_sort(v, left, pos - 1);        
        quick_sort(v, pos + 1, right);        
    }
    
}
int main()
{
    clock_t t;
    double execution_time;
    t = clock();
    //const int SIZE = 10;
    int a[SIZE] = { 8, 4, 1, 5, 10, 7, 6, 2, 9, 3 };
    cout << "unsorted: ";
    output(a, SIZE);
    cout << endl;

    quick_sort(a, 0, SIZE-1);
    cout << "sorted: ";
    output(a, SIZE);
    cout << endl;
    t = clock() - t;
    execution_time = (double)t / CLOCKS_PER_SEC;
    printf("quick sort took %f seconds to execute ", execution_time);
    cout << endl;

    t = clock();
    cout << endl << endl;    
    int b[NEWSIZE];
    cout << "Generating a random array" << endl;
    generate_array(b, NEWSIZE);    
    cout << endl;
    //sorting the array using quicksort
    quick_sort(b, 0, NEWSIZE-1);
    cout << "sorted: ";
    output(b, NEWSIZE);
    cout << endl;
    t = clock() - t;
    execution_time = (double)t / CLOCKS_PER_SEC;
    printf("quick sort took %f seconds to execute ", execution_time);
    cout << endl;

    return 0;
}

Explanation / Answer

In the code, 2 things are improved. First random partition is used for selecting pivot element. And secondly, smaller part of array is sorted before the larger part.

#include "stdafx.h"
#include <iostream>
#include <time.h>
using namespace std;
//to display the array/list values
const int SIZE = 10;
const int NEWSIZE = 100000;
//display output
void output(int a[], int size) {
for (int i = 0; i < size; i++) {
cout << a[i] << ' ';
}
cout << endl;
}

//generating a random array
void generate_array(int a[], int size) {
for (int i = 0; i < size; i++)
a[i] = rand() % 1000 + 1;

cout << "unsorted: ";
output(a, size);
}

//Partition funtion:
int partition(int *v, int left, int right) {
int i = left + 1; //swap index
int p = v[left]; //set current pivot to left-most
for (int j = left + 1; j < right + 1; j++) {
if (v[j] < p) {   
//compare with current p, if less then swap
int temp = v[j];
v[j] = v[i];
v[i] = temp;   
cout << v[j] << " ";
i++;   
}   
cout << endl;
cout << v[j] << " ";   
}
cout << endl;
int pos = i - 1;
int temp = v[left];
v[left] = v[pos];
v[pos] = temp;   
output(v, right+1);
return pos; //return new midpoint with pivot in its final position
}

// use random partition function to reduce the time complexity
int rand_partition ( int *v , int left, int right) {
//chooses position of pivot randomly by using rand() function .
int random = left + rand( )%(right-left +1 ) ;

swap ( v[random] , v[left]) ; //swap pivot with 1st element.
return partition(v ,left ,right) ; //call the above partition function
}

//operate recursively, into smaller and smaller left-right sub lists
void quick_sort(int * v, int left, int right) {   
int pos;
if (left < right) {
pos = rand_partition(v, left, right);
if( pos-1eft < right-pos) //recurse in smaller part of array first
{
quick_sort(v, left, pos-1);
left = pos + 1;
}
else
{
quick_sort(v, pos+1, right);
right = pos-1;
}
}  
}

int main()
{
clock_t t;
double execution_time;
t = clock();
//const int SIZE = 10;
int a[SIZE] = { 8, 4, 1, 5, 10, 7, 6, 2, 9, 3 };
cout << "unsorted: ";
output(a, SIZE);
cout << endl;

quick_sort(a, 0, SIZE-1);
cout << "sorted: ";
output(a, SIZE);
cout << endl;
t = clock() - t;
execution_time = (double)t / CLOCKS_PER_SEC;
printf("quick sort took %f seconds to execute ", execution_time);
cout << endl;

t = clock();
cout << endl << endl;   
int b[NEWSIZE];
cout << "Generating a random array" << endl;
generate_array(b, NEWSIZE);   
cout << endl;
//sorting the array using quicksort
quick_sort(b, 0, NEWSIZE-1);
cout << "sorted: ";
output(b, NEWSIZE);
cout << endl;
t = clock() - t;
execution_time = (double)t / CLOCKS_PER_SEC;
printf("quick sort took %f seconds to execute ", execution_time);
cout << endl;

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

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