Erreur de segmentation causant un sorting rapide récursif (pas de débordement)

Aidez-moi s’il vous plaît (ce serait très utile pour un projet d’école pour demain)

Je n’ai pas essayé d’implémenter un algorithme récursif de sorting rapide en C ++, cependant, lorsque je l’exécute, j’obtiens une erreur de segmentation à l’exécution (Windows):

#include  #include  #include  using namespace std; void getRandomList(int, int*); void outputList(int, int*); void quicksort(int, int*); int main() { cout<<"Quick Sort example, By Jack Wilkie\n"; while (true) { cout<>pnput; cin.ignore(1); ssortingngstream temp; temp <> length; if (length  100000) { cout<<"INVALID INPUT! (0 < input < 100,000)\n"; } else { cout<<"Creating random list of "<<length<<" items\n"; int *list = new int[length]; getRandomList(length, list); outputList(length, list); double start = clock(); quicksort(length, list); double stop = clock(); double time = stop-start; cout<<time<<"ms"; cin.get(); delete[] list; break; } } } void quicksort(int len, int* list) { if (len < 1) { return; } else { int low[10]; int mid[10]; lmid[0] = list[0]; int high[10]; int lens[3] = {0,1,0}; for(int i = 1; i < len; i++) { if(list[i]  list[0]) { high[lens[2]] = list[i]; lens[2]++; } else { mid[lens[1]] = list[i]; lens[1]++; } } quicksort(lens[0], low); quicksort(lens[2], high); for(int i = 0; i < len; i++) { if (i < lens[0]) { list[i] = low[i]; } else if (i < lens[0]+lens[1]) { list[i] = mid[i-lens[0]]; } else { list[i] = high[i-lens[0]-lens[1]]; } } } return; } 

Mon programme de débogage (dev c ++, presque hors d’Internet et je ne peux rien obtenir de gros) dit que l’erreur est en ligne

  lmid[0] = list[0]; 

Cependant, je ne trouve aucun problème, il a l’erreur dès qu’il appelle la fonction quicksort, je pense que le problème a quelque chose à voir avec le passage d’un tableau, et je suis à peu près sûr que la fonction n’est pas récursive et ne gonfle pas emstackr

au cas où vous en auriez besoin pour le débogage, voici les autres fonctions que j’ai utilisées

 void getRandomList(int length, int* output) { for(int i = 0; i < length; i++) { output[i] = rand() % 100; } return; } void outputList(int length, int* input) { for(int i = 0; i < length; i++) { cout<<input[i]<<" "; } cout<<"\n"; return; } 

Je ne vois nulle part la déclaration ou l’initialisation de la variable lmid. Ce serait un problème probablement.

Votre cas de base de sortie est incorrect.

Ce:

 if (len < 1) 

Devrait être ceci:

 if (len <= 1) 

Cela est très important pour arrêter la récursion infinie de votre programme. Votre faute est due au fait que vous soufflez dans votre espace de stockage variable automatique (alias la stack) et que vous en consumz de plus en plus à chaque itération jusqu’à ce que finalement ker-boom


Tri rapide sur place général

