Tri des formes d'onde des tableaux à l'aide de Python

Dans cet article, nous apprendrons un programme Python pour le tri des formes d'onde d'un tableau.

Supposons que nous ayons un tableau d'entrée non trié. Nous allons maintenant trier le tableau d'entrée sous forme de forme d'onde. Si le tableau 'arr [0..n-1]' satisfait à arr [0] >= arr [1] = arr [3] = ...., le tableau est trié en forme d'onde.

Méthodes utilisées

Voici les différentes méthodes utilisées pour accomplir cette tâche &miinus;

• Utilisez la fonction sort() intégrée

• Sans utiliser les fonctions intégrées

Méthode 1 : Utilisation de la fonction sort() intégrée

Algorithme (étapes)

Voici les algorithmes/étapes à suivre pour effectuer la tâche souhaitée −

.

• Créez une fonction pour trier le tableau d'entrée par forme d'onde, en acceptant le tableau d'entrée et la longueur du tableau comme paramètres.

• Utilisez la fonction sort() (trie la liste par ordre croissant/décroissant) pour trier le tableau d'entrée par ordre croissant.

• Utilisez la boucle for pour parcourir alternativement jusqu'à la longueur du tableau (étape = 2)

• Échangez les éléments adjacents, c'est-à-dire l'actuel et le suivant à l'aide de l'opérateur ','.

• Créez une variable pour stocker le tableau d'entrée.

• Utilisez la fonction len() (qui renvoie le nombre d'éléments dans l'objet) pour obtenir la longueur du tableau d'entrée.

• Appelez la fonction sortingInWaveform() définie ci-dessus en passant le tableau d'entrée et la longueur du tableau comme arguments

• Utilisez for loop pour parcourir tous les éléments du tableau

• Imprimez l'élément actuel d'un tableau.

Exemple

Le programme suivant trie le tableau d'entrée sous forme d'onde à l'aide de la fonction python Built-in sort() −

# creating a function to sort the array in waveform by accepting
# the input array, array length as arguments
def sortingInWaveform(inputArray, arrayLength):
   # sorting the input array in ascending order using the sort() function
   inputArray.sort()
   # travsersing till the array length alternatively(step=2)
   for k in range(0, arrayLength-1, 2):
         # swapping the adjacent elements i.e, current and it's next
         inputArray[k], inputArray[k+1] = inputArray[k+1], inputArray[k]
# input array
inputArray = [12, 45, 15, 4, 6, 70, 68, 3, 25]
# getting the length of the input array
arrayLength = len(inputArray)
# printing the given array/list
print("The Given list is:", inputArray)
# calling the above defined sortingInWaveform() function by
# passing input array, length of the array as arguments
sortingInWaveform(inputArray, arrayLength)
print("The Result Array after sorting in wave form is:")
# traversing through all the elements of the array
for k in range(0, arrayLength):
   # printing the current element of the array/list
      print(inputArray[k], end=" ")

Sortie

Lors de l'exécution, le programme ci-dessus générera le résultat suivant &miinus;

The Given list is: [12, 45, 15, 4, 6, 70, 68, 3, 25]
The Result Array after sorting in wave form is:
4 3 12 6 25 15 68 45 70 

Complexité temporelle − O(nLogn).

Ici, le tableau donné a été trié à l'aide de la fonction de tri, qui a généralement une complexité temporelle O(NlogN).

Si vous appliquez l'algorithme de tri O(nLogn), tel que Merge Sort, Heap Sort, etc., la complexité temporelle de la méthode donnée ci-dessus est O(nLogn).

Méthode 2 : Utilisez une seule boucle

Algorithme (étapes)

Voici les algorithmes/étapes à suivre pour effectuer la tâche souhaitée −

.

• Utilisez la boucle for pour parcourir tous les éléments d'index pairs en passant 0, la longueur du tableau et la valeur du pas comme arguments

• Utilisez l'instruction if conditionnelle pour vérifier si l'élément d'index pair actuel est plus petit que l'élément précédent.

• Échangez les éléments si la condition est vrai.

• Utilisez if instruction conditionnelle pour vérifier si l'élément d'index pair actuel est inférieur à l'élément suivant.

• Échangez les éléments si la condition est vrai.

• Appelez la fonction sortingInWaveform() définie ci-dessus en passant le tableau d'entrée et la longueur du tableau comme arguments

• Utilisez for loop pour parcourir les éléments du tableau.

• Imprimez l'élément correspondant du tableau/liste.

Exemple

Le programme suivant trie le tableau d'entrée sous forme d'onde en utilisant une seule boucle for et sans fonctions intégrées −

# creating a function to sort the array in waveform by accepting
# the input array, array length as arguments
def sortingInWaveform(inputArray, arrayLength):
   # traversing through all the even index elements
   for p in range(0, arrayLength, 2):
      # checking whether the current even index element
      # is smaller than the previous
      if (p > 0 and inputArray[p] < inputArray[p-1]):
         # swapping the elements if the condition is true
            inputArray[p], inputArray[p-1] = inputArray[p-1], inputArray[p]
            # checking whether the current even index element
            # is smaller than the next element
      if (p < arrayLength-1 and inputArray[p] < inputArray[p+1]):
         # swapping the elements if the condition is true
            inputArray[p], inputArray[p+1] = inputArray[p+1], inputArray[p]
# input array
inputArray = [12, 45, 15, 4, 6, 70, 68, 3, 25]
# getting the length of the input array
arrayLength = len(inputArray)
print("The Given list is:", inputArray)
# calling the above defined sortingInWaveform() function by
# passing input array, length of the array as arguments
sortingInWaveform(inputArray, arrayLength)
print("The Result Array after sorting in wave form is:")
# traversing through all the elements of the array
for k in range(0, arrayLength):
   # printing the current element
   print(inputArray[k], end=" ")

Sortie

Après avoir exécuté le programme ci-dessus, la sortie suivante sera générée -

The Given list is: [12, 45, 15, 4, 6, 70, 68, 3, 25]
The Result Array after sorting in wave form is:
45 12 15 4 70 6 68 3 25

Complexité temporelle - O(n).

Ici, nous n'avons pas utilisé la fonction de tri ; à la place, nous avons simplement utilisé la boucle for pour parcourir les éléments du tableau donné, qui, en moyenne, a une complexité temporelle O(N).

Conclusion

Dans cet article, nous avons appris à trier un tableau donné de formes d'onde en utilisant deux méthodes différentes. Nous avons utilisé une nouvelle logique dont la complexité temporelle est réduite de O(log N) par rapport à la première méthode. Dans de nombreux cas, ces types d’algorithmes permettent de réduire la complexité temporelle et de mettre en œuvre des solutions efficaces.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!