C++

Forum

 
Quicksort Wont Sort first digit?

cdd (25)
Hi,

I have been going through my code for a while now and still cant find why this quicksort program wont work.

The input im using is

4 3 2 7 4 8 1

and the output is:

7 1 2 4 4 3 8

Im not sure why but is will not sort the first digit. Any ideas?

i am using the second algorithim found on the quicksort wiki page link:

http://en.wikipedia.org/wiki/Quicksort

here is the code:

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
 
//#include"QuicksortBetter.h"
#include<iostream>
#include<vector>


using namespace std;

/////////Prototypes/////////////
void SpitVec(vector<char> Input);
int FindPivot(vector<char> List);
int PartionArray(vector<char>& List,int left, int right, int PIndex);
void quicksort(vector<char>& Input,int left,int right);
void Swap(vector<char>& List,char a, char b);
////////////////////////////////


int FindPivot(vector<char> List) {

     return 0;

}

int PartionArray(vector<char>& List,int left, int right, int PIndex) {

   char PivotValue = List[PIndex];

   Swap(List,right,PIndex);
      
    int StoreIndex = left;

    for(int i=left; i < right; i++) {
        if(List[i] <= PivotValue) {

            Swap(List,StoreIndex,i);
	    
            StoreIndex++;

        }

    }
    
    Swap(List,right, StoreIndex);

    return StoreIndex;
}

void Swap(vector<char>& List,char a, char b){
  
  char temp = List[a];
  List[a] = List[b];
  List[b] = temp;
  
}

void quicksort(vector<char>& List,int left,int right) {

    if(left<right) {

        int PivotIndex = FindPivot(List);
	
	//int PivotIndex = 0;
	
        int PivotNewIndex = PartionArray(List,left,right,PivotIndex);

        quicksort(List,left,PivotNewIndex-1);
	
        quicksort(List,PivotNewIndex+1,right);

    }


}


void SpitVec(vector<char> Input) {

    for(int i=0; i<Input.size(); i++) {

        cout << Input[i] << " ";

    }
    cout << endl;
}



int main() {

    vector<char> TestVec;
    char temp;
    
//    while(temp != 'n'){
//      
//      cin.get(temp);
//      
//      TestVec.push_back(temp);
//      
//   }

     TestVec.push_back('4');
      TestVec.push_back('3');
       TestVec.push_back('2');
        TestVec.push_back('7');
	 TestVec.push_back('4');
	  TestVec.push_back('8');
	  TestVec.push_back('1');
	   
    
    SpitVec(TestVec);

    quicksort(TestVec,0,TestVec.size()-1);

    SpitVec(TestVec);

    return 0;
}
Last edited on
shacktar (1187)
int PivotIndex = left;//FindPivot(List);

You're always grabbing the pivot at position zero. This means that you're often grabbing the pivot from the incorrect part of the array (should be between left and right, inclusive).
Last edited on
Topic archived. No new replies allowed.