Question

data structures c++

please implement the QuickSort algorithm as a C++ function. Use it to sort a large number of integers, say at least 100000. Do a timing test on the sort. Then use the build-in sort() function in to sort the same data and time this sort. Which sort is better? Do some research to see if you can determine what algorithm the built-in sort() function uses and describe this sort if it is different than QuickSort.

Answer 1

#include<iostream>

#include<cstdlib>

#include <ctime>

#include <bits/stdc++.h>

using namespace std;

void quicksort(int *,int,int);

int partition(int *,int,int);

int main()

{  

    int arr1[100000], arr2[100000];

    int i;

  

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

    {

        int n = rand();

       

        // initialize the array with random numbers

        arr1[i] = n;

        arr2[i] = n;

    }

   

    // store the starting time

    double start = clock();

   

    // sort the array using quickort() function

    quicksort(arr1, 0, 100000 - 1);

    // store the ending time

    double end = clock();

   

    // calculate time taken

    double time_taken = ( end - start ) / double( CLOCKS_PER_SEC ) * 1000;

   

    cout << "Time taken by quicksort function : " << time_taken << endl;

       

    // store the starting time

    start = clock();

       

    // sort the function using sort() function

    sort(arr2, arr2 + 100000);

       

    // store the ending time

    end = clock();

   

    // calculate time taken

    time_taken = ( end - start ) / double( CLOCKS_PER_SEC ) * 1000;

   

    cout << "\nTime taken by inbuilt sort function : " << time_taken << endl;

   

    return 0;

}

// function to sort using quick sort

void quicksort(int *arr,int p,int r)

{

    int q;

   

    if(p<r)

    {

        // create a partition

        q = partition(arr,p,r);

       

        // sort the left subarray

        quicksort(arr,p,q-1);

       

      // sort the right subarray

        quicksort(arr,q+1,r);

    }

}

int partition(int *arr,int p,int r)

{  

    // set pivot

    int pivot = arr[r];

   

    // set the lindex of lower element

    int j, i = p - 1;

    for (j = p; j <= r - 1; j++ )

    {

        if (arr[j] <= pivot)

        {

            // increment smaller element index

            i++;

           

            // swap the contents of i and j position

            int temp=arr[i];

            arr[i]=arr[j];

            arr[j]=temp;

        }

    }

   

    int temp = arr[i + 1];

    arr[i+1] = arr[r];

    arr[r] = temp;

   

    return i + 1;

}

Sample Output