Функция быстрой сортировки C ++ 1 параметр - вектор

Question

Мне нужна помощь в реализации алгоритма Quicksort в C ++.Я ограничен передачей только одного параметра, вектора.У меня есть этот код, но он не работает, потому что он говорит, что есть ошибка с функцией копирования.Пожалуйста, помогите мне исправить это.Спасибо.

template <class T>
vector<T> quickSort(vector<T> lst)
{
    double i = 0;
    double j = lst.size() - 2;
    double temp;
    int pivotIndex = lst.size() - 1;
    double pivot = lst[pivotIndex];

    if (lst.size() <= 1)
    {
        return lst;
    }

    while (i <= j)
    {
        while (lst[i] < pivot)
        {
            i++;
        }
        while (lst[j] > pivot)
            j--;

        if (i <= j)
        {
            temp = lst[i];
            lst[i] = lst[j];
            lst[j] = temp;
            i++;
            j--;
        }
    }

    lst[pivotIndex] = lst[i];
    lst[i] = pivot;
    pivotIndex = i;

    if (lst.size() <= 2)
        return lst;

    vector<T> left_vec, right_vec;

    vector<double>::iterator pivotIter = lst.begin() + pivotIndex;
    copy(lst.begin(), pivotIter, back_inserter(left_vec));
    copy(pivotIter + 1, lst.end(), back_inserter(right_vec));

    if (left_vec.size() > 0)
    {
        quickSort(left_vec);
        copy(left_vec.begin(), left_vec.end(), lst.begin());
    }

    if (right_vec.size() > 0)
    {
        quickSort(right_vec);
        copy(right_vec.begin(), right_vec.end(), pivotIter + 1);
    }

    return lst;
}

Answer 1

Есть несколько вещей, которые не так с вашей реализацией.Во-первых, vector<T>::iterator является зависимым.Итак, используйте typename до этого.См. c ++ зависимых .Далее, ваши векторные индексы должны быть целыми числами (i and j), и вы можете использовать аргумент шаблона T вместо double для temp и pivot, так как я считаю, что вы намеревались сделать его универсальным.

Наконец, выполняя быструю сортировку влево и вправо, перезаписать вас left_vec и right_vec.Хотя я предпочитаю передавать по ссылке.

Кроме того, выполняемая вами операция копирования эффективно увеличивает временную сложность быстрой сортировки.Поскольку вам разрешено передавать только один параметр, перепроверьте свою формулировку проблемы, можете ли вы использовать какие-либо глобальные переменные или передать struct с векторными, низкими и высокими индексами.

Исправленная реализация.

#include <stdio.h>
#include <vector>
#include <iostream>

// should be avoided in general.
using namespace std;

template <class T>
vector<T> quickSort(vector<T> lst)
{
    int i = 0;
    int j = lst.size() - 2;
    T temp;
    int pivotIndex = lst.size() - 1;
    T pivot = lst[pivotIndex];

    if (lst.size() <= 1)
    {
        return lst;
    }

    while (i <= j)
    {
        while (lst[i] < pivot)
        {
            i++;
        }
        while (lst[j] > pivot)
            j--;

        if (i <= j)
        {
            temp = lst[i];
            lst[i] = lst[j];
            lst[j] = temp;
            i++;
            j--;
        }
    }

    lst[pivotIndex] = lst[i];
    lst[i] = pivot;
    pivotIndex = i;

    if (lst.size() <= 2)
        return lst;

    vector<T> left_vec, right_vec;

    typename vector<T>::iterator pivotIter = lst.begin() + pivotIndex;
    copy(lst.begin(), pivotIter, back_inserter(left_vec));
    copy(pivotIter + 1, lst.end(), back_inserter(right_vec));

    if (left_vec.size() > 0)
    {
        left_vec = quickSort(left_vec);
        copy(left_vec.begin(), left_vec.end(), lst.begin());
    }

    if (right_vec.size() > 0)
    {
        right_vec = quickSort(right_vec);
        copy(right_vec.begin(), right_vec.end(), pivotIter + 1);
    }

    return lst;
}

int main()
{
    vector<int> a{11, 8, 30, 21, 1, 5, 2};

    vector<int> res = quickSort(a);

    for(int  i = 0; i < res.size(); i++)
        cout<<res[i]<<" ";

    cout<<endl;

    return 0;
}