View
376
Download
0
Category
Preview:
DESCRIPTION
Citation preview
Sortierverfahren und Sortierverfahren und ZufallszahlenZufallszahlen
Christian BeusterChristian Beuster
InhaltInhalt
Sortierverfahren Sortierverfahren Vergleich von SortierverfahrenVergleich von SortierverfahrenZufallzahlZufallzahl
SortierverfahrenSortierverfahren
Vergleichsbasierte Sortierverfahren Vergleichsbasierte Sortierverfahren (Wichtigsten)(Wichtigsten)
Vergleichsbasierte Sortierverfahren Vergleichsbasierte Sortierverfahren (Weitere)(Weitere)
Nichtvergleichsbasierte SortierverfahrenNichtvergleichsbasierte Sortierverfahren
Sortierverfahren Vergleich von Sortierverfahren Zufallszahl
Vergleichsbasierte Sortierverfahren Vergleichsbasierte Sortierverfahren (Wichtigsten)(Wichtigsten)
AlgorithmusGeschwindkeit (günstigster,
durchsschn., schlechtester Fall)
Platzbedarf Stabil?
Bogosort O(n), O(nn!), unendlich in situ Nein
Selectionsort O(n2), O(n2), O(n2) in situ Ja
Insertionsort O(n), O(n2), O(n2) in situ Ja
Bubblesort O(n), O(n2), O(n2) in situ Ja
Quicksort O(n log n), O(n log n), O(n2) in situ Nein
Mergesort O(n log n), O(n log n), O(n log n) O(n) Ja
Heapsort O(n), O(n log n), O(n log n) in situ Nein
Introsort O(n log n), O(n log n), O(n log n) in situ Nein
Sortierverfahren Vergleich von Sortierverfahren Zufallszahl
Vergleichsbasierte Sortierverfahren Vergleichsbasierte Sortierverfahren (Weitere)(Weitere)
Binary Tree SortBinary Tree Sort CombsortCombsort GnomesortGnomesort Merge InsertionMerge Insertion Natural MergesortNatural Mergesort ShakersortShakersort Shellsort Shellsort SlowsortSlowsort SmoothsortSmoothsort StoogesortStoogesort Swap-SortSwap-Sort
Sortierverfahren Vergleich von Sortierverfahren Zufallszahl
Nichtvergleichsbasierte Nichtvergleichsbasierte SortierverfahrenSortierverfahren
BucketsortBucketsortCountingsortCountingsortRadixsortRadixsort
Sortierverfahren Vergleich von Sortierverfahren Zufallszahl
Vergleich von SortierverfahrenVergleich von Sortierverfahren
WirkungsweiseWirkungsweiseZeitaufwand (unsortiert)Zeitaufwand (unsortiert)Zeitaufwand (vorsortiert)Zeitaufwand (vorsortiert)
Sortierverfahren Vergleich von Sortierverfahren Zufallszahl
WirkungsweiseWirkungsweise
Sortierverfahren Vergleich von Sortierverfahren Zufallszahl
Zeitaufwand (unsortiert)Zeitaufwand (unsortiert)Die Ergebnisse in Sekunden der Laufzeitmessung auf einem 450-MHzPentium-II-PC sind - bei unsortierten Daten:
n=10000n=10000 n=20000n=20000 n=30000n=30000 n=40000n=40000
BubbleBubble 1,71,7 6,76,7 14,714,7 26,126,1
SelectionSelection 0,80,8 3,13,1 7,17,1 12,612,6
InsertionInsertion 0,40,4 1,251,25 2,92,9 6,76,7
Sortierverfahren Vergleich von Sortierverfahren Zufallszahl
Zeitaufwand (vorsortiert)Zeitaufwand (vorsortiert)
n=10000n=10000 n=20000n=20000 n=30000n=30000 n=40000n=40000
BubbleBubble 00 00 00 00
SelectionSelection 0,750,75 3,13,1 7,17,1 12,612,6
InsertionInsertion 00 00 00 00
... und bei vorsortierten Daten:
Sortierverfahren Vergleich von Sortierverfahren Zufallszahl
ZufallszahlZufallszahl
HauptbefehlHauptbefehlZufälligkeitZufälligkeitZahlen von bisZahlen von bis
Sortierverfahren Vergleich von Sortierverfahren Zufallszahl
HauptbefehlHauptbefehl
wird mit „rand()“ (random) und „srand()“ wird mit „rand()“ (random) und „srand()“ (start random) gelöst aus „stdlib.h“(start random) gelöst aus „stdlib.h“
„„srand()“ = Start: srand()“ = Start:
srand(/*Startzahl hier eingeben*/)srand(/*Startzahl hier eingeben*/) „„rand()“ für eigentliche „Zufallsgenerierung“rand()“ für eigentliche „Zufallsgenerierung“
Sortierverfahren Vergleich von Sortierverfahren Zufallszahl
ZufälligkeitZufälligkeit
Zufälligkeit existiert nichtZufälligkeit existiert nicht „„time(0)“ deswegen bei srand als Starttime(0)“ deswegen bei srand als Start „„time.h“ erforderlichtime.h“ erforderlich
Sortierverfahren Vergleich von Sortierverfahren Zufallszahl
Zahlen von bisZahlen von bis
durch Modulo bewirken und 1 addierendurch Modulo bewirken und 1 addieren
Sortierverfahren Vergleich von Sortierverfahren Zufallszahl
StandardStandard
#include <iostream>#include <iostream>
#include <stdlib.h>#include <stdlib.h>
#include <time.h>#include <time.h>
using namespace std;using namespace std;
int main()int main()
{{
int x;int x;
srand(time(0)); srand(time(0));
x=rand();x=rand();
cout<<x<<endl;cout<<x<<endl;
return 0;return 0;
}}
Danke für eure und Ihre AufmerksamkeitDanke für eure und Ihre Aufmerksamkeit
Recommended