Error de segmentación recurrente de ordenación rápida (no desbordamiento)

Por favor, ayúdeme (esto sería muy útil para un proyecto escolar que se entregará mañana)

No he estado intentando implementar un algoritmo de ordenamiento rápido recursivo en C ++, sin embargo, cuando lo ejecuto obtengo un error de segmentación en tiempo de ejecución (ventanas):

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

Mi progtwig de depuración (dev c ++, casi fuera de Internet y no puedo obtener nada importante) dice que el error está en línea

  lmid[0] = list[0]; 

sin embargo, no puedo encontrar ningún problema con él, tiene el error tan pronto como llama a la función quicksort, creo que el problema tiene algo que ver con la transmisión de una matriz, y estoy bastante seguro de que la función no es recurrente y dilata astackr

En caso de que lo necesite para la depuración, aquí están las otras funciones que utilicé.

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

No veo en ningún lugar statement o inicialización de la variable lmid. Ese sería probablemente el problema.

Su caso base de salida es incorrecto.

Esta:

 if (len < 1) 

Debería ser esto:

 if (len <= 1) 

Eso es muy importante para detener la recursión infinita de su progtwig. Su falla ocurre porque sopla a través de su espacio de almacenamiento variable automático (también conocido como la stack), consumiendo más y más de él con cada iteración hasta que finalmente se produce un boom.


General en el lugar Quicksort

Como nota de implementación de algoritmo, estás haciendo esto mucho, mucho más difícil de lo que debe ser. Quicksort es acerca de la partición, y hecho correctamente, no debería necesitar almacenamiento temporal fuera de la variable temporal utilizada para intercambiar elementos. Usa la biblioteca a tu favor. Se proporciona un mecanismo de intercambio para usted, a saber, std :: swap . Esto limpia significativamente el código.

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

Esto es diferente a su algoritmo en algunas formas fundamentales, y no solo porque funciona:

  • Toma la matriz como el primer parámetro, la longitud segundo.
  • Utiliza arr[len-1] para mantener el valor pivote, no arr[0]
  • No requiere matrices temporales en absoluto.

Aparte de los valores dynamics de elección (deben estar basados ​​en el azar, no siempre en una ubicación de ranura específica), este es el método tradicional de partición de barrido utilizado para la ordenación rápida en el lugar.


Plantilla basada en iterador

Aunque exageren sus necesidades, el algoritmo anterior se puede extender a una plantilla general basada en iteradores que se implementa fácilmente utilizando la biblioteca estándar de 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 trivial 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); } 

Esto le permite invocar esto en cualquier contenedor de secuencias que admita iteradores bidireccionales. Por ejemplo:

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

Asimismo, se puede utilizar en arreglos fijos:

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

Finalmente, el ejemplo de matriz fija se puede hacer aún más sencillo utilizando un envoltorio de plantilla de matriz fija simple alrededor de nuestra implementación de ordenamiento rápido:

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

que luego nos permite simplemente hacer esto:

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

No es una respuesta a tu pregunta.

Hace unas semanas estaba practicando con contenedores y algoritmos de C ++, y decidí implementar Quicksort. Estoy adjuntando mi código no porque sea particularmente bueno o eficiente, pero me gusta la sensación que me dio al usar algoritmos de C ++ para resolver problemas específicos.

Tal vez pueda ayudarlos a comprender el algoritmo y su implementación “funcional” utilizando 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; } 

Compilé en OS X 10.7.4 utilizando GCC 4.8.1. Ejecución de la muestra:

 $ /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 ]