C++

Forum

 
 
What does this line mean in Quick sort?

Leo Mingo (6)
I'm so confused at the partition() function, this code is guerranted to work


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 
#include <iostream>
#include <vector>

using namespace std;

void quickSort(vector<int>&,int,int);

int partition(vector<int>&, int,int);

int main()
{
    vector<int> A = {6,10,13,5,8,3,2,25,4,11};
    int p=0;
    int q=10;

    cout<<"======Original======="<<endl;
    for(auto e: A)
        cout<< e <<" ";
    cout<< endl;    

    quickSort(A,p,q);

    cout<<"======Sorted======="<<endl;
    for(auto e: A)
        cout<< e <<" ";
    cout<< endl;   
}


void quickSort(vector<int>& A, int p,int q)
{
    int r;
    if(p<q)
    {
        r=partition(A, p,q);
        quickSort(A,p,r);  
        quickSort(A,r+1,q);
    }
}


int partition(vector<int>& A, int p,int q)
{
    int x= A[p];
    int i=p;
    int j;

    for(j=p+1; j<q; j++) 
    {
        if(A[j]<=x)
        {
            i=i+1;          //Im confused here, i = p = j - 1; so i+=1 equals j
            swap(A[i],A[j]);   //then why swap? they should be the same!
        }

    }

    swap(A[i],A[p]);
    return i;
}


Any help would be appreciated, thanks:)
Duthomhas (13119)
You are ignoring the fact that it is in a loop: j gets incremented repeatedly, where i only gets incremented if a swap is needed.

Try tracing through the algorithm to see what happens with your example array, where p=0 and q=10.
Leo Mingo (6)
Oh silly me your right! Thanks :)
Topic archived. No new replies allowed.