Quicksort
-
Hi,
ich hab einen bug in meinen quicksort algo...kann mir jemand helfen?
void quicksort(int *a, int l, int r) { int m = (l + r) / 2; int pivot = a[m]; int i = l; int j = r-1; do { while(a[i] < pivot) i++; // find left element > pivot while(a[j] > pivot) j--; // find right element < pivot // if i and j not already overlapped, we can swap if(i < j) { swap(a[i], a[j]); } } while(i < j); // sort left part if(l < j) { quicksort(a, l, j); } // sort right part if(j < r) { quicksort(a, i, r-1); } } int main() { int a[] = {3,4,8,9,2,6,1,5}; quicksort(a, 0, sizeof(a)/sizeof(int)); }
-
Und wie äußert sich der Fehler? Kannst du mal ein compilierbares Minimalbeispiel liefern? Wie ist swap definiert? Dein swap kann nämlich gar nicht funktionieren, so wie der Aufruf aussieht
-
void swap(int &a, int &b) { int temp = a; a = b; b = temp; } void quicksort(int *a, int l, int r) { int m = (l + r) / 2; int pivot = a[m]; int i = l; int j = r-1; do { while(a[i] < pivot) i++; // find left element > pivot while(a[j] > pivot) j--; // find right element < pivot // if i and j not already overlapped, we can swap if(i < j) { swap(a[i], a[j]); } } while(i < j); // sort left part if(l < j) { quicksort(a, l, j); } // sort right part if(j < r) { quicksort(a, i, r-1); } } int main() { int a[] = {3,4,8,9,2,6,1,5}; quicksort(a, 0, sizeof(a)/sizeof(int)); }
-
Was genau funktioniert denn nicht? Stürtzt das Programm ab? Ist das Ergebnis falsch? Oder was?
-
Referenzen gibt es in C nicht. Das ist (schlechtes) C++. Aber der Rest ist so C-ig, dass ich es mal hier lasse.
Und ich bin sogar so freundlich, für den Threadersteller die Frage zu beantworten, was nicht funktioniert. Bei folgendem Code (von mir auf C umgeschrieben):
#include <stdio.h> void swap(int *a, int *b) { int i = *a; *a = *b; *b = i; } void quicksort(int *a, int l, int r) { int m = (l + r) / 2; int pivot = a[m]; int i = l; int j = r-1; do { while(a[i] < pivot) i++; // find left element > pivot while(a[j] > pivot) j--; // find right element < pivot // if i and j not already overlapped, we can swap if(i < j) { swap(a+i, a+j); } } while(i < j); // sort left part if(l < j) { quicksort(a, l, j); } // sort right part if(j < r) { quicksort(a, i, r-1); } } int main() { int i; int a[] = {3,4,8,9,2,6,1,5}; quicksort(a, 0, sizeof(a)/sizeof(a[0])); for(i = 0; i < sizeof(a)/ sizeof(a[0]); ++i) printf("%d ", a[i]); putchar('\n'); }Produziert valgrind diese Ausgabe:
==22193== Memcheck, a memory error detector ==22193== Copyright (C) 2002-2011, and GNU GPL'd, by Julian Seward et al. ==22193== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info ==22193== Command: ./a.out ==22193== ==22193== Conditional jump or move depends on uninitialised value(s) ==22193== at 0x400604: quicksort (test.c:18) ==22193== by 0x400692: quicksort (test.c:36) ==22193== by 0x400692: quicksort (test.c:36) ==22193== by 0x400692: quicksort (test.c:36) ==22193== by 0x400692: quicksort (test.c:36) ==22193== by 0x400692: quicksort (test.c:36) ==22193== by 0x400673: quicksort (test.c:31) ==22193== by 0x4006EA: main (test.c:44) ==22193== Uninitialised value was created by a stack allocation ==22193== at 0x400695: main (test.c:41) ==22193== ==22193== Stack overflow in thread 1: can't grow stack to 0x7fe001ff8 ==22193== ==22193== Process terminating with default action of signal 11 (SIGSEGV) ==22193== Access not within mapped region at address 0x7FE001FF8 ==22193== at 0x40068E: quicksort (test.c:36) ==22193== If you believe this happened as a result of a stack ==22193== overflow in your program's main thread (unlikely but ==22193== possible), you can try to increase the size of the ==22193== main thread stack using the --main-stacksize= flag. ==22193== The main thread stack size used in this run was 16777216. ==22193== Stack overflow in thread 1: can't grow stack to 0x7fe001ff0 ==22193== ==22193== Process terminating with default action of signal 11 (SIGSEGV) ==22193== Access not within mapped region at address 0x7FE001FF0 ==22193== at 0x4A226CA: _vgnU_freeres (vg_preloaded.c:58) ==22193== If you believe this happened as a result of a stack ==22193== overflow in your program's main thread (unlikely but ==22193== possible), you can try to increase the size of the ==22193== main thread stack using the --main-stacksize= flag. ==22193== The main thread stack size used in this run was 16777216. ==22193== ==22193== FILE DESCRIPTORS: 3 open at exit. ==22193== Open file descriptor 2: /dev/pts/4 ==22193== <inherited from parent> ==22193== ==22193== Open file descriptor 1: /dev/pts/4 ==22193== <inherited from parent> ==22193== ==22193== Open file descriptor 0: /dev/pts/4 ==22193== <inherited from parent> ==22193== ==22193== ==22193== HEAP SUMMARY: ==22193== in use at exit: 0 bytes in 0 blocks ==22193== total heap usage: 0 allocs, 0 frees, 0 bytes allocated ==22193== ==22193== All heap blocks were freed -- no leaks are possible ==22193== ==22193== For counts of detected and suppressed errors, rerun with: -v ==22193== ERROR SUMMARY: 4 errors from 1 contexts (suppressed: 2 from 2) Segmentation faultDen Rest darf er sich zur Übung erst einmal selber denken.
-
Ich bekomms nicht compiliert meintest du sowas wie:
void swap( int *a, int *b)
-
Wer hat denn gesagt, dass das C sein soll?
-
Bashar schrieb:
Wer hat denn gesagt, dass das C sein soll?
Der Threadersteller durch seine Forenwahl.
-
Und um mal ein bisschen nützliche Hilfe zu leisten: Wenn man weder mit dem Debugger umgehen kann (was man schnellsten abstellen sollte) noch sonst einen Plan hat, wie man Fehlern auf die Spur kommt (ebenfalls ein unhaltbarer Zustand), dann hilft vielleicht mal so etwas nach den Variablendefinitionen in deiner Quicksortfunkton:
printf("l = %d r = %d pivot = %d\n", l, r, pivot);Damit sollte der Fehler nun offensichtlich sein.
-
Hi,
fehler gefunden...
kann man mein quicksort noch optimieren?
-
Herbert1 schrieb:
Hi,
fehler gefunden...
kann man mein quicksort noch optimieren?
In welcher Hinsicht? Was ist das Ziel? Wenn es um Geschwindigkeit in einem durchschnittlichen Anwendungsszenario bei gleichzeitig größtmöglicher Allgemeinheit: Nimm die Standardbibliothek statt etwas Selbstgestricktem.
-
Hi,
hab folgendes beispiel gefunden...hab noch nicht durchgeblickt was hier besser ist...!?
void quicksort(int A[],int l,int r) { if (l<r) { int pivot = partition(A,l,r,r); if (pivot-l<r-pivot) { quicksort(A,l,pivot-1); quicksort(A,pivot+1,r); } else { quicksort(A,pivot+1,r); quicksort(A,l,pivot-1); } } } int partition(int A[],int l, int r, int pivot) { int i=l-1; j=r; /*left and right pointer*/ swap(A[pivot],A[r]); /*move pivot to the right end */ pivot=r; while(i<j) { do i++; while((i<j)&&(A[i] < A[pivot])); do j--; while((j>i)&&(A[j] > A[pivot])); if (i ≥ j) swap(A[i],A[pivot]); else swap(A[i],A[j]); } return i; }
-
SeppJ schrieb:
Bashar schrieb:
Wer hat denn gesagt, dass das C sein soll?
Der Threadersteller durch seine Forenwahl.
Hier werden desöfteren Fragen zu C++-Programmen gestellt. Teilweise werden sogar Postings aus anderen Foren hierher verschoben, selbst aus dem C++-Forum, obwohl die gestellten Fragen entweder von C++ handeln oder zumindest nicht klar ist, dass es sich um C handelt. Das gab es früher häufiger, dass eine Frage zu C++ ins C-Forum verschoben wurden, bloß weil es gerade mal nur um for-Schleifen oder so ging.
Beispiel zum fragwürdigen Verschieben:
http://www.c-plusplus.net/forum/298771
Der OP hätte doch auch jederzeit eine Referenz aus dem Hut zaubern können.Beispiele für direkt im C-Forum gestellte Fragen zu C++-Programmen:
http://www.c-plusplus.net/forum/299167 (std::string, Memberfunktionen)
http://www.c-plusplus.net/forum/299073 (cout)
http://www.c-plusplus.net/forum/298825 (function-style cast)
http://www.c-plusplus.net/forum/298812 (Strukturtag = Typname ohne typedef)
