Pengisihan tatasusunan bentuk gelombang menggunakan Python

Dalam artikel ini, kita akan mempelajari program Python untuk pengisihan bentuk gelombang tatasusunan.

Andaikan kita mempunyai tatasusunan input yang tidak diisih. Kami kini akan menyusun tatasusunan input dalam bentuk gelombang. Jika tatasusunan 'arr [0..n-1]' memenuhi arr [0] >= arr [1] = arr [3] = . ...., tatasusunan diisih ke dalam bentuk gelombang.

Kaedah Digunakan

Berikut ialah pelbagai kaedah yang digunakan untuk menyelesaikan tugasan ini &miinus;

• Gunakan fungsi sort() terbina dalam

• Tanpa Menggunakan fungsi Terbina dalam

Kaedah 1: Menggunakan fungsi sort() Terbina dalam

Algoritma (langkah)

Berikut ialah Algoritma/langkah yang perlu diikuti untuk melaksanakan tugasan yang dikehendaki −

• Buat fungsi untuk mengisih tatasusunan input mengikut bentuk gelombang, menerima tatasusunan input dan panjang tatasusunan sebagai parameter.

• Gunakan fungsi sort()(isih senarai dalam tertib menaik/menurun ) untuk mengisih tatasusunan input dalam tertib menaik.

• Gunakan untuk gelung untuk melintasi sehingga panjang tatasusunan secara alternatif(langkah=2)

• Tukar elemen bersebelahan iaitu semasa dan seterusnya menggunakan operator ‘,’.

• Buat pembolehubah untuk menyimpan tatasusunan input.

• Gunakan fungsi len() (yang mengembalikan bilangan item dalam objek) untuk mendapatkan panjang tatasusunan input.

• Panggil fungsi sortingInWaveform() yang ditakrifkan di atas dengan menghantar tatasusunan input dan panjang tatasusunan sebagai argumen

• Gunakan untuk gelung untuk lelaran melalui semua elemen tatasusunan

• Cetak elemen semasa tatasusunan.

Contoh

Atur cara berikut mengisih tatasusunan input dalam bentuk gelombang menggunakan fungsi isihan() terbina dalam python −

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

Output

Semasa pelaksanaan, program di atas akan menjana output berikut &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 

Kerumitan masa − O(nLogn).

Di sini, tatasusunan yang diberikan telah diisih menggunakan fungsi isihan, yang biasanya mempunyai kerumitan masa O(NlogN).

Jika anda menggunakan algoritma pengisihan O(nLogn), seperti Isih Gabung, Isih Timbunan, dsb., kerumitan masa bagi kaedah yang diberikan di atas ialah O(nLogn).

Kaedah 2: Gunakan hanya satu gelung

Algoritma (langkah)

Berikut ialah Algoritma/langkah yang perlu diikuti untuk melaksanakan tugasan yang dikehendaki −

• Gunakan for gelung untuk merentasi semua elemen indeks genap dengan menghantar 0, panjang tatasusunan dan nilai langkah sebagai argumen

• Gunakan penyataan jika bersyarat untuk menyemak sama ada elemen indeks genap semasa lebih kecil daripada elemen sebelumnya.

• Tukar elemen jika syaratnya benar.

• Gunakan jika pernyataan bersyarat untuk menyemak sama ada elemen indeks genap semasa adalah kurang daripada elemen seterusnya.

• Tukar elemen jika syaratnya benar.

• Panggil fungsi sortingInWaveform() yang ditakrifkan di atas dengan menghantar tatasusunan input dan panjang tatasusunan sebagai argumen

• Gunakan untuk gelung untuk mengulangi elemen tatasusunan.

• Cetak elemen tatasusunan/senarai yang sepadan.

Contoh

Atur cara berikut mengisih tatasusunan input dalam bentuk gelombang menggunakan hanya satu untuk gelung dan tanpa fungsi Terbina dalam −

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

Output

Selepas melaksanakan program di atas, output berikut akan dihasilkan -

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

Kerumitan masa - O(n).

Di sini, kami tidak menggunakan fungsi isihan sebaliknya, kami hanya menggunakan gelung for untuk melelaran melalui elemen tatasusunan yang diberikan, yang, secara purata, mempunyai kerumitan masa O(N).

Kesimpulan

Dalam artikel ini, kami mempelajari cara mengisih tatasusunan bentuk gelombang menggunakan dua kaedah berbeza. Kami menggunakan logik baharu yang kerumitan masanya dikurangkan sebanyak O(log N) berbanding kaedah pertama. Dalam kebanyakan kes, jenis algoritma ini membantu mengurangkan kerumitan masa dan melaksanakan penyelesaian yang cekap.

Atas ialah kandungan terperinci Pengisihan tatasusunan bentuk gelombang menggunakan Python. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!