Быстрая сортировка дает ошибку сегментации

Question

Я пытался реализовать алгоритм быстрой сортировки.Вот код самой Quicksort

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); 
     }
}

Переменная pIndex - это расположение элемента, который находится в правильном положении.Я выбрал последний элемент массива в качестве основного в схеме разбиения.Следующий код должен разделить массив:

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

Функция разделения использует функцию подкачки, определенную как

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

И, конечно, есть функция test.cpp, котораяпроверяет алгоритм.

#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;
}

Функция print при первом вызове печатает несортированный массив, но выдает сообщение об ошибке:

 Segmentation fault(core is dumped). 

Я понимаю, что некоторая область памятидоступ, но я не понимаю, где лежит настоящая ошибка.Любая помощь высоко ценится.

Answer 1

Код раздела требует нескольких исправлений. Код использует 0 в тех случаях, когда вместо него следует использовать сначала. Функция подкачки конвертирует из double в int и обратно, вместо этого можно использовать std :: swap.

Для быстрой сортировки, которая сканирует оба конца массива по направлению к середине, середина обычно используется для оси, поскольку это устраняет необходимость использования проверок индекса, чтобы избежать сканирования за пределами массива, что, вероятно, является причиной код получает ошибку сегментации. Сканирование останавливается, когда индексы сканирования пересекаются. Какой индекс возвращать и что этот индекс представляет, зависит от конкретной реализации.

Пример кода для типичной схемы разбиения Hoare. Если вместо индексов используются итераторы, low-1 нельзя использовать, а функция секционирования нуждается в незначительном изменении для обработки начального сравнения с использованием [i]

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);
    }
}

Пример Hoare-подобной схемы разбиения, которая использует постинкремент и пост декремент

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 
}

Answer 2

Ваш код входит в бесконечный цикл, что приводит к ошибке переполнения стека . Псевдокод алгоритма можно найти в википедии, и правильная реализация должна выглядеть примерно так:

#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;
}