Quicksort in C++ mit Pointern und Segmentation Faults

[Procyon]

Tach erstmal

ich wollte mal Quicksort mit Pointern in C++ implementieren und hab' dabei ein Problem:

Das Programm bricht nach 18 Rekursionen mit einem Segmentation Fault ab, und zwar meldet mir gdb das hier:
Program received signal SIGSEGV, Segmentation fault.
quicksort (anfang_ptr=Cannot access memory at address 0x15
) at main.cpp:72
72 if(auf_ptr<ende_ptr)Hier mal der Code (zeile 72 fett):#include <iostream>
#include <cstdlib>
#include <cassert>

typedef unsigned long int sort_element_type;
typedef sort_element_type sort_array_type[32000];

sort_array_type sort_array;

/*
** quicksort
**
** sortiere das array sort_array mit dem Quicksort-Algorithmus
*/
void quicksort(sort_element_type * const anfang_ptr,sort_element_type * const ende_ptr)
{
std::cout<<"in quicksort\n";
assert(anfang_ptr>=&sort_array[0]);
assert(anfang_ptr<&sort_array[sizeof(sort_array_type)/sizeof(sort_element_type)]);

assert(ende_ptr>=&sort_array[0]);
assert(ende_ptr<&sort_array[sizeof(sort_array_type)/sizeof(sort_element_type)]);

assert(anfang_ptr<ende_ptr);

sort_element_type *auf_ptr(anfang_ptr);
sort_element_type *ab_ptr(ende_ptr);

sort_element_type *vgl_obj_ptr;

// vgl_obj_ptr auf das objekt in der mitte von anfang und ende zeigen lassen
while(auf_ptr<ab_ptr)
{
++auf_ptr;
if(auf_ptr==ab_ptr)
break;
--ab_ptr;
}
vgl_obj_ptr=auf_ptr;
auf_ptr=anfang_ptr;
ab_ptr=ende_ptr;

sort_element_type *hilf_ptr;

while(auf_ptr<=ab_ptr)
{
while((*auf_ptr)<(*vgl_obj_ptr))
{
assert(auf_ptr>=&sort_array[0]);
assert(auf_ptr<(&sort_array[sizeof(sort_array_type)/sizeof(sort_element_type)])-1);
++auf_ptr;
}
while((*ab_ptr)>(*vgl_obj_ptr))
{
assert(ab_ptr>&sort_array[0]);
assert(ab_ptr<&sort_array[sizeof(sort_array_type)/sizeof(sort_element_type)]);
--ab_ptr;
}
if(auf_ptr<=ab_ptr)
{
*hilf_ptr=*auf_ptr;
*auf_ptr=*ab_ptr;
*ab_ptr=*hilf_ptr;
assert(auf_ptr<&sort_array[(sizeof(sort_array_type)/sizeof(sort_element_type))-1]);
++auf_ptr;
assert(ab_ptr>&sort_array[0]);
--ab_ptr;
}
}
if(anfang_ptr<ab_ptr)
quicksort(anfang_ptr,ab_ptr);
if(auf_ptr<ende_ptr)
quicksort(auf_ptr,ende_ptr);
} // end function quicksort

int main()
{
std::cout<<"Quicksort\n";

// Array mit Anfangswerten füllen: Werte sind absteigend geordnet
sort_element_type * i_ptr;
unsigned long int j(sizeof(sort_array_type)/sizeof(sort_element_type));
for ( i_ptr=&sort_array[0];
i_ptr<&sort_array[sizeof(sort_array_type)/sizeof(sort_element_type)];
++i_ptr
)
*i_ptr=(--j);

quicksort(&sort_array[0],&sort_array[(sizeof(sort_array_type)/sizeof(sort_element_type))-1]);

for ( i_ptr=&sort_array[0];
i_ptr<&sort_array[sizeof(sort_array_type)/sizeof(sort_element_type)];
++i_ptr
)
std::cout<<(i_ptr-&sort_array[0])<<": "<<(*i_ptr)<<"\n";
return(EXIT_SUCCESS);
} // end function mainich hab keine Ahnung woran das liegen kann bzw. was ich falsch gemacht habe ...

Ich hab mit den asserts versucht sicherzustellen, dass die Pointer nicht aus dem Bereich des Arrays rauswandern ...

Vielleicht sieht ja einer der C++-Profis hier den Fehler ...

Danke im voraus!

[Ray]

Du verwendest hilf_ptr uninitialisiert und greifst darauf zu:
*hilf_ptr=*auf_ptr;

Du brauchst eine Hilfsvariable, keinen Pointer!
Außerdem hast Du einen falschen assert() eingefügt:

if(auf_ptr<=ab_ptr)
{
hilf=*auf_ptr;
*auf_ptr=*ab_ptr;
*ab_ptr=hilf;
// FALSCH:
// assert(auf_ptr<&sort_array[(sizeof(sort_array_type)/sizeof(sort_element_type))-1]);
++auf_ptr;
assert(ab_ptr>&sort_array[0]);
--ab_ptr;
}


Code sollte mit den Änderungen ohne böse Fehler laufen. Ob der Algo richtig ist, hab ich nicht geprüft. ;)

[Procyon]

Tach erstmal

jo richtig, das mit der hilfsvariable ... damit krieg ich ja keinen Speicherplatz für einen Integer ... *chatt*

und irgendwie muss man die implementierung sowieso noch verbessern in der richtung dass da nicht so einfach irgendwas inkrementiert wird (könnte ja überlaufen) ...

Aber danke!!!