I am trying to implement quick sort to sort a sequence of integers. I am getting a segmentation default with the following code:
I implemented partition and quick sort recursive calls.But for some c++ reason I am getting an access to memory or an infinite loop I cant understand why.
#include <fstream>
#include<vector>
#include<iostream>
using namespace std;
int pivotSelection(vector<int> A){
return 0;
}
int partition(vector<int> &A,int l,int r){
int i=l+1;
int p = A[l];
for(int j=0; j< A.size(); j++) {
if(A[j]<p){
swap(A[j], A[i] );
i=i+1;
}
}
swap(A[l], A[i-1]);
return i;
}
vector<int> readArray(char* file){
ifstream inFile;
vector<int> A;
inFile.open(file);
int x;
while (inFile >>x ) {
A.push_back(x);
}
return A;
}
void quickSort(vector<int> &A, int l,int r){
if(r==1) {
return ;
}
if(r>l){
int p= partition(A,l,r);
quickSort(A,l,p-1);
quickSort(A,p+1,r);
}
}
int main(){
vector<int> A;//= readArray((char*)"/home/brunoeducsantos/AlgorithmFoundation/quicksort/data.txt");
A.push_back(3);
A.push_back(5);
A.push_back(7);
A.push_back(1);
int length = A.size();
quickSort(A,0,length-1);
for(int i=0;i<length;i++) cout<<A[i]<<endl;
return 0;
};
The expected result is: 1 3 5 7
Fixes noted in comments:
int partition(vector<int> &A,int l,int r){
int i=l+1;
int p = A[l];
for(int j=i; j<=r; j++) { // fix
if(A[j]<p){
swap(A[j], A[i] );
i=i+1;
}
}
swap(A[l], A[i-1]);
return i-1; // fix
}