Ketahui cara menggunakan fungsi Isih Python untuk mengisih senarai, tatasusunan, kamus, dll menggunakan pelbagai kaedah dan algoritma pengisihan dalam Python:
Isih ialah teknik yang digunakan untuk mengisih data dalam susunan turutan sama ada dalam tertib menaik atau menurun.
Kebanyakan masa data projek besar tidak disusun dalam susunan yang betul dan ini menimbulkan masalah semasa mengakses dan mengambil data yang diperlukan dengan cekap.
Teknik pengisihan digunakan untuk menyelesaikan masalah ini. Python menyediakan pelbagai teknik pengisihan contohnya, Isih gelembung, Isih Sisipan, Isihan Gabung, Isih Pantas, dsb.
Dalam tutorial ini, kita akan memahami cara pengisihan berfungsi dalam Python dengan menggunakan pelbagai algoritma.
Isih Python
Sintaks Isih Python
Untuk melaksanakan pengisihan, Python menyediakan fungsi terbina dalam iaitu fungsi " sort() ". Ia digunakan untuk mengisih elemen data senarai dalam tertib menaik atau dalam tertib menurun.
Mari kita fahami konsep ini dengan contoh.
Contoh 1:
``` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort() print( “ List in ascending order: ”, a ) ```
Output:
Dalam contoh ini, senarai tidak tertib yang diberikan diisih ke dalam tertib menaik dengan menggunakan fungsi “ sort( ) ” .
Contoh 2:
``` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort( reverse = True ) print( “ List in descending order: ”, a ) ```
Output
Dalam contoh di atas, senarai tidak tertib yang diberikan diisih dalam susunan terbalik menggunakan fungsi “ sort( reverse = True ) ”.
Masatempat Isih gelembung O(n) O(n2) O(n2) O(1) Ya Ya Isih sisipan O(n) O(n2) O(n2) O(1) Ya Ya Isih cepat O(n log(n)) O(n log(n)) O(n2) O(N) Tidak Ya Gabung isihan O(n log(n)) O(n log(n)) O(n log(n)) O(N) Ya Tidak Isihan timbunan O(n log (n)) O(n log(n)) O(n log(n)) O(1) Tidak Ya
Dalam jadual perbandingan di atas “ O “ ialah notasi Oh Besar yang dijelaskan di atas manakala “ n ” dan “ N ” bermaksud saiz input .
Soalan Lazim
S #1) Apakah jenis () dalam Python?
Jawapan: Dalam Python sort() ialah fungsi yang digunakan untuk mengisih senarai atau tatasusunan dalam susunan tertentu. Fungsi ini memudahkan proses pengisihan semasa mengerjakan projek besar. Ia sangat membantu pembangun.
S #2) Bagaimanakah anda mengisih dalam Python?
Jawapan: Python menyediakan pelbagai teknik pengisihan yang digunakan untuk mengisih elemen. Contohnya, Isih cepat, Isih Gabung, Isih Buih, Isih Sisipan, dsb. Semua teknik isihan adalah cekap dan mudah difahami.
S #3) Bagaimanakah Python jenis () kerja?
Jawapan: Isih()fungsi mengambil tatasusunan yang diberikan sebagai input daripada pengguna dan menyusunnya dalam susunan tertentu menggunakan algoritma pengisihan. Pemilihan algoritma bergantung pada pilihan pengguna. Pengguna boleh menggunakan Isih Pantas, Isih Gabung, Isih Buih, Isih Sisipan, dll bergantung pada keperluan pengguna.
Kesimpulan
Dalam tutorial di atas, kita membincangkan teknik isihan dalam Python bersama-sama dengan teknik pengisihan umum.
- Isih Buih
- Isih Sisipan
- Isih Pantas
Kami mengetahui tentang kerumitan masa dan kelebihannya & keburukan. Kami juga membandingkan semua teknik di atas.
Kerumitan Algoritma IsihKerumitan Masa ialah jumlah masa yang diambil oleh komputer untuk menjalankan algoritma tertentu. Ia mempunyai tiga jenis kes kerumitan masa.
- Kes Terburuk: Masa maksimum yang diambil oleh komputer untuk menjalankan program.
- Kes Purata: Masa yang diambil antara minimum dan maksimum oleh komputer untuk menjalankan program.
- Kes Terbaik: Masa minimum yang diambil oleh komputer untuk menjalankan program. Ia adalah kes terbaik kerumitan masa.
Notasi Kerumitan
Notasi Oh Besar, O: Notasi oh besar ialah cara rasmi untuk menyampaikan sempadan atas masa menjalankan algoritma. Ia digunakan untuk mengukur kerumitan masa terburuk atau kita katakan jumlah masa terbesar yang diambil oleh algoritma untuk diselesaikan.
Notasi omega besar, : Notasi omega besar ialah cara rasmi untuk menyampaikan had terendah masa berjalan algoritma. Ia digunakan untuk mengukur kerumitan masa kes terbaik atau kita katakan jumlah masa yang sangat baik yang diambil oleh algoritma.
Notasi Theta, : Notasi Theta ialah cara rasmi untuk menyampaikan kedua-dua sempadan iaitu lebih rendah dan atas masa yang diambil oleh algoritma untuk diselesaikan.
Kaedah Isih dalam Python
Isih Buih
Isih Buih ialah cara paling mudah untuk mengisih data yang menggunakan teknik brute force. Ia akan berulang kepada setiap elemen data dan membandingkannya dengan elemen lainuntuk memberikan pengguna data yang diisih.
Mari kita ambil contoh untuk memahami teknik ini:
- Kami disediakan dengan tatasusunan yang mempunyai elemen “ 10, 40, 7, 3, 15 ”. Sekarang, kita perlu menyusun tatasusunan ini dalam susunan menaik menggunakan teknik Bubble sort dalam Python.
- Langkah pertama ialah menyusun tatasusunan dalam susunan yang diberikan.
- Dalam " Lelaran 1 ", kami membandingkan elemen pertama tatasusunan dengan elemen lain satu demi satu.
- Anak panah merah menerangkan perbandingan unsur pertama dengan unsur tatasusunan yang lain.
- Jika anda perasan “ 10 ” lebih kecil daripada “ 40 ” jadi, ia kekal pada kedudukan yang sama tempat tetapi elemen seterusnya " 7 " adalah lebih kecil daripada " 10 ". Oleh itu, ia akan diganti dan berada di tempat pertama.
- Proses di atas akan dilakukan berulang kali untuk mengisih elemen.
-
- Dalam “ Lelaran 2 ” elemen kedua semakin dibandingkan dengan elemen tatasusunan yang lain.
- Jika elemen yang dibandingkan itu kecil maka, ia akan diganti, jika tidak, ia akan kekal di tempat yang sama.
-
- Dalam “ Lelaran 3 “ elemen ketiga semakin dibandingkan dengan unsur tatasusunan yang lain.
-
- Pada yang terakhir " Lelaran 4 " elemen terakhir kedua semakin dibandingkan dengan elemen lain tatasusunan.
- Dalamlangkah ini tatasusunan diisih dalam tertib menaik.
Program untuk isihan Buih
``` def Bubble_Sort(unsorted_list): for i in range(0,len(unsorted_list)-1): for j in range(len(unsorted_list)-1): if(unsorted_list[j]>unsorted_list[j+1]): temp_storage = unsorted_list[j] unsorted_list[j] = unsorted_list[j+1] unsorted_list[j+1] = temp_storage return unsorted_list unsorted_list = [5, 3, 8, 6, 7, 2] print("Unsorted List: ", unsorted_list) print("Sorted List using Bubble Sort Technique: ", Bubble_Sort(unsorted_list)) ```
Output
Kerumitan Masa Isih Buih
- Kes Terburuk: Kerumitan masa yang paling teruk untuk isihan gelembung ialah O( n 2).
- Kes Purata: Purata kerumitan masa untuk isihan gelembung ialah O( n 2).
- Kes Terbaik: Kerumitan masa terbaik untuk isihan gelembung ialah O(n).
Kelebihan
- Kebanyakannya digunakan dan mudah dilaksanakan.
- Kami boleh menukar elemen data tanpa menggunakan storan jangka pendek.
- Ia memerlukan kurang ruang.
Kelemahan
- Ia tidak berfungsi dengan baik semasa berurusan dengan sejumlah besar elemen data yang besar.
- Ia memerlukan n 2 langkah untuk setiap nombor "n" elemen data untuk diisih.
- Ia tidak begitu baik untuk aplikasi dunia sebenar.
Sisipan Isih
Isihan sisipan ialah teknik pengisihan yang mudah dan ringkas yang berfungsi sama seperti mengisih kad permainan. Isih sisipan mengisih elemen dengan membandingkan setiap elemen satu demi satu dengan yang lain. Elemen dipilih dan ditukar dengan elemen lain jika elemen lebih besar atau lebih kecil daripada elemen lain.
Mari kita ambil contoh
- Kami disediakan dengan tatasusunan yang mempunyai elemen " 100, 50, 30, 40, 10 ".
- Mula-mula, kami menyusun tatasusunan dan mula membandingkania.
- Dalam langkah pertama “ 100 ” dibandingkan dengan elemen kedua “ 50 ”. “ 50 ” ditukar dengan “ 100 ” kerana ia lebih besar.
- Dalam langkah kedua, sekali lagi elemen kedua “ 100 ” dibandingkan dengan elemen ketiga “ 30 ” dan ditukar.
- Kini, jika anda perasan “ 30 ” berada di tempat pertama kerana ia sekali lagi lebih kecil daripada “ 50 ”.
- Perbandingan akan berlaku sehingga elemen terakhir tatasusunan dan pada akhirnya, kita akan mendapat data diisih.
Program untuk isihan Sisipan
``` def InsertionSort(array): for i in range(1, len(array)): key_value = array[i] j = i-1 while j >= 0 and key_value array[j] : array[j + 1] = array[j] j -= 1 array[j + 1] = key_value array = [11, 10, 12, 4, 5] print("The unsorted array: ", array) InsertionSort(array) print ("The sorted array using the Insertion Sort: ") for i in range(len(array)): print (array[i]) ```
Output
Kerumitan Masa Isihan Sisipan
- Kes Terburuk: Kerumitan masa terburuk untuk Isihan Sisipan ialah O( n 2).
- Purata Kes: Purata kerumitan masa untuk isihan Sisipan ialah O( n 2).
- Kes Terbaik: Kerumitan masa terbaik untuk Isihan Sisipan ialah O(n).
Kelebihan
- Ianya mudah dan mudah untuk dilaksanakan.
- Ia berfungsi dengan baik semasa berurusan dengan sebilangan kecil elemen data.
- Ia tidak memerlukan lebih banyak ruang untuk pelaksanaannya.
Kelemahan
- Tidak membantu untuk mengisih sejumlah besar elemen data.
- Jika dibandingkan dengan teknik pengisihan lain, ia tidak berfungsi dengan baik.
Isih Gabung
Kaedah isihan ini menggunakan kaedah bahagi dan takluk untuk mengisih unsur dalam susunan tertentu. Semasa menyusun dengan bantuan merge sort, theelemen dibahagikan kepada separuh dan kemudian, ia akan diisih. Selepas mengisih semua bahagian, sekali lagi elemen dicantum untuk membentuk susunan yang sempurna.
Mari kita ambil contoh untuk memahami teknik ini
- Kami dibekalkan dengan tatasusunan “ 7, 3, 40, 10, 20, 15, 6, 5 ”. Tatasusunan mengandungi 7 elemen. Jika kita membahagikannya kepada separuh ( 0 + 7 / 2 = 3 ).
- Dalam langkah kedua, anda akan melihat bahawa elemen dibahagikan kepada dua bahagian. Setiap satu mempunyai 4 elemen di dalamnya.
- Seterusnya, elemen dibahagikan sekali lagi dan mempunyai 2 elemen setiap satu.
- Proses ini akan diteruskan sehingga hanya satu elemen hadir dalam tatasusunan. Rujuk langkah no. 4 dalam gambar.
- Sekarang, kita akan mengisih elemen dan mula menyertainya sebagaimana kita telah dibahagikan.
- Dalam langkah no. 5 jika anda perasan 7 lebih besar daripada 3, jadi kami akan menukarnya dan menyertainya dalam langkah seterusnya dan begitu juga sebaliknya.
- Pada akhirnya, anda akan perasan bahawa tatasusunan kami semakin disusun dalam tertib menaik.
Program untuk Isih Gabungan
``` def MergeSort(arr): if len(arr) > 1: middle = len(arr)//2 L = arr[:middle] R = arr[middle:] MergeSort(L) MergeSort(R) i = j = k = 0 while i len(L) and j len(R): if L[i] R[j]: arr[k] = L[i] i += 1 else: arr[k] = R[j] j += 1 k += 1 while i len(L): arr[k] = L[i] i += 1 k += 1 while j len(R): arr[k] = R[j] j += 1 k += 1 def PrintSortedList(arr): for i in range(len(arr)): print(arr[i],) print() arr = [12, 11, 13, 5, 6, 7] print("Given array is", end="\n") PrintSortedList(arr) MergeSort(arr) print("Sorted array is: ", end="\n") PrintSortedList(arr) ```
Output
Kerumitan Masa Isihan Gabungan
- Kes Terburuk: Kerumitan masa yang paling teruk untuk isihan gabungan ialah O( n log( n )).
- Kes Purata: Purata kerumitan masa untuk isihan gabungan ialah O( n log( n )).
- Kes Terbaik: Kerumitan masa terbaik untuk isihan gabungan ialah O( n log( n )).
Kelebihan
- Saiz fail tidak penting untuk teknik pengisihan ini.
- Teknik ini bagus untuk data yang biasanya diakses dalam susunan turutan. Sebagai contoh, senarai terpaut, pemacu pita, dsb.
Kelemahan
- Ia memerlukan lebih banyak ruang jika dibandingkan dengan yang lain teknik pengisihan.
- Ia agak kurang cekap berbanding yang lain.
Isih cepat
Isih cepat sekali lagi menggunakan kaedah bahagi dan takluk untuk mengisih unsur-unsur Senarai atau tatasusunan. Ia menyasarkan elemen pangsi dan mengisih elemen mengikut elemen pangsi yang dipilih.
Sebagai contoh
- Kami disediakan dengan tatasusunan yang mempunyai elemen “ 1 ,8,3,9,4,5,7 ”.
- Mari kita anggap “ 7 ” sebagai elemen perintis.
- Sekarang kita akan membahagi tatasusunan sedemikian rupa sehingga sebelah kiri mengandungi elemen yang lebih kecil daripada elemen pangsi " 7 " dan bahagian kanan mengandungi elemen yang lebih besar daripada elemen pangsi " 7 ".
- Kami kini mempunyai dua tatasusunan " 1,3,4,5 ” dan “ 8, 9 ”.
- Sekali lagi, kita perlu membahagikan kedua-dua tatasusunan sama seperti yang kita lakukan di atas. Satu-satunya perbezaan ialah elemen pangsi ditukar.
- Kita perlu membahagikan tatasusunan sehingga kita mendapat elemen tunggal dalam tatasusunan.
- Pada akhirnya, kumpulkan semua elemen pangsi dalam urutan dari kiri ke kanan dan anda akan mendapat yang diisihtatasusunan.
Program untuk Isih Pantas
``` def Array_Partition( arr, lowest, highest ): i = ( lowest-1 ) pivot_element = arr[ highest ] for j in range( lowest, highest ): if arr[ j ] = pivot_element: i = i+1 arr[ i ], arr[ j ] = arr[ j ], arr[ i ] arr[ i+1 ], arr[ highest ] = arr[ highest ], arr[ i+1 ] return ( i+1 ) def QuickSort( arr, lowest, highest ): if len( arr ) == 1: return arr if lowest highest: pi = Array_Partition( arr, lowest, highest ) QuickSort( arr, lowest, pi-1 ) QuickSort( arr, pi+1, highest ) arr = [ 9, 6, 7, 8, 0, 4 ] n = len( arr ) print( " Unsorted array: ", arr ) QuickSort( arr, 0, n-1 ) print( " Sorted array using Quick Sort: " ) for i in range( n ): print( " %d " % arr[ i ] ) ```
Output
Kerumitan Masa Isih Pantas
- Kes Terburuk: Kerumitan masa terburuk untuk Isih Pantas ialah O( n 2).
- Purata Kes: Purata kerumitan masa untuk Isih Pantas ialah O( n log( n ) ).
- Kes Terbaik: Kerumitan masa terbaik untuk Isih Pantas ialah O( n log( n )).
Kelebihan
- Ia dikenali sebagai algoritma pengisihan terbaik dalam Python.
- Ia berguna semasa mengendalikan sejumlah besar data.
- Ia tidak memerlukan ruang tambahan.
Kelemahan
- Kerumitan kes terburuknya adalah serupa dengan kerumitan jenis gelembung dan isihan sisipan.
- Kaedah isihan ini tidak berguna apabila kita sudah mempunyai senarai yang diisih.
Isih timbunan
Isihan timbunan ialah versi lanjutan pepohon carian Binari . Dalam isihan timbunan, elemen terbesar tatasusunan diletakkan pada akar pokok sentiasa dan kemudian, berbanding dengan akar dengan nod daun.
Contohnya:
- Kami disediakan dengan tatasusunan yang mempunyai elemen “ 40, 100, 30, 50, 10 ”.
- Dalam “ langkah 1 ” kami membuat pokok mengikut kehadiran unsur dalam tatasusunan.
- Dalam “ langkah 2 ” kita sedang membuat timbunan maksimum iaitu untuk menyusun unsur dalam susunan menurun. Elemen terbesar akanberada di bahagian atas (akar) dan unsur terkecil berada di bahagian bawah (nod daun). Tatasusunan yang diberikan menjadi “ 100, 50, 30, 40, 10 ”.
- Dalam “ langkah 3 ” , kita sedang membuat timbunan minimum supaya kita boleh mencari elemen minimum tatasusunan. Dengan melakukan ini, kami mendapat unsur maksimum dan minimum.
- Dalam “ langkah 4 ” dengan melakukan langkah yang sama kami mendapat tatasusunan yang diisih.
Program untuk isihan Timbunan
``` def HeapSortify( arr, n, i ): larger_element = i left = 2 * i + 1 right = 2 * i + 2 if left n and arr[ larger_element ] arr[ left ]: larger_element = left if right n and arr[ larger_element ] arr[ right ]: larger_element = right if larger_element != i: arr[ i ], arr[ larger_element ] = arr[ larger_element ], arr[ i ] HeapSortify( arr, n, larger_element ) def HeapSort( arr ): n = len( arr ) for i in range( n//2 - 1, -1, -1 ): HeapSortify( arr, n, i ) for i in range( n-1, 0, -1 ): arr[ i ], arr[ 0 ] = arr[ 0 ], arr[ i ] HeapSortify( arr, i, 0 ) arr = [ 11, 10, 12, 4, 5, 6 ] print( " The unsorted array is: ", arr ) HeapSort( arr ) n = len( arr ) print( " The sorted array sorted by the Heap Sort: " ) for i in range( n ): print( arr[ i ] ) ```
Output
Kerumitan Masa Isih Timbunan
- Kes Terburuk: Kerumitan masa yang paling teruk untuk Isih Timbunan ialah O( n log( n )).
- Purata Kes: Purata kerumitan masa untuk Isihan Timbunan ialah O( n log( n )).
- Kes Terbaik: Kerumitan masa terbaik untuk Isihan Timbunan ialahO( n log( n )).
Kelebihan
- Ia kebanyakannya digunakan kerana produktivitinya.
- Ia boleh dilaksanakan sebagai algoritma di tempat.
- Ia tidak memerlukan storan yang besar.
Kelemahan
- Memerlukan ruang untuk mengisih unsur.
- Ia menjadikan pokok untuk mengisih unsur.
Perbandingan Antara Teknik Isih
Kaedah Isih | Kerumitan masa kes terbaik | Purata kerumitan masa kes | Kerumitan masa kes terburuk | Kerumitan ruang | Kestabilan | Dalam - |
---|