[java/alg] beschouwing sorteer algoritmes

donderdag 28 augustus 2003 21:56

Designer Drugs

Waarom zijn onderwijzers toch altijd zo dol op bubblesort? O( n²) worst && best case vind ik nou niet echt een geweldig sorting algoritme.

Qsort, Heapsort en Mergesort werken gewoon netjes in O( n logn) tijd [de ondergrens voor comparisation algoritmes] en anders zou je met bucketsort nog naar O(n) tijd kunnen

Acties:

Verwijderd

omdat bubblesort standaard is en je kan dit ook gebruiken in een structurele taal, quicksort bvb niet

vrijdag 29 augustus 2003 00:04

Acties:

vrijdag 29 augustus 2003 00:08

Verwijderd schreef op 28 August 2003 @ 21:56:
omdat bubblesort standaard is en je kan dit ook gebruiken in een structurele taal, quicksort bvb niet

Als er één algoritme standaard is, is het quicksort wel; bubblesort wordt in de praktijk eigenlijk nooit gebruikt (behalve misschien in de meest triviale gevallen met een heel duidelijke bovengrens). En wat is een "structurele" taal en waarom zou je daar quicksort niet in kunnen implementeren? In principe is elk algoritme natuurlijk in elke taal te implementeren, maar zijn in-place sorting algoritmen wat makkelijker in een imperatieve taal; voor functionele talen zijn recursieve algoritmen dan weer makkelijker (en is het vereist een gesorteerde kopie op te leveren).

Waarschijnlijk is het idee dat bubble sort makkelijk te begrijpen is, omdat je het op kunt delen in kleine losse stapjes (bottom-up uitleg) maar ik moet zeggen dat ik het niet direct duidelijk vind waarom bubble sort werkt (in de zin van: het levert gegarandeerd een gesorteerde lijst op). Ik vind mergesort zelf een van de meest elegante en duidelijke algoritmen, maar ik kan me voorstellen dat het lastig is om studenten daar een implementatie van te laten schrijven in een imperatieve taal (in een functionele taal is het echter een eitje).

Eigenlijk zou ik dan zeggen dat quicksort het ideale algoritme zou zijn om te leren, want het is zowel een efficient algoritme (praktisch bruikbaar, dus), goed te begrijpen en niet heel ingewikkeld te implementeren in zowel een imperatieve als een functionele taal (al is de in-place variant in een puur functionele taal niet te maken).

Acties:

vrijdag 29 augustus 2003 10:21

off topic:

Glimi schreef op 28 August 2003 @ 21:54:
Qsort, Heapsort en Mergesort werken gewoon netjes in O( n logn) tijd [de ondergrens voor comparisation algoritmes] en anders zou je met bucketsort nog naar O(n) tijd kunnen

Quicksort is O(N^2) worst case; bij een voor de hand liggende (naïve) implementatie, waarbij het eerste (of laatste) element als scheidingswaarde wordt gekozen, treedt die worst case op bij gesorteerde invoer. Het komt in de praktijk natuurlijk nogal vaak voor dat invoer al (gedeeltelijk) gesorteerd is en dan is zo'n eigenschap natuurlijk wel erg vervelend!

Uiteraard is die worst-case performance wel enigszins te vermijden door de scheidingswaarde wat slimmer te kiezen (middelste waarde van eerste, laatste en middelste element uit de invoer, bijvoorbeeld) maar ik kan me voorstellen dat dat de theoretische bezwaren niet weg neemt.

Acties:

vrijdag 29 augustus 2003 17:11

Designer Drugs

Soultaker schreef op 29 August 2003 @ 00:08:
off topic:
Quicksort is O(N^2) worst case; bij een voor de hand liggende (naïve) implementatie, waarbij het eerste (of laatste) element als scheidingswaarde wordt gekozen, treedt die worst case op bij gesorteerde invoer. Het komt in de praktijk natuurlijk nogal vaak voor dat invoer al (gedeeltelijk) gesorteerd is en dan is zo'n eigenschap natuurlijk wel erg vervelend!

Offtopic? Nuttig offtopic noem ik dit

Idd, qsort is worstcase niet zo quick als je zou denken. Echter dan heb je het wel over een hele naïve implementatie. Door het gebruiken van een random pivot, kun je uit gaan van een O( n log n ) performance. Bewijs heb ik even niet bij de hand, maar als je het wilt hebben moet je maar even roepen

