Код работает хорошо для маленьких num_items
, но переполняет стек для num_items = 1000
,
Я думаю, что 1000 — это довольно небольшое число, поэтому должен быть способ довести эту работу до гораздо больших чисел. Что я могу сделать, чтобы он выдержал более рекурсивные вызовы?
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <ctime>
void printv(std::vector<int>& v) {
for (int i=0; i<v.size(); i++) std::cout << v[i] << " ";
std::cout << std::endl;
}
void quicksort(std::vector<int>& v, int begin, int end) {
if (((end - begin) <= 1) ||
(begin < 0) ||
(end > (v.size() - 1))) return;
int pivot = v[std::rand() % v.size()];
int x = 0;
int y = v.size() -1;
while(x < y) {
int changed = 0;
if(v[x] <= pivot) {
x++;
changed = 1;
}
if (v[y] > pivot) {
y--;
changed = 1;
}
if (!changed){
std::swap(v[x], v[y]);
x++;
y--;
}
}
if (x == y) y++;
if (x > y) std::swap(x, y);
quicksort(v, begin, x);
quicksort(v, y, end);
}
int ran() {
return std::rand() % 100;
}
int main() {
std::srand(std::time(0));
int num_items = 1000;
std::vector<int> v (num_items);
std::generate_n(v.begin(), num_items, ran);
printv(v);
quicksort(v, 0, v.size()-1);
printv(v);
}
Общие комментарии о коде также приветствуются.
Застрял в [0,4]
:
#1 0x0000000000400b4c in quicksort (
v=std::vector of length 1000, capacity 1000 = {...}, begin=0, end=4)
at quicksort.cpp:14
#2 0x0000000000400cc1 in quicksort (
v=std::vector of length 1000, capacity 1000 = {...}, begin=0, end=4)
at quicksort.cpp:43
#3 0x0000000000400cc1 in quicksort (
v=std::vector of length 1000, capacity 1000 = {...}, begin=0, end=4)
at quicksort.cpp:43
#4 0x0000000000400cc1 in quicksort (
v=std::vector of length 1000, capacity 1000 = {...}, begin=0, end=4)
at quicksort.cpp:43
#5 0x0000000000400cc1 in quicksort (
v=std::vector of length 1000, capacity 1000 = {...}, begin=0, end=4)
at quicksort.cpp:43
#6 0x0000000000400cc1 in quicksort (
v=std::vector of length 1000, capacity 1000 = {...}, begin=0, end=4)
at quicksort.cpp:43
#7 0x0000000000400cc1 in quicksort (
v=std::vector of length 1000, capacity 1000 = {...}, begin=0, end=4)
at quicksort.cpp:43
int pivot = v[std::rand() % v.size()];
int x = 0;
int y = v.size() -1;
Вы явно проходите begin
а также end
позиции, и все же вы выбираете элемент поворота из полного списка. Это не звучит правильно. Вы должны выбрать элемент поворота между begin
а также end
, Также, x
должен начинаться с begin
, а также y
должен начинаться с end
, В противном случае вы всегда обрабатываете полный список на каждом рекурсивном шаге, что объясняет бесконечную рекурсию, которую вы испытываете.
Других решений пока нет …