algorithmes de tri pour les listes triées en majorité

Question

Je travaille sur une liste d'entiers provenant d'un fichier. Et je dois utiliser un algorithme de tri pour les classer par ordre décroissant. Je connais le temps d'exécution de quelques algorithmes de tri et je sais que leur utilisation est situationnelle. Ma question est donc la suivante : Quel serait l'algorithme de tri le plus rapide pour une liste de N'IMPORTE QUELLE taille qui est déjà triée à 90 % ? (dans mon fichier j'ai 10.000 entrées mais 9.500 d'entre elles sont déjà triées).

Merci,

Answer 1

Le site Timsort tel qu'il a été développé pour Python (et maintenant utilisé en Java), intègre des optimisations pour traiter les "runs" partiellement triés.

Answer 2

Le tri par insertion devrait convenir, si vous choisissez de le coder vous-même plutôt que d'utiliser les fonctions de tri fournies par le langage.

1. Il fonctionne vraiment bien lorsque la liste est presque triée (bien qu'il soit d'ordre O(N^2), si la liste est presque triée, la boucle intérieure ne sera pas ne sera pas exécutée souvent)
2. Il est assez facile à mettre en œuvre.

Présentation de l'implémentation Python de Insertion Sort.

Programme

def InsertionSort(Array):
    Total = 0
    for i in xrange(1, len(Array)):
        j, I, = i - 1, i
        while j >= 0 and Array[I] > Array[j]:
            Array[I], Array[j] = Array[j], Array[I]
            j, I, Total = j - 1, I - 1, Total + 1
    print "Insertion Sort Total Operations :", Total

Sortie

Le pire des cas

TestArray  = range(1, 11)
InsertionSort(TestArray)
Insertion Sort Total Operations : 45

Meilleur cas

TestArray  = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
InsertionSort(TestArray)
Insertion Sort Total Operations : 0

Tableau trié à 90

TestArray  = [1, 9, 8, 7, 6, 5, 4, 3, 2, 10]
InsertionSort(TestArray)
Insertion Sort Total Operations : 17

Tableau semi-trié

TestArray  = [10, 9, 8, 7, 6, 1, 2, 3, 4, 5]
InsertionSort(TestArray)
Insertion Sort Total Operations : 10

Answer 3

Pour son std::sort, le C++ utilise le tri introspectif, où le tableau/la liste est d'abord trié(e) à l'aide de quicksort pour une certaine profondeur de récurrence, suivi de heapsort . Je ne sais pas pour 90% mais heapsort semble bien fonctionner sur des tableaux/listes déjà triés... donc je vous recommande d'essayer.