_{Maarja de hele opdracht van de TS is een beetje apart aangezien we Collections.sort() kennen (gemodde mergesort)}

Verder bedoelde s-man2 volgens mij dat recursieve algoritmes niet in alle talen kunnen. Op zich klopt dat, maar is dat een beperking voor de talen die heden ten dage geleerd worden? In dit geval totaal niet en zou ik als onderwijzer per direct overgaan op qsort voor zijn simpelheid en doorzichtigheid. Mergesort lijkt me ook niet zo heel moeilijk, maar een Heapsort zou ik nog even niet aan beginnen

(ga verse java studentjes maar eens een heap laten bouwen

)

Acties:

zaterdag 30 augustus 2003 11:29

Glimi schreef op 29 August 2003 @ 10:21:
Door het gebruiken van een random pivot, kun je uit gaan van een O( n log n ) performance. Bewijs heb ik even niet bij de hand, maar als je het wilt hebben moet je maar even roepen

Ben benieuwd wat jij onder "uitgaan van" verstaat. Volgens mij is een random keuze van je pivot point net zo slecht als het domweg kiezen van het eerste element, als het gaat om de worst case performance van random data sets. Het enige verschil is dat het worst case gedrag dan bij andere data sets optreedt (en dus niet bij de relatief vaak voorkomende gesorteerde invoer).

Wat natuurlijk belangrijk is, is dat met QuickSort de gemiddelde complexiteit wel O(N*log(N)) is.

Verder bedoelde s-man2 volgens mij dat recursieve algoritmes niet in alle talen kunnen. Op zich klopt dat, maar is dat een beperking voor de talen die heden ten dage geleerd worden? In dit geval totaal niet en zou ik als onderwijzer per direct overgaan op qsort voor zijn simpelheid en doorzichtigheid. Mergesort lijkt me ook niet zo heel moeilijk, maar een Heapsort zou ik nog even niet aan beginnen

In ieder geval is HeapSort goed iteratief te programmeren. De echte truc van HeapSort is natuurlijk om in-place te sorteren en niet een losse heap (met een echte recursieve datastructuur) op te bouwen; anders wordt de verborgen constante (ondanks de goede worst case complexiteit) wel erg hoog. Mergesort is, denk ik, ook wel iteratief te implementeren.

[ Voor 16% gewijzigd door Soultaker op 29-08-2003 17:19 ]

Acties:

zaterdag 30 augustus 2003 12:10

Designer Drugs

Soultaker schreef op 29 August 2003 @ 17:11:
Ben benieuwd wat jij onder "uitgaan van" verstaat. Volgens mij is een random keuze van je pivot point net zo slecht als het domweg kiezen van het eerste element, als het gaat om de worst case performance van random data sets. Het enige verschil is dat het worst case gedrag dan bij andere data sets optreedt (en dus niet bij de relatief vaak voorkomende gesorteerde invoer).

Wat natuurlijk belangrijk is, is dat met QuickSort de gemiddelde complexiteit wel O(N*log(N)) is.

Ik bedoelde met 'uitgaan van' de expected running time van qsort. Je hebt inderdaad gelijk dat die worst case nog steeds O(n^2) is. Echter die worst case scenario variëert dan wel steeds, de ene keer is het 1,2,3 de volgende keer is het 3,2,1 bijv. wat het natuurlijk totaal ongeschikt maakt voor de voorspelbaarheid van de executie tijd. Dus je hebt helemaal gelijk, ik heb het fout geformuleerd

Nog een leuk stukje quote uit een boek van M Goodrich en R Tamassia

quote: Data structures and Algorithms in Java SE
Experimental studies have shown that if an input sequence can fit entirely in main memory, then the in-place versions of quick-sort and heap-sort run faster then merge-sort. In fact, quick-sort tends, on average, to beat heap-sort in these tests. So, quick-sort is an excellent choice as an general-purpose sorting utility.

_{spelfouten zijn © * Glimi}

In ieder geval is HeapSort goed iteratief te programmeren. De echte truc van HeapSort is natuurlijk om in-place te sorteren en niet een losse heap (met een echte recursieve datastructuur) op te bouwen; anders wordt de verborgen constante (ondanks de goede worst case complexiteit) wel erg hoog.

Ik weet eigenlijk niet hoe groot dat verschil is. Misschien leuk dat eens te testen.

Mergesort is, denk ik, ook wel iteratief te implementeren.

