7    VisuAlgo.net / /sorting Login Bubble Select Insert Merge Quick R-Quick Count Radix
Mode Eksplorasi ▿

>

>
pelan
cepat
go to beginning previous frame pause play next frame go to end

Pengurutan adalah masalah klasik tentang mengubah urutan elemen-elemen (yang bisa dibandingkan, seperti bilangan bulat, bilangan pecahan, strings, dsb) dari sebuah larik (senarai) ke urutan tertentu (terurut menaik, terurut menurun, terurut secara abjad, dsb).


Ada banyak algoritma-algoritma pengurutan, dan masing-masing memiliki kekuatan-kekuatan maupun kekurangan-kekurangan.


Pengurutan biasanya digunakan sebagai masalah pembuka dalam berbagai kelas-kelas Ilmu Komputer untuk menjelaskan berbagai ide-ide algoritma.


Tanpa kehilangan makna umum, kami menggunakan asumsi bahwa kita akan mengurutkan hanya bilangan-bilangan bulat, tidak harus unik, ke dalam urutan menaik di visualisasi ini. Cobalah klik Bubble Sort untuk animasi contoh pengurutan daftar 5 bilangan-bilangan bulat yang tidak beratur (dengan duplikat) diatas.


Klik 'Berikut' (di sisi kanan atas)/tekan 'Page Down' untuk berpindah ke e-Lecture slide berikutnya, gunakan daftar drop down/tekan tombol 'Space' untuk meloncat ke slide tertentu, atau Klik 'X' (di sisi bawah kanan)/tekan 'Esc' untuk pergi ke mode Penjelajahan.


Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
Please login if you are a repeated visitor or register for an (optional) free account first.

X Esc
Berikut PgDn

Masalah pengurutan mempunyai berbagai solusi-solusi algoritmik yang menarik dan mencakup banyak ide-ide Ilmu Komputer:

  1. Strategi pembandingan dibandingkan tidak-membandingkan,
  2. Implementasi iteratif dibandingkan rekursif,
  3. Paradigma Divide-and-Conquer (ini atau itu),
  4. Analisa kompleksitas waktu Terbaik/Terjelek/Kasus-rata-rata,
  5. Algoritma-algoritma dengan pengacakan, dsb.

Pro-tip: Since you are not logged-in, you may be a first time visitor who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown] to advance to the next slide, [PageUp] to go back to the previous slide, [Esc] to toggle between this e-Lecture mode and exploration mode.

X Esc
Sebelum PgUp
Berikut PgDn

Ketika sebuah larik (bilangan bulat) A terurut, banyak masalah-masalah yang berhubungan dengan A menjadi mudah (atau lebih mudah):

  1. Mencari nilai spesifik v di dalam larik A,
  2. Mencari nilai terkecil/terbesar atau nilai terkecil/terbesar ke-k dalam larik (statis) A,
  3. Mengetes keunikan dan menghapus duplikat dari larik A,
  4. Menghitung seberapa banyak nilai spesifik v muncul dalam larik A,
  5. Himpunan Irisan/Gabungan dari larik A dan larik terurut lainnya yaitu B,
  6. Mencari pasangan target xA dan yA sehingga x+y sama dengan nilai target z, dsb.

Diskusi: Dalam kelas-kelas nyata, instruktor bisa membahas aplikasi-aplikasi ini dengan lebih detail.


Another pro-tip: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2017). We recommend using Google Chrome to access VisuAlgo. Go to full screen mode (F11) to enjoy this setup. However, you can use zoom-in (Ctrl +) or zoom-out (Ctrl -) to calibrate this.

X Esc
Sebelum PgUp
Berikut PgDn

Ada dua aksi yang anda dapat lakukan di visualisasi ini.

X Esc
Sebelum PgUp
Berikut PgDn

Aksi pertama adalah tentang mendefinisikan masukan anda sendiri, sebuah larik/daftar yang:

  1. Betul-betul acak,
  2. Acak tapi terurut (dalam urutan menaik/menurun),
  3. Acak tetapi hampir terurut (dalam urutan menaik/menurun), atau
  4. Didefinisikan oleh anda sendiri.

Dalam mode Eksplorasi, anda dapat bereksperimen dengan berbagai algoritma-algoritma pengurutan yang tersedia di visualisasi ini untuk mengetahui masukan-masukan terbaik dan terjelek untuk algoritma-algoritma tersebut.

X Esc
Sebelum PgUp
Berikut PgDn

Aksi kedua adalah yang terpenting: Jalankan algoritma pengurutan yang sedang aktif dengan meng-klik menu "Urutkan" dan meng-klik "Lakukan".


Ingat bahwa anda dapat mengubah algoritma yang aktif dengan meng-klik singkatan di sisi atas dari halaman visualisasi ini.


Beberapa algoritma pengurutan mempunyai opsi-opsi tambahan. Anda dapat mengatur opsi-opsi ini sesuai keinginan anda sebelum meng-klik "Lakukan". Contohnya, dalam Bubble Sort (dan Merge Sort), ada opsi untuk juga menghitung indeks inversi dari larik masukan (ini adalah sebuah topik tingkat mahir).

X Esc
Sebelum PgUp
Berikut PgDn

Lihat visualisasi/animasi dari algoritma pengurutan terpilih disini.


Tanpa kehilangan makna umum, kami hanya menunjukkan bilangan-bilangan bulat didalam visualisasi ini dan tujuan kami adalah untuk mengurutkan mereka dari status awal ke status terurut menaik.

X Esc
Sebelum PgUp
Berikut PgDn

Di bagian atas halaman ini, anda akan melihat daftar berbagai algoritma-algoritma pengurutan dalam kelas-kelas Ilmu Komputer. Untuk mengaktifkan algoritma tertentu, pilihlah singkatan dari nama algoritma yang bersangkutan sebelum meng-klik "Urutkan → Lakukan".


Untuk memfasilitasi keberagaman, kami akan mengacak algoritma yang aktif setiap kali halaman ini ditampilkan.


Enam algoritma pertama berbasis-pembandingan sedangkan dua terakhir tidak. Kita akan membahas ide ini di pertengahan Kuliah Maya ini.


Tiga algoritma ditengah adalah algoritma pengurutan yang bersifat rekursif ssedangkan sisanya biasa diimplementasikan secara iteratif.

X Esc
Sebelum PgUp
Berikut PgDn

Supaya muat di layar, kami menyingkat nama-nama algoritma menjadi tiga karakter saja:

  1. Algoritma-Algorithma Pengurutan berbasis-pembandingan:
    1. BUB - Bubble Sort,
    2. SEL - Selection Sort,
    3. INS - Insertion Sort,
    4. MER - Merge Sort (implementasi rekursif),
    5. QUI - Quick Sort (implementasi rekursif),
    6. R-Q - Quick Sort Acak (implementasi rekursif).
  2. Algoritma-Algoritma Pengurutan tidak berbasis-pembandingan:
    1. COU - Counting Sort,
    2. RAD - Radix Sort.
