Tri de coquille

Dans ce didacticiel, vous apprendrez comment fonctionne le tri shell. Vous trouverez également des exemples fonctionnels de tri de shell en C, C ++, Java et Python.

Le tri shell est un algorithme qui trie d'abord les éléments très éloignés les uns des autres et réduit successivement l'intervalle entre les éléments à trier. C'est une version généralisée du tri par insertion.

Dans le tri shell, les éléments à un intervalle spécifique sont triés. L'intervalle entre les éléments est progressivement diminué en fonction de la séquence utilisée. Les performances du tri shell dépendent du type de séquence utilisé pour un tableau d'entrée donné.

Certaines des séquences optimales utilisées sont:

• Séquence originale de Shell: N/2 , N/4 ,… , 1
• Incréments de Knuth: 1, 4, 13,… , (3k - 1) / 2
• Les incréments de Sedgewick: 1, 8, 23, 77, 281, 1073, 4193, 16577… 4j+1+ 3·2j+ 1
• Les incréments de Hibbard: 1, 3, 7, 15, 31, 63, 127, 255, 511…
• Incrément de Papernov & Stasevich: 1, 3, 5, 9, 17, 33, 65,…
• Pratt: 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81… .

Comment fonctionne le tri Shell?

1. Supposons que nous devions trier le tableau suivant. Tableau initial
2. Nous utilisons la séquence originale du shell (N/2, N/4,… 1) comme intervalles dans notre algorithme.
   Dans la première boucle, si la taille du tableau est N = 8alors, les éléments situés à l'intervalle de N/2 = 4sont comparés et échangés s'ils ne sont pas dans l'ordre.
   1. Le 0ème élément est comparé au 4ème élément.
   2. Si le 0ème élément est supérieur au 4ème alors, le 4ème élément est d'abord stocké dans la tempvariable et l' 0thélément (c'est-à-dire le plus grand élément) est stocké dans la 4thposition et l'élément stocké dans tempest stocké dans la 0thposition. Réorganiser les éléments à n / 2 intervalle
      Ce processus se poursuit pour tous les éléments restants. Réorganiser tous les éléments à n / 2 intervalle
3. Dans la deuxième boucle, un intervalle de N/4 = 8/4 = 2est pris et à nouveau les éléments se trouvant à ces intervalles sont triés. Réorganiser les éléments à un intervalle n / 4
   Vous pourriez être confus à ce stade. Tous les éléments du tableau se trouvant à l'intervalle courant sont comparés.
   Les éléments en 4ème et en 2ndposition sont comparés. Les éléments en 2ème et en 0thposition sont également comparés. Tous les éléments du tableau se trouvant à l'intervalle courant sont comparés.
4. Le même processus se poursuit pour les éléments restants. Réorganiser tous les éléments à n / 4 intervalle
5. Enfin, lorsque l'intervalle est, N/8 = 8/8 =1les éléments du tableau situés à l'intervalle de 1 sont triés. Le tableau est maintenant complètement trié. Réorganiser les éléments à n / 8 intervalle

Algorithme de tri Shell

 shellSort (tableau, taille) pour l'intervalle i <- size / 2n jusqu'à 1 pour chaque intervalle "i" dans le tableau trie tous les éléments à l'intervalle "i" fin shellSort

Exemples Python, Java et C / C ++

Python Java C C ++

# Shell sort in python def shellSort(array, n): # Rearrange elements at each n/2, n/4, n/8,… intervals interval = n // 2 while interval> 0: for i in range(interval, n): temp = array(i) j = i while j>= interval and array(j - interval)> temp: array(j) = array(j - interval) j -= interval array(j) = temp interval //= 2 data = (9, 8, 3, 7, 5, 6, 4, 1) size = len(data) shellSort(data, size) print('Sorted Array in Ascending Order:') print(data)

// Shell sort in Java programming import java.util.Arrays; // Shell sort class ShellSort ( // Rearrange elements at each n/2, n/4, n/8,… intervals void shellSort(int array(), int n) ( for (int interval = n / 2; interval> 0; interval /= 2) ( for (int i = interval; i  = interval && array(j - interval)> temp; j -= interval) ( array(j) = array(j - interval); ) array(j) = temp; ) ) ) // Driver code public static void main(String args()) ( int() data = ( 9, 8, 3, 7, 5, 6, 4, 1 ); int size = data.length; ShellSort ss = new ShellSort(); ss.shellSort(data, size); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) ) 

// Shell Sort in C programming #include // Shell sort void shellSort(int array(), int n) ( // Rearrange elements at each n/2, n/4, n/8,… intervals for (int interval = n / 2; interval> 0; interval /= 2) ( for (int i = interval; i  = interval && array(j - interval)> temp; j -= interval) ( array(j) = array(j - interval); ) array(j) = temp; ) ) ) // Print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int data() = (9, 8, 3, 7, 5, 6, 4, 1); int size = sizeof(data) / sizeof(data(0)); shellSort(data, size); printf("Sorted array: "); printArray(data, size); ) 

// Shell Sort in C++ programming #include using namespace std; // Shell sort void shellSort(int array(), int n) ( // Rearrange elements at each n/2, n/4, n/8,… intervals for (int interval = n / 2; interval> 0; interval /= 2) ( for (int i = interval; i  = interval && array(j - interval)> temp; j -= interval) ( array(j) = array(j - interval); ) array(j) = temp; ) ) ) // Print an array void printArray(int array(), int size) ( int i; for (i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Driver code int main() ( int data() = (9, 8, 3, 7, 5, 6, 4, 1); int size = sizeof(data) / sizeof(data(0)); shellSort(data, size); cout << "Sorted array: "; printArray(data, size); ) 

Complexité

Le tri Shell est un algorithme de tri instable car cet algorithme n'examine pas les éléments se trouvant entre les intervalles.

Complexité temporelle

• Pire complexité des cas : inférieure ou égale à La complexité des pires cas pour le tri de shell est toujours inférieure ou égale à . Selon le théorème de Poonen, la complexité du pire des cas pour le tri des coquilles est ou ou ou quelque chose entre les deux.O(n2)
O(n2)
Θ(Nlog N)2/(log log N)2)Θ(Nlog N)2/log log N)Θ(N(log N)2)
• Meilleure complexité des cas : O(n*log n)
  lorsque le tableau est déjà trié, le nombre total de comparaisons pour chaque intervalle (ou incrément) est égal à la taille du tableau.
• Complexité moyenne des cas : O(n*log n)
  c'est environ .O(n1.25)

La complexité dépend de l'intervalle choisi. Les complexités ci-dessus diffèrent pour les différentes séquences d'incrément choisies. La meilleure séquence d'incrémentation est inconnue.

Complexité de l'espace:

La complexité spatiale pour le tri des coquilles est O(1).

Applications de tri Shell

Le tri shell est utilisé lorsque:

• appeler une pile est une surcharge. La bibliothèque uClibc utilise ce tri.
• la récursivité dépasse une limite. Le compresseur bzip2 l'utilise.
• Le tri par insertion ne fonctionne pas correctement lorsque les éléments proches sont éloignés. Le tri des coquilles aide à réduire la distance entre les éléments proches. Ainsi, il y aura moins de permutations à effectuer.