Sortieren

[HeAdSh0t]

Hallo!

Ich brauche einen möglichst schnellen Sortieralgorithmus/-funktion für max. 2000 Elementen (als Array gespeichert) der möglichst wenig speicher in anspruch nimmt.
Ich hab da mal was von einem quick-sort gehört, der recht schnell sein soll, aber wie viel speicher nimmt dieser in anspruch (im vergleich zu anderen algorithmen wie bubble-sort, selection-sort, ...)
Gibt es noch andere?

Danke!

[DarthZiu]

http://www.wh-og.hs-niederrhein.de/~docx/docs/studium/sortieralgorithmen/

Ganz einfach gefunden bei http://www.google.de

[hohesC]

Vielleicht hilft dir das der direkte vergleich beim Zahlensortieren.
Bubble- gegen Quicksort.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

#define SIZE 20000 //Anzahl der zu sortierenden Zahlen

int rnd();

void seedrnd(void);

void main()
{
  unsigned long int zahl[SIZE],arr[SIZE];

  int i,j,a,s,x,y,z;

  clock_t start_time, end_time,start_time_1, end_time_1;

  seedrnd();

  for(x=0;x<=(SIZE-1);x++)
  {
    zahl[x]=rnd();
    arr[x]=zahl[x];
  }

  start_time = clock();

  for(x=0;x<=(SIZE-1);x++)      //Anfang Bubblesort
  {                    
    for(y=0;y<=(SIZE-1);y++)
    {
      if(zahl[x]>zahl[y])
      {
        z=zahl[y];
        zahl[y]=zahl[x];
        zahl[x]=z;
      }
    }
  }                        //Ende Bubblesort
  end_time = clock();

  start_time_1 = clock();

  for( j=0; j<=(SIZE-1); j++ )    //Anfang Quicksort
  {
    a = arr[j];
    i = j - 1;
  while( i>0 && arr[i]>a )
  {
    arr[i+1] = arr[i];
    i--;
  }
    arr[i+1] = a;
  }                            //Ende Quicksort
  end_time_1 = clock();

  printf("Bubblesort: %lu sek.\n",(end_time - start_time) / CLOCKS_PER_SEC);
  printf("Quicksort: %lu sek.\n",(end_time_1 - start_time_1) / CLOCKS_PER_SEC);
  printf("Fuer %i Zufallszahlen.\nBeide Sortier-Algorithmen bekamen genau die gleichen Zahlen",SIZE);
  getchar();	
}

int rnd()
{
  int r;
  r = rand();
  return(r);
}

void seedrnd(void)
{
  srand((unsigned)time(NULL));
}

mfg hohesC

[hohesC]

DarthZiu schrieb:

http://www.wh-og.hs-niederrhein.de/~docx/docs/studium/sortieralgorithmen/

Ganz einfach gefunden bei http://www.google.de

Klick mal ein link an.
Ganz einfach tot!

http://www.danielseifert.de/studium/sortier.html#bubble schrieb:

error 404: Datei nicht gefunden!
Das angegebene Dokument konnte auf diesem Server leider nicht gefunden werden.

Da läuft nix

mfg hohesC

Aber er kann ja zum glück selber googeln!

[DarthZiu]

Die URL geht bei mir ohne Probleme...

Die Seite kommt wohl bei dir nicht durch die Kindersicherung im Browser? *rofl*

[hohesC]

Ja aber die links sind ToT.

ich meine die links auf:
http://www.wh-og.hs-niederrhein.de/~docx/docs/studium/sortieralgorithmen/

oder..?

[DarthZiu]

Ach die meinst du - habe ich gar nicht probiert. Auf der Seite steht doch alles schön erklärt. Sogar mit ner absolute heißen Tabelle die Geschwindigkeiten vergleicht.

[hohesC]

Die Einleitung sagt viel....!

Aber hinter den BÖSEN links die meine Kindersicherung verweigert
erscheint error404.

[DarthZiu]

Jaja, du hast recht, die Links auf der linken Seite (quasi die "linken Links" *lol*) sind tot. Aber die braucht man auf der Seite ja nicht, oder!?