X Esc
Sebelum PgUp
Berikut PgDn

Kita akan membahas tiga algoritma-algoritma pengurutan berbasis-pembandingan di beberapa slides berikutnya:

  1. Bubble Sort,
  2. Selection Sort,
  3. Insertion Sort.

Mereka disebut berbasis-pembandingan karena mereka membandingkan pasangan elemen-elemen dari sebuah larik dan menentukan apakah akan menukar posisi mereka atau tidak.


Ketiga algoritma-algoritma pengurutan ini adalah yang termudah untuk diimplementasikan tetapi juga bukan yang paling efisien, karena mereka berjalan dalam kompleksitas waktu O(N2).

X Esc
Sebelum PgUp
Berikut PgDn
Diberikan sebuah larik berisi N elemen, Bubble Sort akan:
  1. Membandingkan pasangan yang bersebelahan (a, b),
  2. Menukar pasangan tersebut bila tidak pada urutan yang seharusnya (dalam kasus ini, a > b),
  3. Ulangi Langkah 1 dan 2 hingga kita sampai di akhir larik (pasangan terakhir adalah elemen ke (N-2) dan (N-1) karena kita menggunakan indeks basis-0),
  4. Pada saat ini, elemen terbesar akan terletak pada posisi terakhir. Kita lalu mengurangi N dengan 1 dan kembali ke Langkah 1 sampai kita mendapat N = 1.

Tanpa basa-basi lagi, mari coba Bubble Sort pada larik contoh kecil [29, 10, 14, 37, 14].


Anda akan melihat animasi 'seperti-gelembung' jika anda membayangkan elemen-elemen yang besar 'menggelembung keatas' (atau sebenarnya 'bergerak ke sisi kanan dari larik').

X Esc
Sebelum PgUp
Berikut PgDn

Pembandingan dan penukaran membutuhkan waktu yang dibatasi oleh sebuah konstanta, mari sebut saja dengan c.


Ada dua perulangan (loop) yang bertingkat (nested) dalam Bubble Sort standar.


Perulangan (loop) luar berjalan tepat sebanyak N iterasi. Tetapi pengulangan (loop) dalam menjadi sedikit lebih pendek pada setiap iterasi:

  1. Saat i=0, (N−1) iterasi (dari pembandingan-pembandingan dan kemungkinan pertukaran-pertukaran),
  2. Saat i=1, (N−2) iterasi,
    ...,
  3. Saat i=(N−2), 1 iterasi,
  4. Saat i=(N−1), 0 iterasi.

Sehingga, jumlah total dari iterasi = (N−1)+(N−2)+...+1+0 = N*(N−1)/2 (penurunan)
Waktu total adalah = c*N*(N−1)/2 = O(N^2)

X Esc
Sebelum PgUp
Berikut PgDn

Bubble Sort sebenarnya tidak efisien dengan kompleksitas waktu O(N^2). Bayangkan jika kita memiliki N = 105 angka-angka. Meskipun komputer kita sangat cepat dan dapat menghitung 108 operasi-operasi dalam 1 detik, Bubble Sort akan membutuhkan sekitar 100 detik untuk bisa selesai.


Tetapi, Bubble Sort dapat dihentikan lebih awal, misalkan coba Bubble Sort pada contoh kecil yang telah terurut menaik diatas [3, 6, 11, 25, 39] dimana Bubble Sort dapat dihentikan dalam waktu O(N).


Idenya mudah: Jika kita melalui perulangan dalam (inner loop) tanpa melakukan pertukaran sama sekali, itu berarti bahwa larik tersebut sudah terurut dan kita dapat menghentikan Bubble Sort pada saat itu.


Diskusi: Meskipun ide tersebut membuat Bubble Sort berjalan lebih cepat dalam kasus-kasus umum, ide ini tidak mengubah kompleksitas waktu O(N^2) dari Bubble Sort... Kenapa?

X Esc
Sebelum PgUp
Berikut PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc
Sebelum PgUp
Berikut PgDn

Diberikan sebuah larik berisi N elemen dan L = 0, Selection Sort akan:

  1. Menemukan posisi X dari elemen terkecil dalam interval [L...N-1],
  2. Tukar item ke-X dengan item ke-L,
  3. Naikkan batas bawah L sebesar 1 dan kembail ke Langkah 1 sampai L = N-2.

Tanpa basa-basi lagi, mari coba Selection Sort pada larik contoh kecil yang sama [29, 10, 14, 37, 13].


Tanpa kehilangan makna umum, kita juga dapat mengimplementasikan Selection Sort secara terbalik: Temukan posisi dari elemen terbesar Y dan tukar dengan elemen terakhir.


X Esc
Sebelum PgUp
Berikut PgDn
void selectionSort(int a[], int N) {
for (int L = 0; L <= N-2; L++) { // O(N)
int X = min_element(a+L, a+N) - a; // O(N)
swap(a[X], a[L]); // O(1), X bisa sama dengan L (tidak ada pertukaran)
}
}

Total: O(N2) — Tepatnya, ini sama dengan analisa Bubble Sort.

X Esc
Sebelum PgUp
Berikut PgDn

Quiz: How many (real) swaps are required to sort [29, 10, 14, 37, 13] by Selection Sort?

3
2
4
1
X Esc
Sebelum PgUp
Berikut PgDn

Insertion Sort mirip dengan bagaimana kebanyakan orang menyusun kartu poker di tangan. Tangan poker

  1. Mulai dengan satu kartu di tangan,
  2. Pilih kartu berikutnya dan masukkan ke dalam posisi yang benar,
  3. Ulang langkah tersebut untuk seluruh kartu.

Tanpa basa-basi lagi, mari coba Insertion Sort pada larik contoh kecil [40, 13, 20, 8.

X Esc
Sebelum PgUp
Berikut PgDn
void insertionSort(int a[], int N) {
for (int i = 1; i < N; i++) { // O(N)
X = a[i]; // X is the item to be inserted
int j = i-1;
for (; j >= 0 && a[j] > X; j--) // can be fast or slow
a[j+1] = a[j]; // make a place for X
a[j+1] = X; // index j+1 is the insertion point
}
}
X Esc
Sebelum PgUp
Berikut PgDn

Perulangan luar (outer loop) dijalankan N−1 kali, sepertinya ini cukup jelas.

Tetapi berapa kali perulangan dalam (inner loop) dilakukan tergantung pada masukan:

  1. Dalam kasus terbaik, larik sudah terurut menaik dan (a[j] > X) selalu salah
    Sehingga tidak ada pergeseran data yang terjadi dan perulangan dalam (inner loop) berjalan dalam O(1),
  2. Dalam kasus terjelek, larik terurut terbalik (menurun) dan (a[j] > X) selalu benar
    Pemasukkan (insertion) selalu terjadi di depan larik dan perulangan dalam (inner loop) berjalan dalam O(N).

Sehingga, waktu terbaik adalah O(N × 1) = O(N) dan waktu terburuk adalah O(N × N) = O(N2).

X Esc
Sebelum PgUp
Berikut PgDn

Quiz: What is the complexity of Insertion Sort on any input array?

O(N^2)
O(N log N)
O(1)
O(N)


Tanya instruktor anda bila anda tidak mengerti tentang hal ini atau baca catatan yang sejenis di slide ini.

X Esc
Sebelum PgUp
Berikut PgDn

Kita akan membahas dua (+setengah) algoritma-algoritma berbasis-pembandingan di beberapa slide berikutnya:

  1. Merge Sort,
  2. Quick Sort dan versi acaknya (yang hanya memiliki satu perubahan).

Algoritma-algoritma pengurutan ini biasanya diimplementasikan secara rekursif, menggunakan paradigma pemecahan masalah Divide and Conquer, dan berjalan dalam waktu O(N log N) untuk Merge Sort dan O(N log N) secara ekspektasi untuk Quick Sort Acak.


PS: Versi tidak-acak dari Quick Sort berjalan dalam waktu O(N2).

X Esc
Sebelum PgUp
Berikut PgDn

Diberikan sebuah larik berisi N elemen, Merge Sort akan:

  1. Menggabungkan tiap pasang elemen (yang secara default terurut) menjadi larik-larik berukuran 2 elemen,
  2. Menggabungkan tiap pasang larik-larik tersebut menjadi larik-larik berukuran 4 elemen, Ulangi proses ini...,
  3. Langkah terakhir: Menggabungkan 2 larik-larik yang sudah terurut dengan jumlah N/2 elemen (untuk memudahkan diskusi, kita berasumsi bahwa N genap) untuk mendapatkan larik yang terurut penuh dengan jumlah N elemen.

Ini hanyalah ide general dan kita membutuhkan beberapa detail tambahan sebelum kita bisa membahas bentuk sebenarnya dari Merge Sort.

X Esc
Sebelum PgUp
Berikut PgDn

Kita akan membahas algoritma Merge Sort ini dengan pertama-tama membahas sub-rutin terpentingnya: Proses penggabungan (merge) dalam O(N).


Diberikan dua larik yang sudah terurut, A dan B, dengan jumlah N1 dan N2 elemen, kita dapat dengan efisien menggabungkan mereka mejadi satu larik terurut yang lebih besar dengan jumlah N = N1+N2 elemen, dalam waktu O(N).


Ini dapat diraih dengan cara membandingkan elemen terdepan dari kedua larik dan mengambil yang terkecil dari dua itu setiap waktu. Tetapi, sub-rutin merge yang sederhana tapi cepat O(N) ini akan membutuhkan larik tambahan untuk melakukan proses penggabungan ini dengan benar. Lihat slide berikutnya.

X Esc
Sebelum PgUp
Berikut PgDn
void merge(int a[], int low, int mid, int high) {
// subarray1 = a[low..mid], subarray2 = a[mid+1..high], terurut
int N = high-low+1;
int b[N]; // diskusi: kenapa kita butuh larik sementara b?
int left = low, right = mid+1, bIdx = 0;
while (left <= mid && right <= high) // proses penggabungan
b[bIdx++] = (a[left] <= a[right]) ? a[left++] : a[right++];
while (left <= mid) b[bIdx++] = a[left++]; // sisanya, jika ada
while (right <= high) b[bIdx++] = a[right++]; // sisanya, jika ada
for (int k = 0; k < N; k++) a[low+k] = b[k]; // kopi kembali
}

Cobalah Merge Sort pada larik contoh [1, 5, 19, 20, 2, 11, 15, 17] yang sebagian pertamanya telah terurut [1, 5, 19, 20] dan sebagian keduanya juga telah terurut [2, 11, 15, 17]. Fokus kepada penggabungan terakhir dari algoritma Merge Sort.

X Esc
Sebelum PgUp
Berikut PgDn

Sebelum kita lanjutkan, mari berbicara tentang Divide and Conquer (disingkat sebagai D&C), sebuah paradigma pemecahan masalah yang kuat.


Algoritma Divide and Conquer menyelesaikan (sejenis) masalah — seperti masalah pengurutan kita — dalam beberapa langkah-langkah berikut:

  1. Langkah Divide: Membagi masalah yang asli dan besar menjadi masalah-masalah yang lebih kecil dan secara rekursif menyelesaikan masalah-masalah yang lebih kecil tersebut,
  2. Langkah Conquer: Gabungkan hasil-hasil dari masalah-masalah yang lebih kecil tersebut untuk menghasilkan hasil dari masalah yang asli dan besar.
X Esc
Sebelum PgUp
Berikut PgDn

Merge Sort adalah algoritma pengurutan bersifat Divide and Conquer.


Langkah pembagian (divide) mudah saja: Bagi larik yang sekarang menjadi dua bagian (sama besar jika N genap atau satu sisi satu elemen sedikit lebih besar jika N ganjil) dan lalu secara rekursif mengurutkan kedua bagian tersebut.


Langkah penaklukkan (conquer) adalah langkah yang melakukan usaha terbesar: Gabungkan dua bagian (yang sudah terurut) untuk membentuk larik yang terurut, menggunakan sub-rutin penggabungan (merge) yang dibahas sebelumnya.

X Esc
Sebelum PgUp
Berikut PgDn
void mergeSort(int a[], int low, int high) {
// larik yang akan diurutkan adalah a[low..high]
if (low < high) { // kasus dasar: low >= high (0 or 1 item)
int mid = (low+high) / 2;
mergeSort(a, low , mid ); // bagi jadi dua bagian
mergeSort(a, mid+1, high); // lalu urutkan secara rekursif
merge(a, low, mid, high); // kuasai: sub-rutin merge
}
}
X Esc
Sebelum PgUp
Berikut PgDn

Silahkan coba Merge Sort pada larik contoh [7, 2, 6, 3, 8, 4, 5] untuk melihat detail-detail lebih lanjut.


Dibandingkan dengan apa yang biasanya ditampilkan di banyak buku-buku teks Ilmu Komputer yang dicetak (karena buku-buku sifatnya statis), eksekusi sebenarnya dari Merge Sort tidak membagi kedua sub-larik per level, tetapi Merge Sort akan secara rekursif mengurutkan sub-larik kiri terlebih dahulu sebelum mengurutkan sub-larik kanan.


Lebih detailnya, pada larik contoh [7, 2, 6, 3, 8, 4, 5], Merge Sort akan merekursi ke [7, 2, 6, 3], lalu [7, 2], lalu [7] (sebuah elemen tunggal, yang sudah terurut secara default), kembali, rekursi ke [2] (terurut), kembali, lalu menggabungkan [7, 2] menjadi [2, 7], sebelum Merge Sort memproses [6, 3] dan selanjutnya.

X Esc
Sebelum PgUp
Berikut PgDn

Dalam Merge Sort, usaha terbanyak dilakukan dalam langkah conquer/merge karena langkah divide sebenarnya tidak melakukan apa-apa (dianggap O(1)).


Ketika kita memanggil merge(a, low, mid, high), kita memproses k = (high-low+1) elemen.
Akan ada paling banyak k-1 pembandingan.
Ada k perpindahan dari larik asli a ke larik temporer b dan k perpindahan lainnya untuk menyalin balik.
Secara total, jumlah operasi dalam operasi sub-rutin merge adalah < 3k-1 = O(k).


Pertanyaan penting berikutnya adalah berapa kali sub-rutin merge ini dipanggil?

X Esc
Sebelum PgUp
Berikut PgDn
The Recursion Tree of Merge Sort
X Esc
Sebelum PgUp
Berikut PgDn

Level 1: 2^0=1 panggilan kepada merge() dengan N/2^1 elemen masing-masing, O(2^0 x 2 x N/2^1) = O(N)
Level 2: 2^1=2 panggilan kepada merge() dengan N/2^2 elemen masing-masing, O(2^1 x 2 x N/2^2) = O(N)
Level 3: 2^2=4 panggilan kepada merge() dengan N/2^3 elemen masing-masing, O(2^2 x 2 x N/2^3) = O(N)
...
Level (log N): 2^(log N-1) (atau N/2) panggilan kepada merge() dengan N/2^log N (or 1) elemen masing-masing, O(N)


Ada log N level dan di setiap level, kita melakukan usaha sebesar O(N), sehingga kompleksitas waktu seluruhnya adalah O(N log N). Nanti, kita akan melihat bahwa ini adalah algoritma pengurutan (berbasis-pembandingan) yang sudah optimal, atau dengan kata lain, kita tidak bisa membuat algoritma lebih baik dari Merge Sort ini.

X Esc
Sebelum PgUp
Berikut PgDn

Bagian bagus dari Merge Sort yang paling penting adalah garansi performa O(N log N), tidak tergantung pada urutan asli dari masukan. Dengan kata lain, tidak ada kasus tes yang bisa membuat Merge Sort berjalan lebih lambat dari O(N log N) untuk segala larik dengan N elemen.


Merge Sort sangat cocok untuk mengurutkan masukan yang sangat besar karena O(N log N) bertumbuh jauh lebih lambat dari algoritma-algoritma pengurutan yang membutuhkan waktu O(N2) seperti yang dibahas sebelumnya.


Merge Sort juga adalah algoritma pengurutan yang stabil. Diskusi: Kenapa?


Tetapi ada juga beberapa bagian yang tidak bagus dari Merge Sort. Pertama, sebenarnya tidak mudah untuk mengimplementasikan Merge Sort dari awal (tetapi sebenarnya kita tidak perlu melakukannya). Kedua, Merge Sort membutuhkan tempat tambahan sebesar O(N) dalam proses penggabungan, sehingga tidak efisien secara memori dan tidak di-tempat. Ngomong-ngomong, bila anda tertarik untuk melihat apa yang sudah dilakukan untuk mengatasi bagian yang tidak bagus dari Merge Sort (klasik) ini, anda bisa membaca ini.

X Esc
Sebelum PgUp
Berikut PgDn

Quick Sort adalah algoritma pengurutan berbasis Divide and Conquer (satu lagi yang telah dibahas di Kuliah Maya ini adalah Merge Sort).


Kita akan melihat bahwa versi deterministik, tidak acak dari Quick Sort bisa memiliki kompleksitas waktu yang jelek, yaitu O(N2) pada masukan jahat (adversary) sebelum kita melanjutkan pembahasan dengan versi acak yang lebih bisa dipakai nantinya.

X Esc
Sebelum PgUp
Berikut PgDn

Langkah Divide: Pilih elemen p (dinamai sebagai pivot)
Lalu partisi (partition) elemen-elemen a[i..j] menjadi tiga bagian: a[i..m-1], a[m], dan a[m+1..j].
a[i..m-1] (kemungkinan kosong) berisi elemen-elemen yang lebih kecil dari p.
a[m] adalah pivot p, indeks m adalah posisi p yang benar didalam larik terurut a nantinya.
a[m+1..j] (kemungkinan kosong) berisi elemen-elemen yang lebih besar atau sama dengan p.
Lalu, urutkan kedua bagian ini secara rekursif.


Langkah Conquer: Jangan kaget... Kita tidak melakukan apa-apa :O!


Jika anda membandingkan ini dengan Merge Sort, anda akan melihat bahwa langkah-langkah D&C dari Quick Sort terbalik total dengan Merge Sort.

X Esc
Sebelum PgUp
Berikut PgDn

We will dissect this Quick Sort algorithm by first discussing its most important sub-routine: The O(N) partition (classic version).


To partition a[i..j], we first choose a[i] as the pivot p.

The remaining items (i.e. a[i+1..j]) are divided into 3 regions:

  1. S1 = a[i+1..m] where items are < p,
  2. S2 = a[m+1..k-1] where items are ≥ p, and
  3. Unknown = a[k..j], where items are yet to be assigned to either S1 or S2.

Discussion: Why do we choose p = a[i]? Are there other choices?


Harder Discussion: Is it good to always put item(s) that is/are == p on S2 at all times?

X Esc
Sebelum PgUp
Berikut PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc
Sebelum PgUp
Berikut PgDn

Pada awalnya, region S1 dan S2 dua-duanya kosong, yaitu semua elemen kecuali pivot p yang terpilih berada dalam region yang tidak diketahui.


Lalu, untuk setiap elemen a[k] di region yang tidak diketahui, kita membandingkan a[k] dengan p dan memutuskan satu dari dua kasus berikut:

  1. Jika a[k]p, taruh a[k] di S2, atau
  2. Lainnya, taruh a[k] di S1.

Kedua kasus-kasus ini akan dijelaskan lebih detil di dua slide berikutnya.


Pada akhirnya, kita menukar a[i] dan a[m] untuk menaruh pivot p tepat diantara S1 dan S2.

X Esc
Sebelum PgUp
Berikut PgDn
Case when a[k] ≥ p, increment k, extend S2 by 1 item
X Esc
Sebelum PgUp
Berikut PgDn
Case when a[k] < p, increment m, swap a[k] with a[m], increment k, extend S1 by 1 item
X Esc
Sebelum PgUp
Berikut PgDn
int partition(int a[], int i, int j) {
int p = a[i]; // p sebagai pivot
int m = i; // S1 dan S2 pada mulanya kosong
for (int k = i+1; k <= j; k++) { // jelajah bagian baru
if (a[k] < p) { // case 2
m++;
swap(a[k], a[m]); // algoritma C++ STL std::swap
} // kita tidak melakukan apa-apa pada kasus 1: a[k] >= p
}
swap(a[i], a[m]); // langkah terakhir, tukar pivot dengan a[m]
return m; // kembalikan indeks pivot
}
X Esc
Sebelum PgUp
Berikut PgDn
void quickSort(int a[], int low, int high) {
if (low < high) {
int m = partition(a, low, high); // O(N)
// a[low..high] ~> a[low..m–1], pivot, a[m+1..high]
quickSort(a, low, m-1); // urutkan sub-larik kiri
// a[m] = pivot telah terurut setelah partition
quickSort(a, m+1, high); // lalu urutkan sub-larik kanan
}
}
X Esc
Sebelum PgUp
Berikut PgDn

Coba Quick Sort pada larik contoh [27, 38, 12, 39, 27, 16]. Kita akan bahas langkah pertama dari partition sebagai berikut:
Kita set p = a[0] = 27.
Kita set a[1] = 38 sebagai bagian S2 jadi S1 = {} dan S2 = {38}.
Kita tukar a[1] = 38 dengan a[2] = 12 jadi S1 = {12} dan S2 = {38}.
Kita set a[3] = 39 dan juga a[4] = 27 sebagai bagian S2 jadi S1 = {12} dan S2 = {38,39,27}.
Kita tukar a[2] = 38 dengan a[5] = 16 jadi S1 = {12,16} dan S2 = {39,27,38}.
Kita tukar p = a[0] = 27 dengan a[2] = 16 jadi S1 = {16,12}, p = {27}, dan S2 = {39,27,38}.


Setelah ini, a[2] = 27 dijamin terurut sekarang dan Quick Sort akan mengurutkan secara rekursif sisi kiri a[0..1] duluan dan nanti mengurutkan secara rekursif sisi kanan a[3..5].

X Esc
Sebelum PgUp
Berikut PgDn

Pertama-tama, kita analisa biaya satu pemanggilan partition.


Didalam partition(a, i, j), hanya ada satu for-loop yang diulang (j-i) kali. Karena j bisa sebesar N-1 dan i bisa sekecil 0, maka kompleksitas waktu dari partition adalah O(N).


Mirip dengan analisa Merge Sort, kompleksitas waktu dari Quick Sort tergantung seberapa banyak partition(a, i, j) dipanggil.

X Esc
Sebelum PgUp
Berikut PgDn

Ketika larik a sudah dalam urutan menaik, seperti contoh diatas, Quick Sort akan mengatur p = a[0] = 5, dan akan mengembalikan m = 0, oleh karena itu membuat region S1 kosong dan region S2: Semuanya kecuali pivot (N-1 elemen).


Cobalah Quick Sort pada larik masukan contoh [5, 18, 23, 39, 44, 50].

X Esc
Sebelum PgUp
Berikut PgDn

Pada skenario terjelek tersebut, inilah yang terjadi:


Worst Case analysis of Quick Sort

Partisi pertama membutuhkan waktu O(N), membagi a menjadi 0, 1, N-1 elemen-elemen, lalu rekursi ke-kanan.
Yang kedua membutuhkan waktu O(N-1), membagi a menjadi 0, 1, N-2 elemen-elemen, lalu rekursi ke-kanan lagi.
...
Sampai yang terakhir, Partisi ke N membagi a menjadi 0, 1, 1 elemen, dan rekursi Quick Sort berhenti.


Ini adalah pola klasik N+(N-1)+(N-2)+...+1, yang disederhanakan sebagai O(N2), analisa yang mirip dengan yang di slide ini...

X Esc
Sebelum PgUp
Berikut PgDn

Skenario terbaik dari Quick Sort terjadi ketika partition selalu membagi larik menjadi dua bagian yang sama besar, seperti Merge Sort.


Ketika itu terjadi, kedalaman rekursi hanyalah O(log N).


Karena setiap level membutuhkan O(N) pembandingan, kompleksitas waktu adalah O(N log N).


Coba Quick Sort di contoh larik masukan yang telah dipersiapkan secara khusus [4, 1, 3, 2, 6, 5, 7].

Pada prakteknya, hal ini jarang terjadi, sehingga kita harus memikirkan cara yang lebih baik: Quick Sort Acak.

X Esc
Sebelum PgUp
Berikut PgDn

Sama seperti Quick Sort tetapi sebelum menjalankan algoritma partition, algoritma ini secara acak memilih sebuah pivot diantara a[i..j] dibandingkan dengan selalu memilih a[i] (atau indeks tetap lainnya diantara [i..j]) secara deterministik.


Coba Random Quick Sort pada larik yang besar dan agak acak ini.


Latihan kecil: Implementasikan ide diatas pada implementasi yang ditunjukkan di slide ini!

X Esc
Sebelum PgUp
Berikut PgDn

Akan dibutuhkan kuliah sekitar 1 jam untuk menjelaskan dengan baik kenapa versi acak dari Quick Sort mempunyai kompleksitas waktu yang diharapkan O(N log N) pada larik masukan apapun dengan N elemen.


Dalam Kuliah Maya ini, kita akan berasumsi bahwa ini benar.


Jika anda membutuhkan penjelasan non formal: Bayangkan bahwa versi acak dari Quick Sort yang mengacak pemilihan pivot, kita tidak akan selalu mendapat pembagian yang sangat jelek yaitu 0 (kosong), 1 (pivot), dan N-1 elemen lainnya. Kombinasi dari beruntung (setengah-pivot-setengah), kira-kira beruntung, kira-kira tidak beruntung, dan sangat tidak beruntung (kosong, pivot, sisanya) menghasilkan kompleksitas waktu rata-rata O(N log N).


Diskusi: Sebenarnya frase "larik masukan apapun" diatas tidak sepenuhnya benar. Sebenarnya ada cara untuk membuat versi acak dari Quick Sort seperti yang sekarang dipresentasikan di halaman VisuAlgo ini agar tetap berjalan dalam O(N2). Bagaimana?

X Esc
Sebelum PgUp
Berikut PgDn

Kita akan membahas dua algoritma-algoritma pengurutan yang tidak berbasis-pembandingan di beberapa slide berikut ini:

  1. Counting Sort,
  2. Radix Sort.

Algoritma-algoritma pengurutan ini bisa lebih cepat dari batas bawah algoritma pengurutan berbasis-pembandingan yaitu Ω(N log N) karena mereka tidak membandingkan elemen-elemen dari larik.

X Esc
Sebelum PgUp
Berikut PgDn

Sudah diketahui (tapi tidak dibuktikan di Kuliah Maya ini karena akan membutuhkan 1 jam kuliah lagi) bahwa semua algortima pengurutan berbasis-pembandingan mempunyai kompleksitas waktu batas bawah sebesar Ω(N log N).


Jadi, algoritma pengurutan berbasis-pembandingan apapun dengan kompleksitas terjelek O(N log N), seperti Merge Sort sebenarnya algoritma yang sudah optimal, kita tidak bisa berbuat lebih baik dari itu.


Tetapi, kita dapat mendapatkan algoritma pengurutan yang lebih cepat — yaitu dalam O(N) — jika ada beberapa asumsi-asumsi dari larik masukan sehingga kita dapat menghindari pembandingan dari elemen-elemen untuk menentukan urutan.

X Esc
Sebelum PgUp
Berikut PgDn

Asumsi: Jika elemen-elemen yang akan diurutkan adalah bilangan-bilangan bulat dengan range kecil, kita dapat menghitung frekuensi dari setiap bialngan bulat (dalam range kecil tersebut) dan lalu mengecek range kecil tersebut untuk mengeluarkan elemen-elemen tersebut dalam urutan terurut.


Coba Counting Sort pada larik contoh diatas dimana semua bilangan-bilangan bulat berada dalam [1..9], sehingga kita hanya perlu menghitung berapa kali bilangan 1 muncul, bilangan 2 muncul, ..., bilangan 9 muncul, dan lalu mengecek 1 sampai 9 untuk mencetak x kopi dari bilangan y jika frekuensi[y] = x.


Kompleksitas waktunya adalah O(N) untuk menghitung frekuensi-frekuensi dan O(N+k) untuk mencetak keluaran dalam urutan terurut dimana k adalah range dari bilangan-bilangan bulat masukan, yang adalah 9-1+1 = 9 dalam contoh ini. Kompleksitas waktu dari Counting Sort menjadi O(N+k), yang adalah O(N) jika k kecil.


Kita tidak bisa melakukan bagian perhitungan dari Counting Sort ketika k cukup besar karena keterbatasan memori, karena kita harus menyimpan frekuensi-frekuensi dari k bilangan-bilangan bulat tersebut.

X Esc
Sebelum PgUp
Berikut PgDn

Asumsi: Jika elemen-elemen yang akan diurutkan adalah bilangan-bilangan bulat dengan range besar tetapi sedikit jumlah digit, kita dapat menggabungkan ide Counting Sort dengan Radix Sort untuk mencapai kompleksitas waktu linear.


Dalam Radix Sort, kita memperlakukan setiap elemen yang akan diurutkan sebagai string dengan w digit (kita tambahkan bilangan-bilangan bulat yang mempunyai kurang dari w digit dengan angka nol pembuka jika diperlukan).


Dari digit yang paling tidak signifikan (yang paling kanan) ke digit yang paling signifikan (yang paling kiri), kita melakukan satu pass ke semua N elemen-elemen dan menaruh mereka sesuai dengan digit aktif ke 10 Antrean (Queues) (satu untuk setiap digit [0..9]), yang seperti Counting Sort termodifikasi karena yang ini menjaga stabilitas. Lalu kita menggabungkan kembali group-group tersebut untuk iterasi selanjutnya.


Coba Radix Sort pada larik masukan contoh diatas untuk penjelasan yang lebih baik.


Catat bahwa kita hanya melakukan O(w × (N+k)) iterasi. Di contoh ini, w = 4 dan k = 10.

X Esc
Sebelum PgUp
Berikut PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc
Sebelum PgUp
Berikut PgDn

Ada beberapa properti-properti lain yang bisa digunakan untuk membedakan algoritma-algoritma pengurutan lebih dari sekedar apakah mereka berbasis-pembandingan atau tidak, rekursif atau iteratif.


Dalam bagian ini, kita akan membahas tentang di-tempat dibandingkan dengan tidak di-tempat, stabil dibandingkan dengan tidak stabil, dan performa caching dari berbagai algoritma-algoritma pengurutan.

X Esc
Sebelum PgUp
Berikut PgDn

Sebuah algoritma pengurutan dikatakan sebagai pengurutan di-tempat jika algoritma tersebut hanya membutuhkan sejumlah ruang konstan (yaitu O(1)) selama proses pengurutan. Dengan kata lain, beberapa (konstan) variable-variable ekstra diperbolehkan tetapi kita tidak diperbolehkan untuk menggunakan variable-variable yang mempunyai ukuran tergantung kepada ukuran masukan N.


Merge Sort (versi klasik), karena sub-rutin merge nya membutuhkan larik temporer tambahan dengan ukuran N, tidak di-tempat.


Diskusi: Bagaimana dengan Bubble Sort, Selection Sort, Insertion Sort, Quick Sort (acak maupun tidak), Counting Sort, dan Radix Sort. Yang mana saja yang di-tempat?

X Esc
Sebelum PgUp
Berikut PgDn

Sebuah algoritma pengurutan dikatakan stabil bila urutan relatif dari elemen-elemen dengan nilai yang sama tetap terpelihara oleh algoritma tersebut setelah pengurutan dilakukan.


Contoh aplikasi dari pengurutan stabil: Asumsikan bahwa kita memiliki nama-nama murid yang telah diurutkan secara abjad. Sekarang, jika daftar ini diurutkan lagi tetapi berdasarkan nomor grup tutorial (ingat bahwa satu grup tutorial biasanya mempunyai banyak murid-murid), sebuah algoritma pengurutan yang stabil akan menjamin bahwa semua murid-murid yang berada di dalam grup tutorial yang sama akan tetap tampil dalam urutan abjad.


Diskusi: Algoritma-algoritma pengurutan mana saja yang dibahas dalam Kuliah Maya ini yang stabil?
Cobalah mengurutkan larik A = {3, 4a, 2, 4b, 1}, lihat bahwa ada dua versi dari 4 (4a duluan, lalu 4b).

X Esc
Sebelum PgUp
Berikut PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc
Sebelum PgUp
Berikut PgDn

Kita mendekati akhir dari Kuliah Maya ini.


Waktunya untuk beberapa pertanyaan-pertanyaan sederhana.

X Esc
Sebelum PgUp
Berikut PgDn

Quiz: Which of these algorithms run in O(N log N) on any input array of size N?

Quick Sort (Deterministic)
Merge Sort
Insertion Sort
Bubble Sort
X Esc
Sebelum PgUp
Berikut PgDn

Quiz: Which of these algorithms has worst case time complexity of Θ(N^2) for sorting N integers?

Selection Sort
Bubble Sort
Merge Sort
Radix Sort
Insertion Sort


Θ adalah analisa kompleksitas waktu yang sudah ketat (tight) dimana analisa kasus terbaik Ω dan kasus terjelek big-O cocok.

X Esc
Sebelum PgUp
Berikut PgDn

Kita telah mencapai akhir dari Kuliah Maya pengurutan.


Tetapi, masih ada dua algoritma-algoritma pengurutan lainnya di VisuAlgo yang berada didalam struktur-struktur data yang lain: Heap Sort dan Balanced BST Sort. Kita akan membahas mereka saat anda menjalani Kuliah Maya dari dua struktur-struktur data tersebut.

X Esc
Sebelum PgUp
Berikut PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc
Sebelum PgUp
Berikut PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc
Sebelum PgUp
Berikut PgDn

Sebenarnya, kode sumber C++ untuk banyak dari algoritma-algoritma pengurutan ini sudah tersebar di berbagai slide-slide Kuliah Maya. Untuk bahasa pemrograman yang lain, silahkan terjemahkan kode sumber C++ yang diberikan ke bahasa pemrograman lain tersebut.


Biasanya, pengurutan hanyalah bagian kecil dari proses pemecahan masalah dan akhir-akhir ini, banyak bahasa-bahasa pemrograman mempunyai fungsi-fungsi pengurutan mereka sendiri-sendiri sehingga kita tidak perlu untuk mengimplementasikan ulang algoritma-algoritma tersebut kecuali sangat perlu.


Dalam C++, anda bisa menggunakan std::sort, std::stable_sort, atau std::partial_sort dalam STL algorithm.
Dalam Python, anda bisa menggunakan sort.
Dalam Java, anda bisa menggunakan Collections.sort.


Jika fungsi pembandingan adalah spesifik ke sebuah masalah, kita mungkin harus memberikan fungsi pembandingan tambahan kepada rutin pengurutan yang sudah built-in tersebut.

X Esc
Sebelum PgUp
Berikut PgDn

Catatan: Silahkan Sign up/Login sebelum mencoba latihan!


Test your understanding here!

X Esc
Sebelum PgUp
Berikut PgDn

Sekarang setelah anda mencapai akhir dari Kuliah Maya ini, apakah anda pikir masalah pengurutan sesimpel pemanggilan rutin pengurutan yang sudah built-in di berbagai bahasa pemrograman?


Cobalah masalah-masalah di online judge ini untuk menyelidiki lebih lanjut:
Kattis - mjehuric
Kattis - sortofsorting, atau
Kattis - sidewayssorting


Ini bukan akhir dari topik pengurutan. Ketika anda menjelajahi topik-topik lain di VisuAlgo, anda akan menyadari bahwa pengurutan adalah langkah pre-processing untuk banyak algoritma-algoritma tingkat lanjut lainnya untuk menyelesaikan masalah-masalah yang lebih sulit, contohnya sebagai langkah pre-processing untuk algoritma Kruskal, secara kreatif dipakai didalam struktur data Larik Akhiran (Suffix Array), dsb.

X Esc
Sebelum PgUp
Berikut PgDn
Selagi aksi dijalankan, tiap langkahnya akan dijelaskan pada panel status.
X Esc
Sebelum PgUp
Berikut PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc
Sebelum PgUp
Berikut PgDn
Kendalikan animasi dengan tombol kendali! Terdapat pula shortcut melalui keyboard:
Spasi: play/pause/replay
Panah kanan/kiri: maju ke depan/belakang
-/+: turunkan/tingkatkan kecepatan

X Esc
Sebelum PgUp
Berikut PgDn
Kembali ke 'Mode Eksplorasi' untuk memulai eksplorasi!

Harap diingat bahwa jika anda menemukan bug pada visualisasi ini atau bila anda ingin meminta fitur / visualisasi baru, jangan segan-segan untuk menghubungi pemimpin proyek ini: Dr Steven Halim melalui alamat emailnya: stevenhalim at gmail dot com.
X Esc
Sebelum PgUp

0 1 2 3 4 5 6 7 8 9

Buat

Urutkan

>

Acak

Terurut

Menaik

Menurun

Hampir terurut

Menaik

Menurun

Lakukan

Hitung Indeks Inversi

Lakukan

Tentang Tim Syarat Guna

Tentang

VisuAlgo digagas pada tahun 2011 oleh Dr Steven Halim sebagai alat untuk membantu murid-muridnya mengerti struktur data dan algoritma dengan memampukan mereka untuk mempelajari dasar-dasar struktur data dan algoritma secara otodidak dan dengan kecepatan mereka sendiri.


VisuAlgo mempunya banyak algoritma-algoritma tingkat lanjut yang dibahas didalam buku Dr Steven Halim ('Competitive Programming', yang ditulis bersama adiknya Dr Felix Halim) dan lebih lagi. Hari ini, beberapa dari visualisasi/animasi algoritma-algoritma tingkat lanjut ini hanya ditemukan di VisuAlgo.


Meskipun pada khususnya didesain untuk murid-murid National University of Singapore (NUS) yang mengambil berbagai kelas-kelas struktur data dan algoritma (contoh: CS1010, CS1020, CS2010, CS2020, CS3230, dan CS3233), sebagai pendukung pembelajaran online, kami berharap bahwa orang-orang di berbagai belahan dunia menemukan visualisasi-visualisasi di website ini berguna bagi mereka juga.


VisuAlgo tidak didesain untuk layar sentuh kecil (seperti smartphones) dari awalnya karena kami harus membuat banyak visualisasi-visualisasi algoritma kompleks yang membutuhkan banyak pixels dan gestur klik-dan-tarik untuk interaksinya. Resolusi layar minimum untuk pengalaman pengguna yang lumayan adalah 1024x768 dan hanya halaman utama VisuAlgo yang secara relatif lebih ramah dengan layar kecil.


VisuAlgo adalah proyek yang sedang terus berlangsung dan visualisasi-visualisasi yang lebih kompleks sedang dibuat.


Perkembangan yang paling menarik adalah pembuatan pertanyaan otomatis (sistem kuis online) yang bisa dipakai oleh murid-murid untuk menguji pengetahuan mereka tentang dasar-dasar struktur data dan algoritma. Pertanyaan-pertanyaan dibuat secara acak dengan semacam rumus dan jawaban-jawaban murid-murid dinilai secara instan setelah dikirim ke server penilai kami. Sistem kuis online ini, saat sudah diadopsi oleh banyak dosen Ilmu Komputer diseluruh dunia, seharusnya bisa menghapuskan pertanyaan-pertanyaan dasar tentang struktur data dan algoritma dari ujian-ujian di banyak Universitas. Dengan memberikan bobot kecil (tapi tidak kosong) supaya murid-murid mengerjakan kuis online ini, seorang dosen Ilmu Komputer dapat dengan signifikan meningkatkan penguasaan materi dari murid-muridnya tentang pertanyaan-pertanyaan dasar ini karena murid-murid mempunyai kesempatan untuk menjawab pertanyaan-pertanyaan ini yang bisa dinilai secara instan sebelum mereka mengambil kuis online yang resmi. Mode latihan saat ini mempunyai pertanyaan-pertanyaan untuk 12 modul visualisasi. Kami akan segera menambahkan pertanyaan-pertanyaan untuk 8 modul visualisasi lainnya sehingga setiap every modul visualisasi di VisuAlgo mempunyai komponen kuis online.


Cabang pengembangan aktif lainnya adalah sub-proyek penerjemahan dari VisuAlgo. Kami mau menyiapkan basis data kosa kata Ilmu Komputer dalam bahasa Inggris yang digunakan di sistem VisuAlgo. Ini adalah pekerjaan besar yang membutuhkan crowdsourcing. Saat sistem tersebut siap, kami akan mengundang beberapa dari anda untuk berkontribusi, terutama bila bahasa Inggris bukan bahasa ibu anda. Saat ini, kami juga telah menulis catatan-catatan publik tentang VisuAlgo dalam berbagai bahasa:
zh, id, kr, vn, th.

Tim

Pemimpin & Penasihat Proyek (Jul 2011-sekarang)
Dr Steven Halim, Senior Lecturer, School of Computing (SoC), National University of Singapore (NUS)
Dr Felix Halim, Software Engineer, Google (Mountain View)

Murid-Murid S1 Peniliti 1 (Jul 2011-Apr 2012)
Koh Zi Chun, Victor Loh Bo Huai

Murid-Murid Proyek Tahun Terakhir/UROP 1 (Jul 2012-Dec 2013)
Phan Thi Quynh Trang, Peter Phandi, Albert Millardo Tjindradinata, Nguyen Hoang Duy

Murid-Murid Proyek Tahun Terakhir/UROP 2 (Jun 2013-Apr 2014)
Rose Marie Tan Zhao Yun, Ivan Reinaldo

Murid-Murid S1 Peniliti 2 (May 2014-Jul 2014)
Jonathan Irvin Gunawan, Nathan Azaria, Ian Leow Tze Wei, Nguyen Viet Dung, Nguyen Khac Tung, Steven Kester Yuwono, Cao Shengze, Mohan Jishnu

Murid-Murid Proyek Tahun Terakhir/UROP 3 (Jun 2014-Apr 2015)
Erin Teo Yi Ling, Wang Zi

Murid-Murid Proyek Tahun Terakhir/UROP 4 (Jun 2016-Dec 2017)
Truong Ngoc Khanh, John Kevin Tjahjadi, Gabriella Michelle, Muhammad Rais Fathin Mudzakir

List of translators who have contributed ≥100 translations can be found at statistics page.

Ucapan Terima Kasih
Proyek ini dimungkinkan karena Hibah Pengembangan Pengajaran dari NUS Centre for Development of Teaching and Learning (CDTL).

Syarat Guna

VisuAlgo bebas biaya untuk komunitas Ilmu Komputer di dunia. Jika anda menyukai VisuAlgo, satu-satunya pembayaran yang kami minta dari anda adalah agar anda menceritakan keberadaan VisuAlgo kepada murid-murid/dosen-dosen Ilmu Komputer yang anda tahu =) lewat Facebook, Twitter, situs mata kuliah, ulasan di blog, email, dsb.


Jika anda adalah murid/dosen struktur data dan algoritma, anda diijinkan untuk menggunakan situs ini secara langsung di kelas-kelas anda. Jika anda mengambil screen shots (video-video) dari situs ini, anda dapat menggunakan screen shots (video-video) tersebut ditempat lain asalkan anda menyebut URL dari situs ini (http://visualgo.net) dan/atau daftar publikasi dibawah ini sebagai referensi. Tetapi, anda TIDAK diijinkan untuk mengunduh berkas-berkas VisuAlgo (sisi-klien) dan memasangnya di situs anda sendiri karena itu dikategorikan sebagai plagiat. Saat ini, kami TIDAK mengijinkan orang lain untuk membuat cabang/varian dari proyek VisuAlgo ini. Menggunakan kopi offline (sisi-klien) dari VisuAlgo untuk kepentingan pribadi diijinkan.


Ingat bahwa komponen kuis online dari VisuAlgo secara natur membutuhkan sisi-server dan tidak bisa dengan mudah disimpan di komputer lokal. Saat ini, publik hanya bisa menggunkaan 'mode latihan' untuk mengakses sistem kuis online. Saat ini, 'mode ujian' adalah sistem untuk mengakses pertanyaan-pertanyaan acak ini yang digunakan untuk ujian resmi di NUS. Dosen-dosen Ilmu Komputer yang lain harus menghubungi Steven jika anda mau mencoba 'mode ujian' tersebut.


Dafatar Publikasi


Karya ini telah dipresentasikan singkat pada CLI Workshop sewaktu ACM ICPC World Finals 2012 (Poland, Warsaw) dan pada IOI Conference di IOI 2012 (Sirmione-Montichiari, Italy). Anda bisa mengklik link ini untuk membaca makalah kami tahun 2012 tentang sistem ini (yang belum disebut sebagai VisuAlgo pada tahun 2012 tersebut).


Karya ini dibuat denbgan bantuan bekas murid-murid saya. Laporan-laporan proyek yang cukup mutakhir bisa dibaca disini: Erin, Wang Zi, Rose, Ivan.


Laporan Bug atau Meminta Fitur Baru


VisuAlgo bukanlah proyek yang sudah selesai. Dr Steven Halim masih aktif dalam mengembangkan VisuAlgo. Jika anda adalah pengguna VisuAlgo dan menemukan bug di halaman visualisasi/sistem kuis online atau jika anda mau meminta fitur baru, silahkan hubungi Dr Steven Halim. Alamat emailnya adalah gabungan dari namanya dan tambahkan gmail titik com.