Quicksort gives segmentation fault

Question

I tried to implement the Quicksort algorithm. Here is the code for the Quicksort itself

void quicksortlast(double* a, int first, int last)
{
     if(first<last)
     {
        int pIndex=partition(a, first, last);
        quicksortlast(a, first, pIndex-1);
        quicksortlast(a, pIndex+1, last); 
     }
}

The pIndex variable is the location of the element which is at the right position. I choose the last array element as pivot in the partitioning scheme. The following code is supposed to partition the array:

 int partition(double* a, int first, int last)
 {
     int pivot=last;
     int i=0;
     int j=last-1;
     while(i<j && i<=last && j>=0)
     {
        while(a[i++]<a[pivot])
        {
            if(i>last)
                break;
        }
        while(a[j--]>a[pivot])
        {
            if(j<0)
                break;
        }
        if(i<j && i<=last && j>=0)
        {
            swap(a,i,j);
            i++;
            j--;
        }
    }
    swap(a,j,pivot);
    return j;   
 }

The partition function uses the swap function defined as

void swap(double* a, int left, int right)
{
    int temp=a[left];
    a[left]=a[right];
    a[right]=temp;
    return;
}

And, of course, there is the test.cpp function that tests the algo.

#include <iostream>
#include "qsort.h"
using namespace std;

int main()
{
    int len;
    cin>>len;
    double* a= new double[len];
    for(int i=0;i<len;i++)
        cin>>a[i];
    cout<<"Unsorted array"<<endl;
    print(a,len);
    quicksortlast(a, 0, len-1);
    cout<<"printed array"<<endl;
    print(a, len);
   return 0;
}

The print function on its first call prints the unsorted array but the it gives me error an message :

 Segmentation fault(core is dumped).

I understand, that some memory location is accessed, but I do not understand where the actual mistake lies. Any help is highly appreciated.

Briefly looking at it you might want a part of the condition to be `i < last` or make sure that `last` is exclusive. — Thomas Lang, Apr 02 '19 at 09:01
In `partition`, you're partitioning from `0` to `last`, while it should be from `first` to `last`. (I suspect that you have a non-terminating recursion.) — molbdnilo, Apr 02 '19 at 09:04

score 0 · Answer 1 · answered Apr 02 '19 at 09:21

You're code goes into a infinite loop which result in a stack overflow error. The pseudo code of the algorithm can be found on wikipedia and the right implementation should be something like that :

#include <stdio.h>

// Example program
#include <iostream>
#include <string>

void swap(double* a, int left, int right)
{
    int temp = a[left];
    a[left] = a[right];
    a[right] = temp;
    return;
}
int partition(double* a, int first, int last)
{
    int pivot = last;
    int i = 0;
    for (int j = 0; j < last - 1; j++) {
        if (a[j] < pivot) {
            swap(a, i, j);
            i++;
        }
    }
    swap(a, i, last);
    return i;
}

void quicksortlast(double* a, int first, int last)
{
    if (first < last)
    {
        int pIndex = partition(a, first, last);
        quicksortlast(a, first, pIndex - 1);
        quicksortlast(a, pIndex + 1, last);
    }
}

using namespace std;
int main()
{
    int len;
    cin >> len;
    double* a = new double[len];
    for (int i = 0; i < len; i++)
        cin >> a[i];
    quicksortlast(a, 0, len - 1);
    return 0;
}

Shouldn't that be `double pivot = a[last]` and `for (int j = 0; j < last; j++)` or `for (int j = 0; j <= last-1; j++)` ? — rcgldr, Apr 02 '19 at 19:08

rcgldr · Answer 2 · 2019-04-04T15:57:17.287

The partition code needs several fixes. The code is using 0 in cases where it should be using first instead. The swap function is converting from double to int and back, and std::swap can be used instead.

For a quicksort that scans from both ends of an array towards the middle, the middle is normally used for the pivot, since this eliminates having to use index checks to avoid scanning beyond the ends of the array, which is probably the reason the code is getting a segmentation fault. The scanning stops when the scanning indexes cross each other. Which index to return and what that index represents depends on the specific implementation.

Example code for typical Hoare partition scheme. If using iterators instead of indexes, low-1 can't be used and the partition function needs a minor change to handle the initial compare using a[i] < pivot instead of a[++i] < pivot. High+1 isn't an issue because that is the same as the "end" iterator.

int Partition(double a[], int low, int high)
{
    double pivot = a[low+(high-low)/2];
    int i = low - 1;
    int j = high + 1;
    while(1)
    {
        while(a[++i] < pivot);
        while(a[--j] > pivot);
        if(i >= j)
            return j;
        std::swap(a[i], a[j]);
    }
}

void QuickSort(double a[], int low, int high)
{
    if (low < high)
    {
        int index = Partition(a, low, high);
        QuickSort(a, low, index);             // not index - 1 for Hoare
        QuickSort(a, index + 1, high);
    }
}

Example Hoare like partition scheme which uses post increment and post decrement

int partition(double a[], int first, int last)
{
    double pivot = a[first+(last-first)/2]; // use middle for pivot
    while(first <= last) {
        while (a[first] < pivot)
            first++;
        while (a[last] > pivot)
            last--;
        if(first > last)
            break;
        std::swap(a[first],a[last]);
        first++;
        last--;
    }
    return first;       // index to 1st element of right part
}

void quicksort(double a[], int first, int last)
{
     if(first >= last)          // style change
        return;
    int index=partition(a, first, last);
    // index to 1st element of right part
    quicksort(a, first, index-1); 
    quicksort(a, index, last);  // not index+1 for this implementation 
}

Thanks, I am trying to understand, why the Hoare scheme does not work this way — olzha bala, Apr 05 '19 at 14:03
@olzhabala - I'm not sure what you mean by "why the Hoare scheme does not work this way". "What way" are you referring to? If you mean why the first or last values are not used for pivot, note that Hoare normally includes the pivot in either the left or right part after a partition, and if the data was already in order, then results in a 0,n or a n,0 size split, it makes no progress. The algorithm can be modified to work like Lomuto scheme, which excludes the pivot from recursive calls, but this could end up making it slower. — rcgldr, Apr 05 '19 at 19:47

Quicksort gives segmentation fault

2 Answers2