Algorithme Gymnastique 24 Tri cyclique

Cyclic Sort

Étant donné une liste contenant n objets. Chaque objet s'est vu attribuer un numéro unique de 1 à n lors de sa création, en fonction de l'ordre dans lequel il a été créé.

Créez une fonction qui trie les objets sur place en fonction de nombres consécutifs de O (n). Aucune structure de données supplémentaire n'est nécessaire. Par souci de simplicité, supposons que vous receviez une liste d'entiers contenant uniquement des nombres consécutifs. Cependant, chaque numéro est en fait un objet.

Exemple

Input: [3, 1, 5, 4, 2] Output: [1, 2, 3, 4, 5]

Input: [2, 6, 4, 3, 1, 5] Output: [1, 2, 3, 4, 5, 6]

Input: [1, 5, 6, 4, 3, 2] Output: [1, 2, 3, 4, 5, 6]

Solution Comme vous le savez, la liste contient des nombres compris entre 1 et n. Profitez de ce fait pour trouver un moyen efficace de trier les nombres. Tous les numéros sont uniques, vous pouvez donc placer chaque numéro dans la bonne position. Autrement dit, 1 est placé à l'index 0, 2 est placé à l'index 1, et ainsi de suite.

Pour placer un nombre (ou un objet en général) dans l'index correct, vous devez d'abord le trouver. Si vous trouvez d'abord le numéro et le mettez au bon endroit, O (N ^ 2), c'est inacceptable.

Au lieu de cela, répétez la liste avec un nombre à la fois, et si le numéro actuel n'est pas dans l'index correct, remplacez-le par le nombre dans l'index correct. De cette façon, il recherche tous les nombres, les met dans le bon index et trie la liste entière.

def cyclic_sort(nums):
  i = 0
  while i < len(nums):
    j = nums[i] - 1
    if nums[i] != nums[j]:
      nums[i], nums[j] = nums[j], nums[i]  # swap
    else:
      i += 1
  return nums


def main():
  print(cyclic_sort([3, 1, 5, 4, 2]))
  print(cyclic_sort([2, 6, 4, 3, 1, 5]))
  print(cyclic_sort([1, 5, 6, 4, 3, 2]))


main()

Recommended Posts

Algorithme Gymnastique 24 Tri cyclique
Gymnastique algorithmique 10
Gymnastique algorithmique 3
Gymnastique algorithmique 9
Gymnastique algorithmique 2
Gymnastique algorithmique 7
Gymnastique algorithmique 15
Gymnastique algorithmique 16
Gymnastique algorithmique 8
Gymnastique algorithmique 17
Gymnastique algorithmique 18
Gymnastique algorithmique 11
Exercice d'algorithme 5
Gymnastique algorithmique 4
Gymnastique algorithmique 24 sous-ensembles
Gymnastique algorithmique 23 Intervalles de fusion
Gymnastique d'algorithme 20 Supprimer les doublons
Algorithme Gymnastique 21 Cycle LinkedList
Gymnastique d'algorithme 19 Sous-chaîne sans répétition
Gymnastique algorithmique 24 Inverser une liste liée
Gymnastique d'algorithme 20 paires avec somme cible
Trier
Gymnastique algorithmique 22 Mise au carré d'un tableau trié
Gymnastique algorithmique 24 Milieu de la liste liée