Answer to Question #190689 in Algorithms for sagun poudel

Question

Write and apply the partition procedure of Quick Sort algorithm to the following array. Show all the intermediate steps. 25 27 15 35 13 50 33 14 40 27

Answer 1

#include <iostream>
using namespace std;
size_t partition(size_t left,size_t right)
{
    return (left+right)/2;
}
void myQuickSort(double a[],size_t left,size_t right)
{
    if(left>=right){return;}
    size_t part=partition( left, right);
    cout<<"for this array:\n";
    for(size_t i=left;i<=right;i++)
    {
        cout<<a[i]<<" ";
    }cout<<"\nthe pivots will be:\n";
    cout<<a[part]<<"\n";
    double less_array[right-left+1],more_or_equal_array[right-left+1],pivots;
    size_t lenght_less_array=0,lenght_more_or_equal_array=0;
    for(size_t i=left;i<=right;i++)
    {
        if(i==part)
        {
            continue;
        }
        if(a[i]>=a[part])
        {
            more_or_equal_array[lenght_more_or_equal_array]=a[i];
            lenght_more_or_equal_array++;
            cout<<"element "<<a[i]<<"go right\n";
        }else
        {
            less_array[lenght_less_array]=a[i];
            lenght_less_array++;
            cout<<"element "<<a[i]<<"go left\n";
        }




    }
    pivots=a[part];
    for(size_t i=left;i<=right;i++)
    {
        if((i-left)<lenght_less_array)
        {
            a[i]=less_array[i-left];
        }
        if((i-left)==lenght_less_array)
        {
            a[i]=pivots;
        }
        if((i-left)>lenght_less_array)
        {
            a[i]=more_or_equal_array[i-left-1-lenght_less_array];
        }
    } cout<<"result for this array:\n";
    for(size_t i=left;i<=right;i++)
    {
        cout<<a[i]<<" ";
    }cout<<"\n";


    if(lenght_less_array)
    {
        myQuickSort(a,left,left+lenght_less_array-1);
    }
    myQuickSort(a,left+lenght_less_array+1,right);


}
int main()
{


    double a[10]={25, 27 ,15 ,35, 13, 50, 33, 14, 40, 27};
    myQuickSort(a,0,9);
    cout<<"total result\n";
    for(size_t i=0;i<=9;i++)
    {
        cout<<a[i]<<" ";
    }cout<<"\n";
    return 0;
}

for this array:

25 27 15 35 13 50 33 14 40 27

the pivots will be:

13

element 25go right

element 27go right

element 15go right

element 35go right

element 50go right

element 33go right

element 14go right

element 40go right

element 27go right

result for this array:

13 25 27 15 35 50 33 14 40 27

for this array:

25 27 15 35 50 33 14 40 27

the pivots will be:

50

element 25go left

element 27go left

element 15go left

element 35go left

element 33go left

element 14go left

element 40go left

element 27go left

result for this array:

25 27 15 35 33 14 40 27 50

for this array:

25 27 15 35 33 14 40 27

the pivots will be:

35

element 25go left

element 27go left

element 15go left

element 33go left

element 14go left

element 40go right

element 27go left

result for this array:

25 27 15 33 14 27 35 40

for this array:

25 27 15 33 14 27

the pivots will be:

15

element 25go right

element 27go right

element 33go right

element 14go left

element 27go right

result for this array:

14 15 25 27 33 27

for this array:

25 27 33 27

the pivots will be:

27

element 25go left

element 33go right

element 27go right

result for this array:

25 27 33 27

for this array:

33 27

the pivots will be:

33

element 27go left

result for this array:

27 33

total result

13 14 15 25 27 27 33 35 40 50