Shell sortieren nur 3 mal schneller als Bubble sort?

Ich habe Shell in C und nur etwa 3 mal schneller als Bubble Sort implementiert. Hier ist meine Sortierdauer in Sekunden:Shell sortieren nur 3 mal schneller als Bubble sort?

For list of 100 integers: 
BubbleSort: 0.000333 
ShakeSort: 0.000282 
QuickSort: 0.000048 
QuickSort_Iter: 0.000063 
InsertionSort: 0.000188 
ShellSort: 0.000150 

For list of 1000 integers: 
BubbleSort: 0.028191 
ShakeSort: 0.019354 
QuickSort: 0.000435 
QuickSort_Iter: 0.000528 
InsertionSort: 0.011917 
ShellSort: 0.003664 

For list of 5000 integers: 
BubbleSort: 0.241116 
ShakeSort: 0.222127 
QuickSort: 0.001306 
QuickSort_Iter: 0.001592 
InsertionSort: 0.151656 
ShellSort: 0.091002 

For list of 10000 integers: 
BubbleSort: 0.959580 
ShakeSort: 0.872648 
QuickSort: 0.002877 
QuickSort_Iter: 0.003379 
InsertionSort: 0.601329 
ShellSort: 0.350866

Es sich normal oder ist es wahrscheinlich ein Problem mit meiner Implementierung?

Quelle

2016-07-23 LynnXe

Es hängt enorm auf Dataset – Jcl

es Array-basierten Vektor von pseudozufälligen Ganzzahlen 0-999. Ich frage mich nur, ob es überhaupt eine angemessene Leistung für Shell-Sortierung, unter jeder Bedingung – LynnXe

Es gibt keine solche Sache wie "keine" Bedingung. Bedingung ist wirklich wichtig ... stellen Sie sich vor, Sie haben ein komplett sortiertes Zahlenfeld mit Ausnahme der ersten und der letzten, die getauscht werden: In diesem Fall ist die Shell-Sortierung wahrscheinlich schneller als die Blasensortierung (da sie einen Swap durchführen kann) bubble sort müsste alle Zahlen tauschen) ... aber das ist nur ein Randfall: Es bedeutet nicht, dass die Blasensortierung langsamer oder schneller ist als die Shell-Sortierung, sondern nur für diesen spezifischen Datensatz. Das 'n' im großen O zählt, viel :-) – Jcl

Ich habe ein Sortier-Benchmark-Programm mit 4 Varianten von Shell-Sortierung und Bubble-Sortierung eingebaut. Drei der vier Varianten haben ähnliche Timing-Eigenschaften; der vierte ist dramatisch schlechter als die anderen drei. Wenn die Sortierungsgröße 1000 ist, benötigen die 3 Shell-Sortierungen weniger als 100 μs, während der Slow-Modus weniger als 600 μs und die Bubble-Sortierung weniger als 900 μs benötigt. Bei 10.000 variieren die Zeiten zwischen 1-2 ms und 70 ms gegenüber 142 ms. und bei Größe 100.000 variieren die Zeiten zwischen 14-30ms vs 8.6s vs 18s. Somit ist eine der Shell-Sorten etwa halb so schnell wie die Bubble-Sorte, aber die anderen sind viel besser. - Jonathan Leffler

Ok, änderte ich die Implementierung, Insertion Art Logik Untervektoren zu sortieren während Shell sortieren, so dass nun führt er wie erwartet - LynnXe

Quelle

2016-08-05 06:32:15 Armali

Shell sortieren nur 3 mal schneller als Bubble sort?

Antwort

Verwandte Themen