Pengurutan
Mengurutkan item
- Pengurutan mengatur daftar menjadi urutan, biasanya dari yang terkecil terlebih dahulu.
- Gerakan utamanya adalah tukar: tukar dua item.
- Dalam Python:
a[i], a[j] = a[j], a[i]menukar dua item daftar dalam satu baris.
Bubble sort
- Bandingkan setiap pasangan tetangga; tukar mereka jika urutannya salah.
- Setelah satu kali lintasan penuh, item terbesar telah "menggelembung" ke ujung.
- Ulangi beberapa kali. Setelah
n − 1kali perulangan, daftar pasti sudah terurut; Anda dapat berhenti lebih awal jika suatu perulangan tidak melakukan pertukaran.
data = [3, 1, 2]
n = len(data)
for i in range(n - 1):
for j in range(n - 1 - i):
if data[j] > data[j + 1]:
data[j], data[j + 1] = data[j + 1], data[j]
print(data)
Insertion sort
- Anggap bagian kiri daftar sebagai daftar yang sudah terurut.
- Ambil item berikutnya dan geser ke kiri hingga berada di tempat yang tepat.
- Seperti mengurutkan kartu remi di tangan, satu per satu.
data = [3, 1, 2]
for i in range(1, len(data)):
key = data[i]
j = i - 1
while j >= 0 and data[j] > key:
data[j + 1] = data[j]
j = j - 1
data[j + 1] = key
print(data)
Bandingkan keduanya
- Keduanya memeriksa sekitar
n × npasangan, sehingga keduanya lambat pada daftar besar. - Insertion sort cepat ketika daftar sudah hampir terurut.
- Metode yang lebih cepat ada, namun bubble sort dan insertion sort mudah dipahami.
Dalam pseudocode Cambridge
- Urutan gelembung dengan variabel
tempuntuk pertukaran, pada arraylist[1:n].
FOR i ← 1 TO n - 1
FOR j ← 1 TO n - i
IF list[j] > list[j + 1] THEN
temp ← list[j]
list[j] ← list[j + 1]
list[j + 1] ← temp
ENDIF
NEXT j
NEXT i
Kesalahan umum
- Bubble sort dan insertion sort keduanya O(n²).
- Jejaklah daftar kecil secara manual untuk memeriksa apakah pengurutan Anda berfungsi.
Sekarang Anda coba
- Setiap tugas mengubah daftar in place — tidak perlu mengembalikannya.
- Tekan Periksa jawaban untuk menguji kode Anda.
Lihat proses pengurutan berjalan
Pengurutan berulang kali membandingkan dan menukar hingga semuanya tersusun.
Kesulitan 4/5 · 280 koin + bonus kecil pada penyelesaian pertama hari ini
Tulis swap(items, i, j) yang menukar item pada indeks i dan indeks j dalam daftar. Ubah daftar di tempat (tanpa mengembalikan nilai).
Klik Jalankan untuk melihat output di sini.
Kesulitan 4/5 · 280 koin + bonus kecil pada penyelesaian pertama hari ini
Tulis bubble_sort(items) yang mengurutkan daftar ke dalam urutan menaik menggunakan algoritma bubble sort. Ubah daftar di tempat.
Klik Jalankan untuk melihat output di sini.
Kesulitan 4/5 · 280 koin + bonus kecil pada penyelesaian pertama hari ini
Tulis insertion_sort(items) yang mengurutkan daftar ke dalam urutan menaik menggunakan algoritma insertion sort. Ubah daftar di tempat.
Klik Jalankan untuk melihat output di sini.