Pelajari cara menggunakan fungsi Python Sort untuk mengurutkan daftar, array, kamus, dll menggunakan berbagai metode dan algoritma pengurutan di Python:
Pengurutan adalah teknik yang digunakan untuk mengurutkan data dalam urutan tertentu, baik dalam urutan naik maupun turun.
Seringkali data dari proyek-proyek besar tidak diatur dalam urutan yang benar dan hal ini menimbulkan masalah saat mengakses dan mengambil data yang dibutuhkan secara efisien.
Teknik pengurutan digunakan untuk mengatasi masalah ini. Python menyediakan berbagai teknik pengurutan misalnya, Pengurutan gelembung, Pengurutan penyisipan, Pengurutan gabungan, Pengurutan cepat, dll.
Dalam tutorial ini, kita akan memahami cara kerja pengurutan di Python dengan menggunakan berbagai algoritma.
Urutan Python
Sintaks Pengurutan Python
Untuk melakukan pengurutan, Python menyediakan fungsi bawaan yaitu fungsi "sort ()". Fungsi ini digunakan untuk mengurutkan elemen data dari sebuah daftar dalam urutan menaik atau menurun.
Mari kita pahami konsep ini dengan sebuah contoh.
Contoh 1:
``` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort() print( "Daftar dalam urutan menaik: ", a ) ```
Keluaran:
Dalam contoh ini, daftar tak berurutan yang diberikan diurutkan ke dalam urutan menaik dengan menggunakan fungsi " sort ( ) ".
Contoh 2:
``` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort( reverse = True ) print( "Daftar dalam urutan menurun: ", a ) ```
Keluaran
Pada contoh di atas, daftar tak berurutan yang diberikan diurutkan dalam urutan terbalik menggunakan fungsi "sort( reverse = True )".
Kompleksitas Waktu Algoritma Penyortiran
Kompleksitas Waktu adalah jumlah waktu yang dibutuhkan oleh komputer untuk menjalankan algoritme tertentu, dan ada tiga jenis kasus kompleksitas waktu.
- Kasus terburuk: Waktu maksimum yang dibutuhkan oleh komputer untuk menjalankan program.
- Kasus rata-rata: Waktu yang dibutuhkan antara minimum dan maksimum oleh komputer untuk menjalankan program.
- Kasus terbaik: Waktu minimum yang dibutuhkan oleh komputer untuk menjalankan program. Ini adalah kasus terbaik dari kompleksitas waktu.
Notasi Kompleksitas
Notasi Oh Besar, O: Notasi big oh adalah cara resmi untuk menyampaikan batas atas waktu berjalan algoritma. Notasi ini digunakan untuk mengukur kompleksitas waktu terburuk atau dengan kata lain, jumlah waktu terbesar yang dibutuhkan algoritma untuk menyelesaikannya.
Notasi omega besar, : Notasi omega besar adalah cara resmi untuk menyampaikan batas terendah dari waktu berjalannya algoritme. Notasi ini digunakan untuk mengukur kompleksitas waktu kasus terbaik atau bisa dikatakan jumlah waktu yang sangat baik yang dibutuhkan oleh algoritme.
Notasi Theta, : Notasi Theta adalah cara resmi untuk menyampaikan kedua batas, yaitu batas bawah dan batas atas dari waktu yang dibutuhkan oleh algoritme untuk menyelesaikannya.
Metode Pengurutan dalam Python
Sortir Gelembung
Pengurutan gelembung adalah cara paling sederhana untuk mengurutkan data yang menggunakan teknik brute force, yang akan mengulang ke setiap elemen data dan membandingkannya dengan elemen lain untuk memberikan data yang telah diurutkan kepada pengguna.
Mari kita ambil contoh untuk memahami teknik ini:
- Kita diberikan sebuah larik yang memiliki elemen "10, 40, 7, 3, 15." Sekarang, kita perlu mengatur larik ini dalam urutan menaik menggunakan teknik pengurutan gelembung di Python.
- Langkah pertama adalah menyusun larik dalam urutan yang diberikan.
- Pada "Iterasi 1", kita membandingkan elemen pertama dari sebuah larik dengan elemen lainnya satu per satu.
- Panah merah menggambarkan perbandingan elemen pertama dengan elemen lain dari suatu larik.
- Jika Anda perhatikan " 10 " lebih kecil dari " 40 ", jadi, ia tetap berada di tempat yang sama, tetapi elemen berikutnya " 7 " lebih kecil dari " 10 ". Oleh karena itu, elemen tersebut akan digantikan dan menjadi yang pertama.
- Proses di atas akan dilakukan berulang-ulang untuk menyortir elemen.
- Pada "Iterasi 2", elemen kedua akan dibandingkan dengan elemen-elemen lain dalam larik.
- Jika elemen yang dibandingkan kecil, maka elemen tersebut akan diganti, jika tidak, elemen tersebut akan tetap berada di tempat yang sama.
- Pada "Iterasi 3", elemen ketiga dibandingkan dengan elemen-elemen lain dalam larik.
- Pada "Iterasi 4" terakhir, elemen terakhir kedua akan dibandingkan dengan elemen-elemen larik lainnya.
- Pada langkah ini, larik diurutkan dalam urutan menaik.
Program untuk pengurutan gelembung
``` 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("Daftar yang diurutkan menggunakan Bubble SortTeknik: ", Bubble_Sort(unsorted_list)) ```
Keluaran
Kompleksitas Waktu dari jenis gelembung
- Kasus terburuk: Kompleksitas waktu terburuk untuk pengurutan gelembung adalah O( n 2).
- Kasus rata-rata: Kompleksitas waktu rata-rata untuk pengurutan gelembung adalah O( n 2).
- Kasus terbaik: Kompleksitas waktu terbaik untuk pengurutan gelembung adalah O(n).
Keuntungan
- Ini banyak digunakan dan mudah diterapkan.
- Kita dapat menukar elemen data tanpa menggunakan penyimpanan jangka pendek.
- Ini membutuhkan lebih sedikit ruang.
Kekurangan
- Ini tidak berkinerja baik saat berurusan dengan sejumlah besar elemen data yang besar.
- Ini membutuhkan n 2 langkah untuk setiap "n" jumlah elemen data yang akan diurutkan.
- Ini tidak terlalu bagus untuk aplikasi dunia nyata.
Urutan Penyisipan
Insertion sort adalah teknik pengurutan yang mudah dan sederhana yang bekerja mirip dengan mengurutkan kartu remi. Insertion sort mengurutkan elemen dengan membandingkan setiap elemen satu per satu dengan yang lain. Elemen-elemen tersebut diambil dan ditukar dengan elemen lainnya jika elemen tersebut lebih besar atau lebih kecil dari yang lain.
Mari kita ambil sebuah contoh
- Kita diberikan sebuah larik yang memiliki elemen "100, 50, 30, 40, 10".
- Pertama, kita susun larik dan mulai membandingkannya.
- Pada langkah pertama "100" dibandingkan dengan elemen kedua "50". "50" ditukar dengan "100" karena lebih besar.
- Pada langkah kedua, sekali lagi elemen kedua "100" dibandingkan dengan elemen ketiga "30" dan ditukar.
- Sekarang, jika Anda perhatikan, " 30 " berada di urutan pertama karena sekali lagi lebih kecil dari " 50 ".
- Perbandingan akan dilakukan hingga elemen terakhir dari sebuah larik dan pada akhirnya, kita akan mendapatkan data yang telah diurutkan.
Program untuk penyisipan penyisipan
``` def InsertionSort(array): for i in range(1, len(array)): nilai_kunci = array[i] j = i-1 while j>= 0 and nilai_kunci <array[j]: array[j + 1] = array[j] j -= 1 array[j + 1] = nilai_kunci array = [11, 10, 12, 4, 5] print ("Larik yang belum diurutkan: ", array) InsertionSort(array) print ("Larik yang sudah diurutkan dengan menggunakan Pengurutan Sisipan: ") for i in range(len(array)): print (array[i]) ```
Keluaran
Kompleksitas Waktu Penyisipan sortir
- Kasus terburuk: Kompleksitas waktu terburuk untuk pengurutan Penyisipan adalah O( n 2).
- Kasus rata-rata: Kompleksitas waktu rata-rata untuk pengurutan Penyisipan adalah O( n 2).
- Kasus terbaik: Kompleksitas waktu terbaik untuk pengurutan penyisipan adalah O(n).
Keuntungan
- Sederhana dan mudah diterapkan.
- Ini bekerja dengan baik saat menangani sejumlah kecil elemen data.
- Tidak membutuhkan lebih banyak ruang untuk implementasinya.
Kekurangan
- Mengurutkan elemen data dalam jumlah yang sangat banyak tidak akan membantu.
- Apabila dibandingkan dengan teknik penyortiran lainnya, teknik ini tidak memiliki kinerja yang baik.
Gabungkan sortir
Metode pengurutan ini menggunakan metode bagi dan taklukkan untuk mengurutkan elemen dalam urutan tertentu. Saat mengurutkan dengan bantuan pengurutan gabungan, elemen dibagi menjadi dua bagian dan kemudian diurutkan. Setelah mengurutkan semua bagian, sekali lagi elemen digabungkan untuk membentuk urutan yang sempurna.
Mari kita ambil contoh untuk memahami teknik ini
- Kita diberikan sebuah larik " 7, 3, 40, 10, 20, 15, 6, 5 ". Larik tersebut berisi 7 elemen. Jika kita membaginya menjadi setengah ( 0 + 7 / 2 = 3 ).
- Pada langkah kedua, Anda akan melihat bahwa elemen-elemennya dibagi menjadi dua bagian, masing-masing memiliki 4 elemen di dalamnya.
- Selanjutnya, elemen-elemen tersebut dibagi lagi dan masing-masing memiliki 2 elemen.
- Proses ini akan terus berlanjut hingga hanya ada satu elemen dalam larik. Lihat langkah no. 4 pada gambar.
- Sekarang, kita akan menyortir elemen-elemen tersebut dan mulai menggabungkannya seperti yang telah kita bagi.
- Pada langkah no. 5 jika Anda melihat 7 lebih besar dari 3, maka kita akan menukarnya dan menggabungkannya di langkah berikutnya dan sebaliknya.
- Pada akhirnya, Anda akan melihat bahwa larik kita diurutkan dalam urutan menaik.
Program untuk Sortir 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 inrange(len(arr)): print(arr[i],) print() arr = [12, 11, 13, 5, 6, 7] print("Larik yang diberikan adalah", end="\n") PrintSortedList(arr) MergeSort(arr) print("Larik yang diurutkan adalah: ", end="\n") PrintSortedList(arr) ```
Keluaran
Kompleksitas Waktu dari Urutan Penggabungan
- Kasus terburuk: Kompleksitas waktu terburuk untuk penggabungan sortir adalah O( n log( n )).
- Kasus rata-rata: Kompleksitas waktu rata-rata untuk pengurutan gabungan adalah O( n log( n )).
- Kasus terbaik: Kompleksitas waktu terbaik untuk pengurutan gabungan adalah O( n log( n )).
Keuntungan
- Ukuran file tidak menjadi masalah untuk teknik penyortiran ini.
- Teknik ini bagus untuk data yang umumnya diakses dalam urutan yang berurutan. Sebagai contoh, daftar tertaut, tape drive, dll.
Kekurangan
- Ini membutuhkan lebih banyak ruang bila dibandingkan dengan teknik penyortiran lainnya.
- Ini relatif kurang efisien daripada yang lain.
Urutkan cepat
Pengurutan cepat sekali lagi menggunakan metode bagi dan taklukkan untuk mengurutkan elemen Daftar atau larik. Metode ini menargetkan elemen pivot dan mengurutkan elemen menurut elemen pivot yang dipilih.
Sebagai contoh
- Kita diberikan sebuah larik yang memiliki elemen "1,8,3,9,4,5,7".
- Mari kita asumsikan "7" sebagai elemen percontohan.
- Sekarang kita akan membagi larik sedemikian rupa sehingga sisi kiri berisi elemen-elemen yang lebih kecil dari elemen pivot "7" dan sisi kanan berisi elemen-elemen yang lebih besar dari elemen pivot "7".
- Kita sekarang memiliki dua array " 1,3,4,5 " dan " 8, 9 ".
- Sekali lagi, kita harus membagi kedua array sama seperti yang kita lakukan di atas. Satu-satunya perbedaan adalah bahwa elemen pivot diubah.
- Kita perlu membagi larik hingga mendapatkan satu elemen dalam larik tersebut.
- Pada akhirnya, kumpulkan semua elemen pivot dalam urutan dari kiri ke kanan dan Anda akan mendapatkan larik yang diurutkan.
Program untuk penyortiran cepat
``` def Array_Partition( arr, terendah, tertinggi ): i = ( terendah-1 ) pivot_element = arr[ tertinggi ] for j in range( terendah, tertinggi ): if arr[ j ] <= pivot_element: i = i+1 arr [ i ], arr[ j ] = arr [ j ], arr[ i ] arr[ i+1 ], arr[ tertinggi ] = arr[ tertinggi ], arr[ i+1 ] return ( i+1 ) def QuickSort( arr, terendah, tertinggi ): if len( arr ) == 1: return arr if terendah <tertinggi: pi = Array_Partition(arr, terendah, tertinggi ) QuickSort( arr, terendah, pi-1 ) QuickSort( arr, pi+1, tertinggi ) arr = [ 9, 6, 7, 8, 0, 4 ] n = len( arr ) print( " Larik yang belum diurutkan: ", arr ) QuickSort( arr, 0, n-1 ) print( " Larik yang sudah diurutkan dengan menggunakan Quick Sort : " ) for i in range( n ): print( " %d "% arr[ i ] ) ```
Keluaran
Kompleksitas Waktu dari Pengurutan cepat
- Kasus terburuk: Kompleksitas waktu terburuk untuk pengurutan cepat adalah O( n 2).
- Kasus rata-rata: Kompleksitas waktu rata-rata untuk pengurutan cepat adalah O( n log( n )).
- Kasus terbaik: Kompleksitas waktu terbaik untuk pengurutan cepat adalah O( n log( n )).
Keuntungan
- Algoritma ini dikenal sebagai algoritma penyortiran terbaik dalam Python.
- Hal ini berguna saat menangani data dalam jumlah besar.
- Tidak memerlukan ruang tambahan.
Kekurangan
- Kompleksitas kasus terburuknya mirip dengan kompleksitas pengurutan gelembung dan pengurutan penyisipan.
- Metode pengurutan ini tidak berguna ketika kita sudah memiliki daftar yang telah diurutkan.
Tumpukan sortir
Dalam pengurutan larik, elemen terbesar dari sebuah larik selalu ditempatkan pada akar pohon dan kemudian dibandingkan dengan akar dengan simpul-simpul daun.
Sebagai contoh:
- Kita diberikan sebuah larik yang memiliki elemen "40, 100, 30, 50, 10".
- Dalam "Langkah 1" kami membuat pohon menurut keberadaan elemen dalam larik.
- Dalam " langkah 2 " kita membuat sebuah tumpukan maksimum, yaitu menyusun elemen-elemen dalam urutan menurun. Elemen terbesar akan berada di bagian atas (root) dan elemen terkecil berada di bagian bawah (simpul daun). Larik yang diberikan menjadi "100, 50, 30, 40, 10".
- Dalam "Langkah 3" kita membuat larik minimum sehingga kita dapat menemukan elemen-elemen minimum dari larik. Dengan melakukan ini, kita mendapatkan elemen-elemen maksimum dan minimum.
- Dalam "Langkah 4" dengan melakukan langkah yang sama, kita mendapatkan larik terurut.
Program untuk mengurutkan tumpukan
``` 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( " Larik yang belum diurutkan: ", arr ) HeapSort( arr ) n = len( arr ) print( " Larik yang sudah diurutkan oleh Heap Sort: " ) for i in range( n ): print( arr[ i ] ) ```
Keluaran
Kompleksitas Waktu dari jenis Timbunan
- Kasus terburuk: Kompleksitas waktu terburuk untuk pengurutan Tumpukan adalah O( n log( n )).
- Kasus rata-rata: Kompleksitas waktu rata-rata untuk pengurutan Tumpukan adalah O( n log( n )).
- Kasus terbaik: Kompleksitas waktu terbaik untuk pengurutan Tumpukan adalahO( n log( n )).
Keuntungan
- Sebagian besar digunakan karena produktivitasnya.
- Ini dapat diimplementasikan sebagai algoritme di tempat.
- Tidak memerlukan penyimpanan yang besar.
Kekurangan
- Membutuhkan ruang untuk menyortir elemen.
- Ini membuat pohon untuk menyortir elemen.
Perbandingan Antara Teknik Penyortiran
Metode Penyortiran | Kompleksitas waktu kasus terbaik | Rata-rata kompleksitas waktu kasus | Kompleksitas waktu kasus terburuk | Kompleksitas ruang | Stabilitas | Di tempat |
---|---|---|---|---|---|---|
Sortir gelembung | O (n) | O (n2) | O (n2) | O(1) | Ya. | Ya. |
Urutan penyisipan | O (n) | O (n2) | O (n2) | O(1) | Ya. | Ya. |
Urutkan cepat | O(n log(n)) | O(n log(n)) | O (n2) | O (N) | Tidak. | Ya. |
Gabungkan sortir | O(n log(n)) | O(n log(n)) | O(n log(n)) | O (N) | Ya. | Tidak. |
Tumpukan sortir | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(1) | Tidak. | Ya. |
Pada tabel perbandingan di atas, "O" adalah notasi Big Oh yang telah dijelaskan di atas, sedangkan "n" dan "N" berarti ukuran input.
Pertanyaan yang Sering Diajukan
T #1) Apa yang dimaksud dengan sort () dalam Python?
Jawaban: Dalam Python, sort() adalah sebuah fungsi yang digunakan untuk mengurutkan list atau array dalam urutan tertentu. Fungsi ini memudahkan proses pengurutan ketika mengerjakan proyek-proyek yang besar, dan sangat membantu para developer.
T # 2) Bagaimana cara mengurutkan di Python?
Jawaban: Python menyediakan berbagai teknik pengurutan yang digunakan untuk mengurutkan elemen. Sebagai contoh, Penyortiran cepat, Penyortiran gabungan, Penyortiran gelembung, Penyortiran penyisipan, dll. Semua teknik penyortiran ini efisien dan mudah dipahami.
T # 3) Bagaimana cara kerja pengurutan Python ()?
Jawaban: Fungsi sort() mengambil larik yang diberikan sebagai masukan dari pengguna dan mengurutkannya dalam urutan tertentu menggunakan algoritma pengurutan. Pemilihan algoritma tergantung pada pilihan pengguna. Pengguna dapat menggunakan pengurutan Cepat, pengurutan Gabung, pengurutan Gelembung, pengurutan Penyisipan, dll. Tergantung pada kebutuhan pengguna.
Kesimpulan
Pada tutorial di atas, kita telah membahas teknik pengurutan di Python bersama dengan teknik pengurutan secara umum.
- Sortir Gelembung
- Urutan Penyisipan
- Penyortiran Cepat
Kami belajar tentang kompleksitas waktu dan kelebihan serta kekurangannya. Kami juga membandingkan semua teknik di atas.