Zou dat veel winst opleveren? Je spaart natuurlijk de recursieve aanroep uit, maar zijn die kosten nou zo hoog tov de input?
De java library (java.util.Arrays) doet het in ieder geval gewoon recursief (mergesort).

Java:

    private static void mergeSort(Object src[], Object dest[],
                                  int low, int high) {
    int length = high - low;

    // Insertion sort on smallest arrays
    if (length < 7) {
        for (int i=low; i<high; i++)
        for (int j=i; j>low &&
                 ((Comparable)dest[j-1]).compareTo((Comparable)dest[j])>0; j--)
            swap(dest, j, j-1);
        return;
    }

        // Recursively sort halves of dest into src
        int mid = (low + high) >> 1;
        mergeSort(dest, src, low, mid);
        mergeSort(dest, src, mid, high);

        // If list is already sorted, just copy from src to dest.  This is an
        // optimization that results in faster sorts for nearly ordered lists.
        if (((Comparable)src[mid-1]).compareTo((Comparable)src[mid]) <= 0) {
           System.arraycopy(src, low, dest, low, length);
           return;
        }

        // Merge sorted halves (now in src) into dest
        for(int i = low, p = low, q = mid; i < high; i++) {
            if (q>=high || p<mid && ((Comparable)src[p]).compareTo(src[q])<=0)
                dest[i] = src[p++];
            else
                dest[i] = src[q++];
        }
    }

Misschien leuk om op te merken dat java voor primitieven quick-sort gebruikt en voor objecten merge-sort. Heb jij enig idee waarom?

[ Voor 3% gewijzigd door Glimi op 30-08-2003 11:37 ]

Acties:

ACM

Software Architect

Werkt hier

Btw, ik gok dat BubbleSort zo vaak gebruik wordt omdat het een simpel algoritme is, en daarmee een mooie inleiding in het sorteren.

Om iemand gelijk maar Quicksort en co te laten leren is niet echt de beste manier lijkt me...

zaterdag 30 augustus 2003 12:40

Acties:

Verwijderd

offtopic:
@Glimi, jij doet op het moment van schrijven toch 2e jaar informatica op de UU? Dan mag je volgende week aan een gedistribueerde quicksort beginnen

[ Voor 4% gewijzigd door Verwijderd op 30-08-2003 12:40 ]

zondag 31 augustus 2003 00:35

Acties:

wasigh

wasigh.blogspot.com

Misschien kan de titel van dit topic beter veranderd worden in "efficientie van algoritmen ;)"

Overigens als je met java 1.3 werkt kun je Arrays.sort gebruiken in combinatie met de Comparable interface.

Niet dat je daar iets van leert maar is wel zo snel.

Je kunt natuurlijk ook chars vergelijken. ( A < z) en de eerste char van een String verkrijgen door String.charAt(0);' maar dat wist je natuurlijk al

zondag 31 augustus 2003 00:42

Acties:

wasigh

wasigh.blogspot.com

Misschien leuk om op te merken dat java voor primitieven quick-sort gebruikt en voor objecten merge-sort. Heb jij enig idee waarom?

[/quote]

Ik neem aan dat dat te maken heeft met de manier waarop ze worden opgeslagen in het geheugen.

De vm alloceert standaard weinig geheugen en bij merge sort kun je makkelijker tijdelijk bestanden naar disk schrijven (sequentieel).

maandag 1 september 2003 13:38

Acties:

maandag 1 september 2003 13:47

Designer Drugs

ACM schreef op 30 August 2003 @ 12:10:
Btw, ik gok dat BubbleSort zo vaak gebruik wordt omdat het een simpel algoritme is, en daarmee een mooie inleiding in het sorteren.

Om iemand gelijk maar Quicksort en co te laten leren is niet echt de beste manier lijkt me...

Mwoah, de complexiteit van bubblesort vind ik niet echt minder dan qsort. Het is wel wat moeilijker in te zien waarom qsort sneller is _{of kan zijn}, maar de werking van qsort is easy

Verwijderd schreef op 30 August 2003 @ 12:40:

offtopic:
@Glimi, jij doet op het moment van schrijven toch 2e jaar informatica op de UU? Dan mag je volgende week aan een gedistribueerde quicksort beginnen

Ik zal zorgen dat ik herkenbaar ben

