Not able to find out the error while implementing QuickSort

Question

I am writing a basic QuickSort method, but I am unable to find out the errors in the code. The program is returning the same input as after going through the sorting function.Although I cross-checked my code with other internet resources, I tried to find out the error myself, and there seems to be some error in the Partition function, but I'm not able to figure out what exactly is causing the error.

Below is my code.

#include<iostream>
#include<stdio.h>
#include<vector>

using namespace std;

void swap(int n1, int n2)
{
    int temp = n1;
    n1=n2;
    n2=temp;

}



int Partition(vector<int> &A, int start, int end)
{
        int pivot = A[end];
        int Pindex = start;
        for(int i=start;i<end;i++)
        {
            if(A[i]<=pivot)
            {
                swap(A[i],A[Pindex]);
                Pindex++;
            }
        }
        swap(A[Pindex],A[end]);
        return Pindex;
}

void QuickSort(vector<int> &A, int start, int end)
{
    if(start<end)
    {
        int Pindex = Partition(A,start,end);
      //  printf("Partition Index:%d  \n",Pindex);
        QuickSort(A,start,Pindex-1);
        QuickSort(A,Pindex+1,end);
    }
}





int main()
{
    vector<int>A = {4,6,7,9,3,2,0,5};
    cout<<"Before Sorting\n";
    int length = A.size();
    for(int i=0;i<length;i++)
    {
        printf("%d",A[i]);

    }
    printf("\n");
    QuickSort(A,0,length-1);
    cout<<"After Sorting:\n";
    for(int i=0;i<length;i++)
    {
        printf("%d",A[i]);


    }

    return 0;

}

thats cos your swap function doesnt do anyting. It is simply juggling local copies of its input numbers — pm100, Dec 14 '18 at 17:24

Prajval M · Answer 1 · 2018-12-17T14:04:43.490

1

void swap(int * n1, int * n2) 
{ int temp = *n1; *n1=*n2; *n2=temp; }

swap must be reference by address and not valid value. Or the values will be not to exchanged.

Also while calling swap function call it as follows swap(&A[i] , &A[j])

edited Dec 17 '18 at 14:04

answered Dec 14 '18 at 18:19

Prajval M

2,298
11
32

score 1 · Answer 2 · answered Dec 15 '18 at 02:34

If you code that way in Java, you also hit the same problem. The root cause is that the value you compared in the swap funtion is passed into that function by value, compared with by reference. Refer to this link: C++: Argument Passing "passed by reference"

Papan · Answer 3 · 2018-12-14T18:06:54.507

Actually the problem is , you sending two integer variable in swap(int a,int b) function. This variables exchange value between them.

But you have an array which holds this integer values. you need to pass the array to swap two integer basis of their position.

You need to call swap function in following way :

void swap(vector<int> &A,int Pindex,int end){                                                  
    int temp = A[Pindex]; 
    A[Pindex]= A[end];
    A[end]=temp; 
}

Not able to find out the error while implementing QuickSort

3 Answers3