Search code examples
c++quicksort

Memory issue implementing quick sort


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


Solution

  • 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
    }