Confusion sur l'efficacité des algorithmes de tri

Question

J'ai lu sur le livre des algorithmes de sélection/insertion/tri des coquilles, et selon le livre, le tri par sélection est généralement plus lent que le tri par insertion qui est plus lent que le tri des coquilles. Cependant, j'ai effectué quelques tests en utilisant Python seulement pour trouver que le tri par sélection est le plus rapide! Je n'arrive pas à comprendre pourquoi, la seule raison à laquelle je peux penser est qu'il y a trop de swaps entre les éléments de la liste.

Voici le code que j'utilisé pour le test:

import random 
import time 



lst = [ random.randint(1,10000) for _ in xrange(10000) ] 

def timeit(f): 
    def wrapper(*args): 
     t1 = time.time() 
     result = f(*args) 
     t2 = time.time() 
     print 'time: %f' %(t2 - t1) 
     return result 
    return wrapper 

@timeit 
def selectionSort(lst): 
    for i in xrange(len(lst)): 
     minNum = lst[i] 
     for j in xrange(i+1, len(lst)): 
      if lst[j] < minNum: 
       minNum = lst[j] 
     lst[i], minNum = minNum, lst[i] 
    return lst 

@timeit 
def insertionSort(lst): 
    for i in xrange(len(lst)): 
     for j in xrange(i, 0, -1): 
      if lst[j] < lst[j-1]: 
       lst[j], lst[j-1] = lst[j-1], lst[j] 
      else: 
       break 
    return lst 

@timeit 
def shellSort(lst): 
    h = 1 
    while (h < len(lst)//3): 
     h = h * 3 + 1 


    while (h >= 1): 
     for i in xrange(h, len(lst)): 
      for j in xrange(i, h-1, -h): 
       if lst[j] < lst[j-h]: 
        lst[j], lst[j-h] = lst[j-h], lst[j] 
       else: 
        break 
     h //= 3 
    return lst 


selectionSort(lst[:]) 
insertionSort(lst[:]) 
shellSort(lst[:]) 

Le résultat sur ma machine se présente comme suit:

[linuxfish@Arch week2]$./sortAlgorithms.py 
time: 4.533489 
time: 22.247762 
time: 12.867564 

Voici les résultats après que j'ai ajouté le code à deux lignes, assez incroyable ..

time: 4.937693 
time: 16.773167 
time: 0.179526 

La méthode de tri a été adapté à partir this book par Robert Sedgewick, et je pense que j'ai implémenté les algorithmes exactement comme le livre a été dit bien que les algorithmes originaux dans le livre aient été écrits en Java

Answer 1

Regardez la section de tri http://bigocheatsheet.com/. et http://en.wikipedia.org/wiki/Shellsort Il semble que les données que vous utilisez provoquent un comportement différent car seul le tri sélectif est stable.

Voici une l'info:

   | Best | Average | Worst 
Select Sort | O(n^2) | O(n^2) | O(n^2) 

Insertion Sort | O(n) | O(n^2) | O(n^2) 

Shell sort  | O(nlogn) | depends on the gap | O(n^2)