The lab is to develop a C++ program that will implement the Quicksort algorithm.

Question

The lab is to develop a C++ program that will implement the Quicksort algorithm.

You need to write

a) Quicksort function that will take three inputs: array A, integer variables first and last which represent first and last index of the array.

The algorithm for QuickSort is as follows

Check if first < last, then

      call the Partition function and store the value in an integer variable mid.

      Then recursively call QuickSort twice, using the following function calls.

      QuickSort(A, first, mid-1);

      QuickSort(A, mid+1, last);

b) Swap function

     Swap function takes three inputs, array A, index i and J and then swaps the two values stored in A[I] and A[J] using a temp variable.

c) call QuickSort as

   QuickSort(A, 1, N);

Explanation / Answer

Please give a Thumps Up if you like the answer

Program

#include <iostream>
using namespace std;

void quick_sort(int[],int,int);
void swap(int[],int,int);
int partition(int[],int,int);
int main()
{
    int a[50],n,i;
    cout<<"How many elements: ";
    cin>>n;
    cout<<" Enter array elements:";

    for(i=1;i<=n;i++)
        cin>>a[i];

    quick_sort(a,1,n);
    cout<<" Array after sorting:";

    for(i=1;i<=n;i++)
        cout<<a[i]<<" ";

    return 0;
}

void quick_sort(int a[],int first,int last)
{
    int mid;
    if(first<last)
    {
        mid=partition(a,first,last);
        quick_sort(a,first,mid-1);
        quick_sort(a,mid+1,last);
    }
}

int partition(int a[],int first,int last)
{
    int v,i,j,temp;
    v=a[first];
    i=first;
    j=last+1;

    do
    {
        do
            i++;

        while(a[i]<v&&i<=last);

        do
            j--;
        while(v<a[j]);

        if(i<j)
        {
            swap(a,i,j);
        }
    }while(i<j);

    a[first]=a[j];
    a[j]=v;

    return(j);
}

void swap(int a[],int i,int j)
{
    int temp;
            temp=a[i];
            a[i]=a[j];
            a[j]=temp;
}

Output

How many elements: 6

Enter array elements:18
3
95
75
6
54

Array after sorting:3 6 18 54 75 95

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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