Quick-Sort

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Quick-Sort

    Hallo,
    Agnahim fragte mich neulich nach einem guten sortieralgorythmus. da ich über sortieralgorythmen erst vor wenigen wochen eine klausur geschrieben habe und mich auf dem gebiet nun ein bischen auskenne, habe ich mich für den quicksort entschieden. ich kenne ihn aus java, und dachte das es ziemlich einfach währe ihn zu "konvertieren", dem ist aber leider nicht so.
    hier erstmal die 3 scripte die dazu gebraucht werden:

    GML-Quellcode

    1. // scr_quick
    2. a = argument0;
    3. anfang = argument1;
    4. ende = argument2;
    6. var p, k;
    8. if ( anfang >= ende ) {
    9. // mach nix mehr
    10. } else {
    12. p = a[floor((anfang+ende)/2)];
    13. k = scr_partition(a,anfang,ende,p);
    15. scr_quick(a,anfang,k);
    16. scr_quick(a,k+1,ende);
    17. }
    Alles anzeigen



    GML-Quellcode

    1. // scr_partition
    2. a = argument0;
    3. l = argument1;
    4. r = argument2;
    5. p = argument3;
    7. while( l < r ){
    8. while( a[l] < p ) {
    9. l+=1;
    10. }
    11. while( a[r] > p ) {
    12. r-=1;
    13. }
    14. if ( l < r ) {
    15. scr_tausch(l,r,a);
    16. l+=1;
    17. r-=1;
    18. }
    19. }
    20. if ( a[r] > p ) {
    21. return (r-1);
    22. } else {
    23. return (r);
    24. }
    Alles anzeigen



    GML-Quellcode

    1. // scr_tausch
    2. anfang = argument0;
    3. ende = argument1;
    4. a = argument2;
    6. var temp1, temp2;
    8. temp1 = a[anfang];
    9. temp2 = a[ende];
    11. a[anfang] = temp2;
    12. a[ende] = temp1;
    Alles anzeigen


    und das objekt mit dem ich die sache teste:

    GML-Quellcode

    1. //create:
    2. for(i=0;i<9;i+=1) {
    3. a[i] = floor(random(10));
    4. b[i] = a[i];
    5. }
    6. // temp=0;
    8. scr_quick(a[],0,8);
    10. //draw:
    11. for(i=0;i<9;i+=1) {
    12. draw_text(32,16+i*32,b[i]);
    13. draw_text(128,16+i*32,a[i]);
    14. }
    Alles anzeigen
    leider wird der array nicht korrekt sortiert, ich vermute das die arrayübergabe nicht so einfach ist wie in java.

    irgentwelche vorschläge?
    :) Nobody is perfect (-:

    "Dummköpfe sind Denkerköpfen weit überlegen. Zahlenmäßig." Ernst Ferstl

  • Also an der Übergabe von Arrays hab ich mir auch schon die Zähne ausgeschlagen. GM kann nur Strings und Zahlen als Argumente nehmen, bei Arrays wird der erste Inhalt als Wert übertragen.
    Du musst deshalb den Arraynamen als String übertragen und mit dem Funktionen für Arrays arbeiten, nur so kann man Arrays Skriptübergreifend wirklich benutzen.
    "Die Erde ist ein Irrenhaus. Dabei könnte das bis heute erreichte Wissen der Menschheit aus ihr ein Paradies machen. Dafür müsste die weltweite Gesellschaft allerdings zur Vernunft kommen."
    - Joseph Weizenbaum

  • RE: Quick-Sort

    Original von Nobody-86

    GML-Quellcode

    1. // scr_quick
    2. a = argument0;
    3. anfang = argument1;
    4. ende = argument2;
    6. var p, k;
    8. if ( anfang >= ende ) {
    9. // mach nix mehr
    10. } else {
    12. p = variable_local_array_get(a, floor((anfang+ende)/2));
    13. k = scr_partition(a,anfang,ende,p);
    15. scr_quick(a,anfang,k);
    16. scr_quick(a,k+1,ende);
    17. }
    Alles anzeigen



    GML-Quellcode

    1. // scr_partition
    2. a = argument0;
    3. l = argument1;
    4. r = argument2;
    5. p = argument3;
    7. while( l < r ){
    8. while( variable_local_array_get(a, l) < p ) {
    9. l+=1;
    10. }
    11. while( variable_local_array_get(a, r) > p ) {
    12. r-=1;
    13. }
    14. if ( l < r ) {
    15. scr_tausch(l,r,a);
    16. l+=1;
    17. r-=1;
    18. }
    19. }
    20. if ( variable_local_array_get(a, r) > p ) {
    21. return (r-1);
    22. } else {
    23. return (r);
    24. }
    Alles anzeigen



    GML-Quellcode

    1. // scr_tausch
    2. anfang = argument0;
    3. ende = argument1;
    4. a = argument2;
    6. var temp1, temp2;
    8. temp1 = variable_local_array_get(a, anfang);
    10. variable_local_array_set(a, anfang, variable_local_array_get(a, ende));
    11. variable_local_array_set(a, ende, temp1);
    Alles anzeigen


    und das objekt mit dem ich die sache teste:

    GML-Quellcode

    1. //create:
    2. for(i=0;i<9;i+=1) {
    3. a[i] = floor(random(10));
    4. b[i] = a[i];
    5. }
    6. // temp=0;
    8. scr_quick("a",0,8); //MUSS als string übergeben werden
    10. //draw:
    11. for(i=0;i<9;i+=1) {
    12. draw_text(32,16+i*32,b[i]);
    13. draw_text(128,16+i*32,a[i]);
    14. }
    Alles anzeigen

  • Ich könnte noch die Datenstruckturen empfehlen. Das macht es gegenüber arrays wesentlich leichter die Daten zu verwalten.

    GML-Quellcode

    1. ds_list_sort(...);


    Damit wird dann die Liste sortiert.
    In der Anleitung steht auch, dass Listen schneller sind als Arrays. Wenn also arrays nicht unbedingt erforderlich sind wird ich diese Datenstrucktur nehmen.

    gamemaker.nl/doc/html/411_03_lists.html

  • Ich hab die quicksort routine schon in einem meiner projekte benutzt, und habe das array problem gelöst, indem ich nicht das array übergeben habe, sonder den namen des arrays einfach angeben haben ohne es zu übergeben.
    das heisst, wenn ich im object das array a[] deklariere, arbeite ich einfach mit a[] in der quicksort routine
    hier die datei:
    yourfileupload.com/file.php?fi…02147060160f3c939bd72f135

    hoffe es hilft.
    Zitat während der Programmierarbeit: "Ach das geht schon" ;
    "Moment, das hab ich gleich" "Ich weiss wo der Fehler liegt....."
    "lol"