En tant que note d’implémentation d’algorithme, vous rendez ceci beaucoup plus difficile qu’il ne devrait l’être. Quicksort concerne le partitionnement, et correctement, vous ne devriez pas avoir besoin de stockage temporaire en dehors de la variable temp utilisée pour échanger des éléments. Utilisez la bibliothèque à votre avantage. Un mécanisme d'échange est prévu pour vous, à savoir std :: swap . Cela nettoie considérablement le code.

 void quicksort(int arr[], size_t len) { if (len <= 1) return; size_t pvt = 0, i; for (i=0; i 

Cela diffère de votre algorithme de manière fondamentale, et pas seulement parce que cela fonctionne:

  • Il prend le tableau comme premier paramètre, la longueur en second.
  • Il utilise arr[len-1] pour conserver la valeur de pivot, pas arr[0]
  • Il ne nécessite aucun tableau temporaire que ce soit.

Outre les valeurs de pivot choix (il doit être aléatoire, pas toujours dans un emplacement de logement spécifique), il s'agit de la méthode de balayage par balayage traditionnelle utilisée pour le sorting rapide sur place.


Modèle basé sur un iterator

Bien que vos besoins soient excessifs, l'algorithme ci-dessus peut être étendu à un modèle général basé sur un iterator et facilement implémenté à l'aide de la bibliothèque standard C ++.

 #include  #include  #include  // assumes T::operator <(const T&) exists for the iterated type. template< typename Iterator, typename Compare=std::less::value_type> > void quicksort(Iterator first, Iterator last, Compare&& cmp = Compare()) { // early exit on sortingvial list (zero or one element) typename std::iterator_traits::difference_type len = std::distance(first, last); if (len <= 1) return; // establish pivot, move it to end of sequence Iterator tail = std::prev(last,1); Iterator pvt = std::next(first, (std::rand() % len)); std::iter_swap(pvt, tail); // run through scan pvt = first; for (Iterator head = first; head != tail; ++head) { if (cmp(*head,*tail)) std::iter_swap(head, pvt++); } std::iter_swap(pvt, tail); // run through sublists. note: pvt is NOT included. quicksort(first, pvt, cmp); quicksort(++pvt, last, cmp); } 

Cela vous permet d’appeler cela sur n’importe quel conteneur de séquence prenant en charge des iterators bidirectionnels. Par exemple:

 std::vector data; // populate data with values. quicksort(data.begin(), data.end()); 

De même, il peut être utilisé sur des tableaux fixes:

 int arr[N]; // populate arr with values quicksort(std::begin(arr), std::end(arr)); // or quicksort(arr, arr + sizeof(arr)/sizeof(*arr)); 

Enfin, l'exemple de tableau fixe peut être rendu encore plus simple en utilisant un simple wrapper de tableau fixe autour de notre implémentation quicksort:

 template void quicksort(T (&arr)[N]) { quicksort(std::begin(arr), std::end(arr)); } 

ce qui nous permet alors de faire simplement ceci:

 int arr[N]; // populate arr with values quicksort(arr); 

Pas une réponse à votre question.

Il y a quelques semaines, je pratiquais avec des conteneurs et des algorithmes C ++ et j’ai décidé d’implémenter quicksort. J’attache mon code non pas parce qu’il est particulièrement efficace ou efficace, mais j’aime bien l’impression que cela m’a donné d’utiliser des algorithmes C ++ pour résoudre des problèmes spécifiques.

Peut-être que cela peut vous aider à comprendre l’algorithme et son implémentation “fonctionnelle” en C ++.

 #include #include #include #include #include #include #include #include namespace detail { template void show(Iterator first, Iterator last, Iterator pidx, int depth) { if(std::distance(first, last) <= 0) { return; } std::cout<<"tail depth: "<(std::cout, " ")); std::cout<<"] + "<<(*pidx) <<" + [ "; std::copy(std::next(pidx), last, std::ostream_iterator(std::cout, " ")); std::cout<<"]"< void quicksort(Iterator first, Iterator last, int depth=0) { if(std::distance(first, last) > 0) { auto pred = std::bind(std::less(), std::placeholders::_1, *first); std::iter_swap(first, std::prev(last)); auto pidx = std::partition(first, last, pred); std::iter_swap(pidx, std::prev(last)); depth++; show(first, last, pidx, depth); detail::quicksort(first, pidx, depth); detail::quicksort(std::next(pidx), last, depth); } } } template void show(T& data) { std::cout<<"[ "; std::copy(data.begin(), data.end(), std::ostream_iterator(std::cout, " ")); std::cout<<"]"< void quicksort(Container& data) { using T = typename Container::value_type; std::cout<<"Before sort: "; show(data); detail::quicksort(std::begin(data), std::end(data)); std::cout<<"After sort: "; show(data); } int main(int argc, char* argv[]) { std::cout<<"working with vector"< vdata = {5, 10, 0, 2, 8, 3, 7, 4, 6}; quicksort(vdata); std::cout<<"working with array"< adata = {5, 10, 0, 2, 8, 3, 7, 4, 6}; quicksort(adata); std::cout<<"working with list"< cdata = {5, 10, 0, 2, 8, 3, 7, 4, 6}; quicksort(cdata); std::cout<<"worst case performance: sort a sorted container"< with elements in [0, ..., "< ldata(N); std::iota(ldata.begin(), ldata.end(), 0); std::random_shuffle(ldata.begin(), ldata.end()); quicksort(ldata); return 0; } 

J’ai compilé sur OS X 10.7.4 en utilisant GCC 4.8.1. Échantillon échantillon:

 $ /usr/local/bin/g++ quicksort-functional.cpp -std=c++11 -Wall -Wextra $ ./a.out working with vector Before sort: [ 5 10 0 2 8 3 7 4 6 ] tail depth: 1 [ 4 3 0 2 ] + 5 + [ 10 7 6 8 ] tail depth: 2 [ 2 3 0 ] + 4 + [ ] tail depth: 3 [ 0 ] + 2 + [ 3 ] tail depth: 4 [ ] + 0 + [ ] tail depth: 4 [ ] + 3 + [ ] tail depth: 2 [ 8 7 6 ] + 10 + [ ] tail depth: 3 [ 6 7 ] + 8 + [ ] tail depth: 4 [ ] + 6 + [ 7 ] tail depth: 5 [ ] + 7 + [ ] After sort: [ 0 2 3 4 5 6 7 8 10 ] working with array Before sort: [ 5 10 0 2 8 3 7 4 6 ] tail depth: 1 [ 4 3 0 2 ] + 5 + [ 10 7 6 8 ] tail depth: 2 [ 2 3 0 ] + 4 + [ ] tail depth: 3 [ 0 ] + 2 + [ 3 ] tail depth: 4 [ ] + 0 + [ ] tail depth: 4 [ ] + 3 + [ ] tail depth: 2 [ 8 7 6 ] + 10 + [ ] tail depth: 3 [ 6 7 ] + 8 + [ ] tail depth: 4 [ ] + 6 + [ 7 ] tail depth: 5 [ ] + 7 + [ ] After sort: [ 0 2 3 4 5 6 7 8 10 ] working with list Before sort: [ 5 10 0 2 8 3 7 4 6 ] tail depth: 1 [ 4 3 0 2 ] + 5 + [ 10 7 6 8 ] tail depth: 2 [ 2 3 0 ] + 4 + [ ] tail depth: 3 [ 0 ] + 2 + [ 3 ] tail depth: 4 [ ] + 0 + [ ] tail depth: 4 [ ] + 3 + [ ] tail depth: 2 [ 8 7 6 ] + 10 + [ ] tail depth: 3 [ 6 7 ] + 8 + [ ] tail depth: 4 [ ] + 6 + [ 7 ] tail depth: 5 [ ] + 7 + [ ] After sort: [ 0 2 3 4 5 6 7 8 10 ] worst case performance: sort a sorted container Before sort: [ 0 2 3 4 5 6 7 8 10 ] tail depth: 1 [ ] + 0 + [ 2 3 4 5 6 7 8 10 ] tail depth: 2 [ ] + 2 + [ 3 4 5 6 7 8 10 ] tail depth: 3 [ ] + 3 + [ 4 5 6 7 8 10 ] tail depth: 4 [ ] + 4 + [ 5 6 7 8 10 ] tail depth: 5 [ ] + 5 + [ 6 7 8 10 ] tail depth: 6 [ ] + 6 + [ 7 8 10 ] tail depth: 7 [ ] + 7 + [ 8 10 ] tail depth: 8 [ ] + 8 + [ 10 ] tail depth: 9 [ ] + 10 + [ ] After sort: [ 0 2 3 4 5 6 7 8 10 ] test on vector with elements in [0, ..., 99] shuffled randomly Before sort: [ 95 37 56 15 50 77 61 66 8 43 90 7 25 74 1 26 38 87 13 64 57 84 6 16 17 67 35 42 55 9 59 81 2 68 58 29 76 73 99 96 33 11 34 4 86 46 39 52 97 82 10 41 53 28 49 5 80 12 71 14 91 88 24 93 45 79 62 31 19 60 22 69 94 63 51 32 44 75 98 78 30 89 47 23 83 48 54 21 70 36 20 27 0 3 72 40 85 18 65 92 ] tail depth: 1 [ 92 37 56 15 50 77 61 66 8 43 90 7 25 74 1 26 38 87 13 64 57 84 6 16 17 67 35 42 55 9 59 81 2 68 58 29 76 73 65 18 33 11 34 4 86 46 39 52 85 82 10 41 53 28 49 5 80 12 71 14 91 88 24 93 45 79 62 31 19 60 22 69 94 63 51 32 44 75 40 78 30 89 47 23 83 48 54 21 70 36 20 27 0 3 72 ] + 95 + [ 97 96 99 98 ] tail depth: 2 [ 72 37 56 15 50 77 61 66 8 43 90 7 25 74 1 26 38 87 13 64 57 84 6 16 17 67 35 42 55 9 59 81 2 68 58 29 76 73 65 18 33 11 34 4 86 46 39 52 85 82 10 41 53 28 49 5 80 12 71 14 91 88 24 3 45 79 62 31 19 60 22 69 0 63 51 32 44 75 40 78 30 89 47 23 83 48 54 21 70 36 20 27 ] + 92 + [ 93 94 ] tail depth: 3 [ 27 37 56 15 50 20 61 66 8 43 36 7 25 70 1 26 38 21 13 64 57 54 6 16 17 67 35 42 55 9 59 48 2 68 58 29 23 47 65 18 33 11 34 4 30 46 39 52 40 44 10 41 53 28 49 5 32 12 71 14 51 63 24 3 45 0 62 31 19 60 22 69 ] + 72 + [ 88 91 80 82 75 85 78 86 89 73 76 83 81 84 87 74 90 77 79 ] tail depth: 4 [ 22 19 0 15 3 20 24 14 8 12 5 7 25 10 1 26 4 21 13 11 18 23 6 16 17 2 9 ] + 27 + [ 55 35 59 48 67 68 58 29 54 47 65 57 33 64 34 38 30 46 39 52 40 44 70 41 53 28 49 36 32 43 71 66 51 63 61 50 45 56 62 31 37 60 69 42 ] tail depth: 5 [ 9 19 0 15 3 20 2 14 8 12 5 7 17 10 1 16 4 21 13 11 18 6 ] + 22 + [ 26 25 24 23 ] tail depth: 6 [ 6 4 0 1 3 7 2 5 8 ] + 9 + [ 14 20 17 10 15 16 19 21 13 11 18 12 ] tail depth: 7 [ 5 4 0 1 3 2 ] + 6 + [ 8 7 ] tail depth: 8 [ 2 4 0 1 3 ] + 5 + [ ] tail depth: 9 [ 1 0 ] + 2 + [ 3 4 ] tail depth: 10 [ 0 ] + 1 + [ ] tail depth: 11 [ ] + 0 + [ ] tail depth: 10 [ ] + 3 + [ 4 ] tail depth: 11 [ ] + 4 + [ ] tail depth: 8 [ 7 ] + 8 + [ ] tail depth: 9 [ ] + 7 + [ ] tail depth: 7 [ 12 11 13 10 ] + 14 + [ 16 19 21 17 20 18 15 ] tail depth: 8 [ 10 11 ] + 12 + [ 13 ] tail depth: 9 [ ] + 10 + [ 11 ] tail depth: 10 [ ] + 11 + [ ] tail depth: 9 [ ] + 13 + [ ] tail depth: 8 [ 15 ] + 16 + [ 21 17 20 18 19 ] tail depth: 9 [ ] + 15 + [ ] tail depth: 9 [ 19 17 20 18 ] + 21 + [ ] tail depth: 10 [ 18 17 ] + 19 + [ 20 ] tail depth: 11 [ 17 ] + 18 + [ ] tail depth: 12 [ ] + 17 + [ ] tail depth: 11 [ ] + 20 + [ ] tail depth: 6 [ 23 25 24 ] + 26 + [ ] tail depth: 7 [ ] + 23 + [ 25 24 ] tail depth: 8 [ 24 ] + 25 + [ ] tail depth: 9 [ ] + 24 + [ ] tail depth: 5 [ 42 35 37 48 31 45 50 29 54 47 51 43 33 32 34 38 30 46 39 52 40 44 36 41 53 28 49 ] + 55 + [ 64 57 71 66 65 63 61 58 68 56 62 67 59 60 69 70 ] tail depth: 6 [ 28 35 37 41 31 36 40 29 39 30 38 34 33 32 ] + 42 + [ 51 47 46 54 52 50 44 45 48 53 49 43 ] tail depth: 7 [ ] + 28 + [ 35 37 41 31 36 40 29 39 30 38 34 33 32 ] tail depth: 8 [ 32 33 34 31 30 29 ] + 35 + [ 39 36 38 41 37 40 ] tail depth: 9 [ 29 30 31 ] + 32 + [ 33 34 ] tail depth: 10 [ ] + 29 + [ 30 31 ] tail depth: 11 [ ] + 30 + [ 31 ] tail depth: 12 [ ] + 31 + [ ] tail depth: 10 [ ] + 33 + [ 34 ] tail depth: 11 [ ] + 34 + [ ] tail depth: 9 [ 37 36 38 ] + 39 + [ 40 41 ] tail depth: 10 [ 36 ] + 37 + [ 38 ] tail depth: 11 [ ] + 36 + [ ] tail depth: 11 [ ] + 38 + [ ] tail depth: 10 [ ] + 40 + [ 41 ] tail depth: 11 [ ] + 41 + [ ] tail depth: 7 [ 43 47 46 49 48 50 44 45 ] + 51 + [ 53 54 52 ] tail depth: 8 [ ] + 43 + [ 47 46 49 48 50 44 45 ] tail depth: 9 [ 45 46 44 ] + 47 + [ 50 49 48 ] tail depth: 10 [ 44 ] + 45 + [ 46 ] tail depth: 11 [ ] + 44 + [ ] tail depth: 11 [ ] + 46 + [ ] tail depth: 10 [ 48 49 ] + 50 + [ ] tail depth: 11 [ ] + 48 + [ 49 ] tail depth: 12 [ ] + 49 + [ ] tail depth: 8 [ 52 ] + 53 + [ 54 ] tail depth: 9 [ ] + 52 + [ ] tail depth: 9 [ ] + 54 + [ ] tail depth: 6 [ 60 57 59 62 56 63 61 58 ] + 64 + [ 65 66 67 71 70 69 68 ] tail depth: 7 [ 58 57 59 56 ] + 60 + [ 63 61 62 ] tail depth: 8 [ 56 57 ] + 58 + [ 59 ] tail depth: 9 [ ] + 56 + [ 57 ] tail depth: 10 [ ] + 57 + [ ] tail depth: 9 [ ] + 59 + [ ] tail depth: 8 [ 62 61 ] + 63 + [ ] tail depth: 9 [ 61 ] + 62 + [ ] tail depth: 10 [ ] + 61 + [ ] tail depth: 7 [ ] + 65 + [ 66 67 71 70 69 68 ] tail depth: 8 [ ] + 66 + [ 67 71 70 69 68 ] tail depth: 9 [ ] + 67 + [ 71 70 69 68 ] tail depth: 10 [ 68 70 69 ] + 71 + [ ] tail depth: 11 [ ] + 68 + [ 70 69 ] tail depth: 12 [ 69 ] + 70 + [ ] tail depth: 13 [ ] + 69 + [ ] tail depth: 4 [ 79 77 80 82 75 85 78 86 74 73 76 83 81 84 87 ] + 88 + [ 90 91 89 ] tail depth: 5 [ 76 77 73 74 75 78 ] + 79 + [ 86 82 80 87 83 81 84 85 ] tail depth: 6 [ 75 74 73 ] + 76 + [ 78 77 ] tail depth: 7 [ 73 74 ] + 75 + [ ] tail depth: 8 [ ] + 73 + [ 74 ] tail depth: 9 [ ] + 74 + [ ] tail depth: 7 [ 77 ] + 78 + [ ] tail depth: 8 [ ] + 77 + [ ] tail depth: 6 [ 85 82 80 84 83 81 ] + 86 + [ 87 ] tail depth: 7 [ 81 82 80 84 83 ] + 85 + [ ] tail depth: 8 [ 80 ] + 81 + [ 83 84 82 ] tail depth: 9 [ ] + 80 + [ ] tail depth: 9 [ 82 ] + 83 + [ 84 ] tail depth: 10 [ ] + 82 + [ ] tail depth: 10 [ ] + 84 + [ ] tail depth: 7 [ ] + 87 + [ ] tail depth: 5 [ 89 ] + 90 + [ 91 ] tail depth: 6 [ ] + 89 + [ ] tail depth: 6 [ ] + 91 + [ ] tail depth: 3 [ ] + 93 + [ 94 ] tail depth: 4 [ ] + 94 + [ ] tail depth: 2 [ 96 ] + 97 + [ 99 98 ] tail depth: 3 [ ] + 96 + [ ] tail depth: 3 [ 98 ] + 99 + [ ] tail depth: 4 [ ] + 98 + [ ] After sort: [ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 ]