Реализовать гибридную вставку и быструю сортировку C ++ - PullRequest
Новая
       24

Реализовать гибридную вставку и быструю сортировку C ++

0 голосов
/ 08 июня 2018

Я пытаюсь реализовать гибридную вставку и быструю сортировку.Задача состоит в том, чтобы использовать быструю сортировку для больших векторов, и всякий раз, когда векторы становятся меньше определенного значения (точки пересечения), алгоритм должен переключаться на сортировку вставкой.Пока у меня есть этот код, но он не сортирует векторы, и я не знаю почему.Любая помощь будет оценена.Спасибо! 

#include <iostream>
#include "console.h"
#include "vector.h"  // for Vector
#include <cmath>
using namespace std;


/* Partition for quicksort algorithm */
int partition(Vector<int> &vec, int start, int end){
    int lh = start +1;
    int rh = end;
    int pivotVal = vec[start];

    while (true){
        while (lh<rh && vec[lh]<pivotVal) lh++;
        while (rh>lh && vec[rh]>=pivotVal) rh--;
        if (lh==rh) break;
        swap(vec[lh], vec[rh]);
    }

    if (pivotVal<vec[lh]) return start;
    swap(vec[start], vec[lh]);
    return lh;
}


/* Regular quicksort */
void quickSort(Vector<int> &vec, int start, int end){
    if(start<end){
        int pivotIndex = partition(vec, start, end);
        quickSort(vec, start, pivotIndex-1);
        quickSort(vec, pivotIndex+1, end);
    }
}


/* Insertion sort algorithm */
void insertionSort(Vector<int> &vec, int start, int end){
    int size = vec.size();
    for (int i=start; i<end; i++){
        int j=i;
        while (j>start && vec[j-1]>vec[j]){
            swap(vec[j-1], vec[j]);
            j--;
        }
    }
}



/* Hybrid quicksort & insertion sort, as soon as the part of the vector to 
   sort becomes less than the crossover value, the algorithm switches to 
   insertion sort, otherwise it 
   uses quicksort */
void hybridSort(Vector<int> &vec, int start, int end, int crossover){
    if(start < end){
        if (end-start <= crossover){
            insertionSort(vec, start, end);
        } else {
            int pivotIndex = partition(vec, start, end);
            hybridSort(vec, start, pivotIndex-1, crossover);
            hybridSort(vec, pivotIndex+1, end, crossover);
        }
    }
}



int main() {

    Vector<int> vec {9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 14, 39, 30, 83, 92, 41};
    int end = vec.size()-1;
    hybridSort(vec, 0, end, 4);
    cout << vec.toString() <<endl;

    return 0;

}

1 Ответ

0 голосов
/ 08 июня 2018

Я переписал partition: 

int partition(Vector<int>& vec, int start, int end) {
    int pivot = start;
    for(int i = start + 1; i <= end; ++i) {
        if(vec[i] < vec[pivot]) {
            swap(vec[pivot + 1], vec[i]);
            swap(vec[pivot], vec[pivot + 1]);
            ++pivot;
        }
    }
    return pivot;
}

Также есть ошибка в insertionSort.Это должно быть i <= end вместо i < end.Вот исправленная версия: 

void insertionSort(Vector<int>& vec, int start, int end) {
    for(int i = start; i <= end; i++) {
        int j = i;
        while(j > start && vec[j-1] > vec[j]) {
            swap(vec[j-1], vec[j]);
            j--;
        }
    }
}
...