wasigh schreef op 31 August 2003 @ 00:35:
Misschien kan de titel van dit topic beter veranderd worden in "efficientie van algoritmen ;)"

Hmmmz, zo beter?

Je kunt natuurlijk ook chars vergelijken. ( A < z) en de eerste char van een String verkrijgen door String.charAt(0);' maar dat wist je natuurlijk al

Voor lexcografische ordening zul je moeten sorteren van [minStringLength -1..0] (plus dat de sorting stabiel moet zijn

met een stabiel algoritme

Voorbeeld:
"Ik", "Iep", "Wopper" en "Wasigh" gaan we ordenen. Omdat de kortse string length 2 is gaan we van 1..0 ordenen

pass 1: Char 1
• Wasigh
• Iep
• Ik
• Wopper

pass 2: Char 0
• Iep
• Ik
• Wasigh
• Wopper

Had ik dit gedaan met een stabiel sorting algoritme van char 0..1 dan kwam er dit uit:
pass 1: Char 0
• Ik
• Iep
• Wopper
• Wasigh

pass 1: Char 1
• Wasigh
• Iep
• Ik
• Wopper

_{Ik vertel je toch niets nieuws, maar ik troost me maar dat de search er beter op wordt}

wasigh schreef op 31 August 2003 @ 00:42:
Ik neem aan dat dat te maken heeft met de manier waarop ze worden opgeslagen in het geheugen.

De vm alloceert standaard weinig geheugen en bij merge sort kun je makkelijker tijdelijk bestanden naar disk schrijven (sequentieel).

Hoezo? Een array van objecten wordt net als een array van ints op de heap gealloceerd en opzich bevat een array van objecten ook alleen maar references naar objecten ( ik weet niet precies hoe groot die references zijn, maar groter als een double zal toch niet? - 64 bits dus op I386)

Opzich doet het sorteren niets met de objecten behalve ze benaderen, maar dat zou toch net zo snel moeten gaan als het benaderen van een int op de heap?

Volgens mij zou het dus een array van objecten evenveel ruimte en niet excessief meer accesstijd moeten innemen als een array van primitieven ( ik stel even als max de double) Daarom snap ik je uitleg dus niet helemaal en begrijp ook niet waarom het anders gesorteerd moet worden tbv optimaliteit. Kun je het anders iets duidelijker uitleggen aub?

Acties:

wasigh

wasigh.blogspot.com

De Array zelf word idd op de heap gealloceerd.

De accestijd van de pointer is dus niet groter idd
Maar om Objecten te kunnen vergelijken zul je ze aan moeten spreken. Deze Objecten staan in principe op de Heap gealloceerd. Maar ik kan me voorstellen dat wanneer een een array van Objecten te groot voor de heap wordt deze naar een file wordt weggeschreven. (Door de VM dan)

Bij I/O naar disk maakt het nogal veel uit in efficientie of je een file random aanspreekt of sequentieel aanspreekt.

Wanneer je mergesort gebruikt kun je 2 bestanden sequentieel uitlezen en mergen. Bij quicksort moet je random door je file lezen. Waardoor dat inefficienter wordt.

Dat zou voor mij de enige reden zijn waarom ze mergesort gebruiken.

Het kan natuurlijk ook zijn dat ik er helemaal naast zit

maandag 1 september 2003 13:48

Acties:

dotcode

///\00/\\

http://sunburn.stanford.edu/~knuth/taocp.html

Na deel 3 weetje alles over sorting, laat me weten als je alles begrijpt. Sorteren is niet echt triviaal

maandag 1 september 2003 14:33

Acties:

dinsdag 2 september 2003 00:06

Glimi schreef op 30 August 2003 @ 11:29:
[over het verschil tussen in-place HeapSort en sorteren met een binaire boom]
Ik weet eigenlijk niet hoe groot dat verschil is. Misschien leuk dat eens te testen.

Het hangt een beetje van de omgeving waarin je werkt af. Het verschil tussen in-place en met een kopie sorteren zal niet heel groot zijn (maar zeker wel te merken). Als je een echte binaire boom gaat opbouwen (en voor elke node dus een object met een waarde en twee pointers naar de ondergelegen elementen aanmaakt op de heap) dan kan ik je garanderen dat de performance dramatisch is.

In-place sorteren (en dus met een array inplaats van met losse objecten) is essentieel voor HeapSort, om de strijd met QuickSort nog enigszins aan te kunnen. Zelfs dan is QuickSort gemiddeld efficienter, maar daar staat de onbetrouwbaarheid tegenover (terwijl HeapSort een beter begrensde run time heeft). Daarbij is het gewoon zonde om niet in-place te sorteren terwijl het zonder significante overhead kan. In veel situaties hoef je immers geen kopie van je invoer te houden; in de overige situaties kun je die zelf wel maken.

[over iteratieve ten opzichte van recursive merge sort]
Zou dat veel winst opleveren? Je spaart natuurlijk de recursieve aanroep uit, maar zijn die kosten nou zo hoog tov de input? De java library (java.util.Arrays) doet het in ieder geval gewoon recursief (mergesort).

Dat hangt een beetje van de taal, compiler en het platform af. Een function call zelf is niet echt duur, maar ik kan me voorstellen dat de compiler een iteratief algoritme beter kan optimaliseren (omdat alle instructies voor het algoritme zich binnen dezelfde functie bevinden). Recursieve functies inlinen lijkt me nogal een lastige bezigheid voor een compiler (behalve voor een functionele compiler, natuurlijk, die er specifiek voor gebouwd is).

Misschien leuk om op te merken dat java voor primitieven quick-sort gebruikt en voor objecten merge-sort. Heb jij enig idee waarom?

Volgens mij worden alle primitive types in de Java JVM gerepresenteerd door native ints, net als de object references, dus dan zou het sorteren van primitives met hetzelfde algoritme moeten kunnen (behalve dat er misschien een built-in vergelijkingsinstructie gebruikt kan worden, in plaats van een function call te doen). Het lijkt me dus dat het alloceren/kopiëren van object references in een array dezelfde run-time eigenschappen heeft als het alloceren/kopiëren van primitieve waarden, tenzij er een probleem is met concurrency of de garbage collector ofzo, waardoor primitives toch anders zijn.

Acties:

Infinitive

Misschien leuk om op te merken dat java voor primitieven quick-sort gebruikt en voor objecten merge-sort. Heb jij enig idee waarom?

De vergelijkingsfunctie is vrij traag te noemen. Zou dit ermee te maken kunnen hebben? Zou gemiddeld gezien merge sort minder vergelijkingsaanroepen doen dan quicksort? Hmm, dit slaat waarschijnlijk nergens op...

Zou zo'n keuze eigenlijk niet in commentaar verantwoord moeten zijn?

putStr $ map (x -> chr $ round $ 21/2 * x^3 - 92 * x^2 + 503/2 * x - 105) [1..4]

dinsdag 2 september 2003 01:57

Acties:

dinsdag 2 september 2003 10:18

Moderator Devschuur®

Demotivational Speaker

Glimi schreef op 01 September 2003 @ 13:38:
( ik weet niet precies hoe groot die references zijn, maar groter als een double zal toch niet? - 64 bits dus op I386)

32 bits over het algemeen, tenzij het een machine is met 64 bits geheugenadressen natuurlijk. Veel meer info dan het geheugenadres hoeft er niet te staan. Null is gewoon 0, wat over het algemeen een ongeldig adres is, en de rest van de info, zoals het type van het object, kan gewoon vanaf dat geheugenadres worden gelezen

Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.

Acties:

Pooh

Lees eens een boek

Glimi schreef op 01 September 2003 @ 13:38 een heleboel, waaronder::
[...]
Voor lexcografische ordening zul je moeten sorteren van [minStringLength -1..0] (plus dat de sorting stabiel moet zijn met een stabiel algoritme

Voorbeeld:
[...]

Volgens mij ben je er daarmee niet. Wat als je de volgende array wilt sorteren?
"bb"
"aaaaa2"
"cc"
"aaaaa1"

dinsdag 2 september 2003 12:03

Acties:

MSalters

Yep, de correcte methode om een verzameling strings te sorteren is door een enkele sorteerslag waarbij je alle karakters checkt, te beginnen met de eerste.

Dus (pseudo-code)

code:

for( i = 0 ; i < length(lhs) AND i < length(rhs) ; ++ i )
  if ( lhs[i] < rhs[i] ) return smaller
  if ( lhs[i] > rhs[i] ) return greater
// Remaining cases are when lhs is a prefix of rhs or vice versa
if ( length(lhs) < length(rhs) ) return smaller
if ( length(lhs) > length(rhs) ) return greater
return equal

[ Voor 3% gewijzigd door MSalters op 02-09-2003 12:03 ]

Man hopes. Genius creates. Ralph Waldo Emerson
Never worry about theory as long as the machinery does what it's supposed to do. R. A. Heinlein

dinsdag 2 september 2003 12:16

Acties:

dinsdag 2 september 2003 13:16

MSalters schreef op 02 september 2003 @ 12:03:
Yep, de correcte methode om een verzameling strings te sorteren is door een enkele sorteerslag waarbij je alle karakters checkt, te beginnen met de eerste.

Noem je dat een sorteerslag? Ik zie alleen maar een vergelijking van twee strings. Die is zowel in Java als C/C++ al standaard beschikbaar.

Acties:

RickN

Ik denk dat Glimi het Radix Sort algoritme beschreef, waarbij je idd van het minst significante char/digit naar het meest significante char/digit sorteert. Dit is vrij tegenintuïtief, maar het levert een algoritme met een theoretische O(n) efficientie op, wat alleen mogelijk is omdat het geen comparision sort is. In de praktijk is radix sort helemaal niet zo geweldig, omdat het aantal digits/chars van de te sorteren elementen vaak logaritmisch van n afhangt, waardoor je weer op een O(n log n) algoritme komt.

Als je alleen twee elementen wilt vergelijken moet je natuurlijk niet bij het minst significante digit beginnen. In dat geval moet je immers altijd alle digits aflopen, terwijl je als je bij het meest significante digit begint een early out hebt.

[ Voor 3% gewijzigd door RickN op 02-09-2003 13:19 ]

He who knows only his own side of the case knows little of that.

dinsdag 2 september 2003 17:56

Acties:

Grijze Vos

Ik heeb zelf toen ik een jaar of 10 was mbv bubbelsort een top 10 scorelijst geimplementeerd, voor een game die ik had gebouwd op mn MSX-2. Ik begreep toen voor 100% hoe het werktte, dusse, kdenk niet dat bubblesort zo moeilijk te begrijpen is.

Quicksort is een goeie als je les krijgt in een functionele taal, imperatief, zou ik toch echt met de bubblesort beginnen.

Op zoek naar een nieuwe collega, .NET webdev, voornamelijk productontwikkeling. DM voor meer info

dinsdag 2 september 2003 19:14

Acties:

vinnux

Quicksort is ook niet zo ontzettend moeilijk te begrijpen. Je neemt een ongeordende lijst. Je pakt de waarde die op de middelste plaatst staat en zet alles wat groter is erboven en alles wat kleiner is er onder. Nu heb je twee partities, eentje met de hoogste getallen en eentje met de laagste. Voor deze partities herhaal je het zelfde truukje nogmaals, todat alle partities 1 groot zijn. Op dat momement heb je je lijst geordenend. Echter wanneer de partities te klein worden (8ofzo?) dan is het beter om deze met insertion sort te sorteren en dan heb je Optimized Quicksort.n O ja Quixksort is niet stabiel.
Het is maar een globale uitleg he.

Tevens moet ik zeggen dat voor kleine lijsten (onder de 1000 items ofzo) Quicksort langzamer is dan BV Bubble sort. Sorteer algoritmes zijn allemaal gemaakt voor speciale doeleinden en aantal te sorteren items.
BubbleSort is bijvoorbeeld veel sneller wanneer de lijst al gedeeltelijk gesorteerd is en in veel gevallen is dat ook zo.

[ Voor 3% gewijzigd door vinnux op 02-09-2003 19:16 ]

dinsdag 2 september 2003 22:49

Acties:

dinsdag 2 september 2003 23:44

vgouw schreef op 02 September 2003 @ 19:14:
Tevens moet ik zeggen dat voor kleine lijsten (onder de 1000 items ofzo) Quicksort langzamer is dan BV Bubble sort. Sorteer algoritmes zijn allemaal gemaakt voor speciale doeleinden en aantal te sorteren items.
BubbleSort is bijvoorbeeld veel sneller wanneer de lijst al gedeeltelijk gesorteerd is en in veel gevallen is dat ook zo.

Waar baseer je deze uitspraken op? Heb je het over specifieke implementaties op specifieke platforms of over objectieve gegevens als het aantal vergelijkingen en verwisselingen van een bepaald algoritme? Bij welke invoergrootte ligt volgens jouw het omslagpunt?

Ik vind je uitspraken op deze manier nogal radikaal en slecht onderbouwd. Qua complexiteit is QuickSort hooguit net zo slecht als BubbleSort (en is BubbleSort dus nooit beter); over executietijden valt zonder informatie over implementatie en platform niet zoveel te zeggen, maar het lijkt me vrij onwaarschijnlijk dat je een BubbleSort implementatie weet te construeren die daadwerkelijk efficienter is dan een efficiente QuickSort implementatie, behalve misschien voor enkele triviale gevallen met een invoer van 2 of 3 elementen.

Acties:

vinnux

Alle uitspraken zijn gebasseerd op in Java geschreven sorteer algoritmes en gebasseerd op strings.

Kosten van een sorteeralgoritme zijn gebasseerd op de volgende punten:
- Vergelijkingen (aantal, kosten)
- Verwisselingen (aantal, kosten)
Hoe minder vergelijkingen er nodig zijn hoe sneller het algoritme.
Hoe minder zwaar een verwisseling is hoe sneller een algoritme.
Het vergelijken van native types is altijd sneller dan het vergelijken van objecten, hetzelfde geld voor verplaatsen echter in mindere mate.

Hier een aantal N^2 algoritmes, namelijk Selection sort (S), Insertation sort(I) en Bubble sort(B ).
Selection sort: N^2/2 vergelijkingen N verwisselingen
Insertation sort: N^2/4 vergelijkingen N^2/4 verwisselingen (gem)
Bubble sort: N^2/2 vergelijkingen N^2/2 verwisselingen

Er wordt uitgegaan van het sorteren van Strings.
1000 items = S129 I65 B170
2000 items = S563 I295 B725
4000 items = S238 I1328 B3210

Insertation Sort is het snelst omdat String Objecten zijn en Objecten vergelijken kost veel tijd. Wanneer verwisselen het duurste zou zijn dan zou Selection sort het snelste zijn.

Quicksort, etc bespreek ik morgen wel. Nu slapen.

woensdag 3 september 2003 00:01

Acties:

woensdag 3 september 2003 00:24

Moderator Devschuur®

Demotivational Speaker

Nu zeg je nog niet veel
Hoe lang zijn de strings? Waar komen ze vandaan? (zijn ze gegenereerd? zo ja, hoe?) In welke mate zijn ze al gesorteerd?

Gewoon komen met een paar nummertjes bewijst natuurlijk niets

Overigens is een verwisseling van een object net zo snel als een verwisseling van een int (mits er bij de verwisseling niet gecast wordt)

[ Voor 26% gewijzigd door .oisyn op 03-09-2003 00:05 ]

Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.

Acties:

vinnux

Met die getallen bedoel je dit?
1000 items = S129 I65 B170
2000 items = S563 I295 B725
4000 items = S238 I1328 B3210

Gebasseerd op de meeste gangbare vorm.

[ Voor 16% gewijzigd door vinnux op 03-09-2003 00:25 ]

woensdag 3 september 2003 00:55

Acties:

woensdag 3 september 2003 12:17

Moderator Devschuur®

Demotivational Speaker

ja dat postte je net ook al, en zoals ik al zei, dat bewijst natuurlijk nog helemaal niets

Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.

Acties:

woensdag 3 september 2003 12:23

Designer Drugs

Waarom zou quicksort niet stabiel te maken zijn? Als je je lijst met getallen netjes afloopt voor te orderen, loop je ze gewoon vanaf 0..n af en push je ze ergens in op die volgorde. Als je dan ook nog je pivot (en de objecten equal to the pivot) op volgorde van aflopen in een lijst stopt, lijkt quicksort me zo stabiel als wat

Acties:

woensdag 3 september 2003 12:28

Moderator Devschuur®

Demotivational Speaker

Glimi: je vergeet de pivot zelf. Als er een element is dat gelijk is aan de pivot, wordt hij voor (of juist achter, ligt eraan wat je doet) de pivot geplaatst, terwijl hij er in de oorspronkelijke volgorde juist achter (of voor) kan staan

Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.

Acties:

woensdag 3 september 2003 12:40

Designer Drugs

Hoezo? Je kunt gewoon een random place kiezen in de array van te sorteren getallen, de pivot niet uit de lijst halen, maar een copie van de pivot maken.
Vervolgens ga je de lijst totaal aflopen en plaats je de getallen in 3 lijsten; de kleiner, de groter en de equal lijst.
Ik zie het onstabiele nog niet echt?

Acties: