Lewati ke konten utama
Numekara
Konsultasi GratisKontak

K1 · Modul 08

Pengurutan efisien

46 langkah singkat, dari mudah sampai tantangan.

  1. Level 1

    Kenal

  2. Level 2

    Paham

  3. Level 3

    Terapkan

  4. Level 4

    Tantangan

  5. Level 5

    Pendalaman

Intinya

  • Bagi-dan-taklukkan: belah, selesaikan tiap bagian secara rekursif, satukan.
  • Merge sort Θ(n log n) di semua kasus dan stabil bila penggabungan memakai <=; quicksort cepat dalam praktik, tetapi pivot yang buruk memberi Θ(n²).
  • Setiap pengurutan berbasis perbandingan butuh Ω(n log n) perbandingan (pohon keputusan).
  • Counting sort dan radix sort lolos dari batas itu karena tidak membandingkan, asalkan kuncinya terbatas.
  • sorted (Timsort) memanfaatkan run yang sudah urut: hampir n perbandingan untuk data yang hampir terurut.

Sebelum mulai

±4–5 jam.

Modul ini memakai materi di bawah. Belum yakin? Ulas dulu bagian yang disebut.

Hasil belajar: menulis merge sort stabil, membuktikannya dengan induksi, dan menurunkan Θ(n log n) dari rekurensi; menulis quicksort dan menghindari kasus terburuk Θ(n²); membuktikan bahwa pengurutan berbasis perbandingan butuh Ω(n log n) perbandingan; menulis counting sort dan radix sort; serta menjelaskan kenapa sorted sangat cepat untuk data yang hampir terurut.

Proyek: Kurir Makmur langkah 8: urutkan_gabung (kontrak Proyek Kurir §3), merge sort stabil dengan O(n log n) perbandingan.

Istilah di modul ini (36)

Ketuk istilah untuk melihat penjelasannya. Di materi, istilah bergaris titik membuka kartu yang sama. Semua istilah course

Bahan modul

Semua kode, latihan, dan data modul ini dalam satu zip, untuk dijalankan di laptop atau Google Colab.

  • 30 contoh kode
  • 9 berkas latihan + tes
  • 1 berkas data
Semua data course (data-k1.zip) Cara menjalankan di laptop
Lihat isi zip
  • BACA-DULU.txt
  • contoh_k1_08_26.py
  • contoh_k1_08_49.py
  • contoh_k1_08_140.py
  • contoh_k1_08_176.py
  • contoh_k1_08_211.py
  • contoh_k1_08_248.py
  • contoh_k1_08_293.py
  • contoh_k1_08_363.py
  • contoh_k1_08_842.py
  • contoh_k1_08_930.py
  • contoh_k1_08_962.py
  • contoh_k1_08_1024.py
  • contoh_k1_08_1059.py
  • contoh_k1_08_1406.py
  • contoh_k1_08_1606.py
  • contoh_k1_08_1649.py
  • contoh_k1_08_1684.py
  • contoh_k1_08_1728.py
  • contoh_k1_08_1784.py
  • contoh_k1_08_1802.py
  • contoh_k1_08_1845.py
  • contoh_k1_08_1873.py
  • contoh_k1_08_1903.py
  • contoh_k1_08_2186.py
  • contoh_k1_08_2266.py
  • contoh_k1_08_2297.py
  • contoh_k1_08_2459.py
  • contoh_k1_08_2504.py
  • contoh_k1_08_2554.py
  • contoh_k1_08_2586.py
  • test_k1_08_1.py
  • test_k1_08_5.py
  • test_k1_08_6.py
  • test_k1_08_2.py
  • test_k1_08_4.py
  • test_k1_08_7.py
  • test_k1_08_3.py
  • test_k1_08_8.py
  • test_k1_08_9.py
  • peta.json