tri d'un tableau partiellement trié avec tri par insertion

-1

J'ai un tableau avec le premier jusqu'à ce que l'élément N soit trié et N + 1 jusqu'à ce que elemnt N + M soit trié (le tableau est composé de N + M éléments). quelle est la complexité du tri de ce tableau en utilisant le tri par insertion? Je pense que c'est (N + M)^2, est-ce vrai?tri d'un tableau partiellement trié avec tri par insertion

Source

2013-02-01 user2023203

Vous devez trier les éléments (M-N). Supposons que le tableau entier est réellement trié. Combien de comparaisons sont nécessaires pour insérer l'élément N + 1 à sa place? Combien de comparaisons sont nécessaires pour insérer l'élément M à sa place? – beaker

Les éléments situés aux M dernières places (de N + 1 à N + M) sont-ils tous plus grands que les premiers N éléments? Ou en d'autres termes est-il garanti que 'array [i] == trié [i]' pour chaque 'i <= N'? – amit

amit, non, ils ne sont pas – user2023203

Si vous souhaitez utiliser le tri par insertion, vous devez utiliser O (M * (M + N)). Cependant, une meilleure approche pourrait être de trier la partie non triée dans O (M * lgM), puis de fusionner deux parties triées dans O (N + M).

Source

2013-02-02 07:17:21 iampat

tri d'un tableau partiellement trié avec tri par insertion

Répondre

Questions connexes