Wellenformsortierung von Arrays mit Python

In diesem Artikel lernen wir ein Python-Programm zur Wellenformsortierung eines Arrays kennen.

Angenommen, wir haben ein unsortiertes Eingabearray. Wir werden nun das Eingabearray nach Wellenform sortieren. Wenn das Array 'arr [0..n-1]' arr [0] >= arr [1] = arr [3] = erfüllt . ...., das Array wird in eine Wellenform sortiert.

Verwendete Methoden

Hier sind die verschiedenen Methoden, mit denen diese Aufgabe erledigt wird &miinus;

• Verwenden Sie die integrierte Funktion sort()

• Ohne Verwendung integrierter Funktionen

Methode 1: Verwendung der integrierten Funktion sort()

Algorithmus (Schritte)

Im Folgenden sind die Algorithmen/Schritte aufgeführt, die zur Ausführung der gewünschten Aufgabe befolgt werden müssen

• Erstellen Sie eine Funktion zum Sortieren des Eingabearrays nach Wellenform und akzeptieren Sie das Eingabearray und die Arraylänge als Parameter.

• Verwenden Sie die Funktion

  sort() (sortiert die Liste in aufsteigender/absteigender Reihenfolge), um das Eingabearray in aufsteigender Reihenfolge zu sortieren.

• Verwenden Sie alternativ die

  for-Schleife, um bis zur Array-Länge zu durchlaufen (Schritt=2)

• Vertauschen Sie die benachbarten Elemente, d. h. das aktuelle und das nächste, mit dem Operator „,“.

• Erstellen Sie eine Variable zum Speichern des Eingabearrays.

• Verwenden Sie die Funktion

  len() (die die Anzahl der Elemente im Objekt zurückgibt), um die Länge des Eingabearrays zu ermitteln.

• Rufen Sie die oben definierte Funktion

  sortingInWaveform() auf, indem Sie das Eingabearray und die Länge des Arrays als Argumente übergeben

• Verwenden Sie die

  for-Schleife, um alle Elemente des Arrays zu durchlaufen

• Drucken Sie das aktuelle Element eines Arrays.

Beispiel

Das folgende Programm sortiert das Eingabearray in Wellenform mithilfe der in Python integrierten Funktion 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=" ")

Ausgabe

Bei der Ausführung generiert das obige Programm die folgende Ausgabe &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 

Zeitkomplexität − O(nLogn).

Hier wurde das angegebene Array mithilfe der Sortierfunktion sortiert, die normalerweise eine Zeitkomplexität von O(NlogN) aufweist.

Wenn Sie einen O(nLogn)-Sortieralgorithmus wie

Merge Sort, Heap Sort usw. anwenden, beträgt die zeitliche Komplexität der oben angegebenen Methode O(nLogn).

Methode 2: Verwenden Sie nur eine Schleife

Algorithmus (Schritte)

Im Folgenden sind die Algorithmen/Schritte aufgeführt, die zur Ausführung der gewünschten Aufgabe befolgt werden müssen

Verwenden Sie die
• for-Schleife

  , um alle geraden Indexelemente zu durchlaufen, indem Sie 0, Array-Länge und Schrittwert als Argumente übergeben

Verwenden Sie die Anweisung
• if bedingt

  , um zu prüfen, ob das aktuelle gerade Indexelement kleiner als das vorherige Element ist.

Tauschen Sie die Elemente, wenn die Bedingung
• wahr ist.

Verwenden Sie die
• if-Bedingungsanweisung

  , um zu überprüfen, ob das aktuelle gerade Indexelement kleiner als das nächste Element ist.

Tauschen Sie die Elemente, wenn die Bedingung
• wahr ist.

Rufen Sie die oben definierte Funktion
• sortingInWaveform()

  auf, indem Sie das Eingabearray und die Länge des Arrays als Argumente übergeben

Verwenden Sie die
• for-Schleife

  , um die Elemente des Arrays zu durchlaufen.

Drucken Sie das entsprechende Element des Arrays/der Liste aus.
Beispiel

Das folgende Programm sortiert das Eingabearray in Wellenform mit nur einer for-Schleife und ohne integrierte Funktionen −

# 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=" ")

Ausgabe

Nachdem das obige Programm ausgeführt wurde, wird die folgende Ausgabe generiert -

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

Zeitkomplexität

- O(n). Hier haben wir stattdessen nicht die Sortierfunktion verwendet, sondern nur die for-Schleife, um die Elemente des angegebenen Arrays zu durchlaufen, das im Durchschnitt eine Zeitkomplexität von O(N) aufweist.

Fazit

In diesem Artikel haben wir gelernt, wie man ein bestimmtes Array von Wellenformen mit zwei verschiedenen Methoden sortiert. Wir haben eine neue Logik verwendet, deren Zeitkomplexität im Vergleich zur ersten Methode um O(log N) reduziert ist. In vielen Fällen tragen solche Algorithmen dazu bei, die Zeitkomplexität zu reduzieren und effiziente Lösungen zu implementieren.

Das obige ist der detaillierte Inhalt vonWellenformsortierung von Arrays mit Python. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!