#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);
[B] if(auf_ptr<ende_ptr)[/B]
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 main