Pengurutan (sorting) adalah proses mengatur sekumpulan objek menurut
urutan atau susunan tertentu. Urutan objek tersebut dapat menaik (ascending) atau
menurun (descending). Bila N buah objek atau data disimpan di dalam larik L,
maka pengurutan menaik berarti menyusun elemen larik sedemikian sehingga:
L[1] _ L[2] _ L[3 _ … _ L[N]
Sedangkan pengurutan menurun berarti menyusun elemen larik sedemikian
sehingga:
L[1] _ L[2] _ L[3 _ … _ L[N]
Data yang diurut dapat berupa data bertipe dasar atau tipe terstruktur (record).
Jika data bertipe terstruktur, maka harus dispesifikasikan berdasarkan field apa
data tersebut diurutkan. Field yang dijadikan dasar pengurutan dikenal sebagai
field kunci.Adanya kebutuhan terhadap proses pengurutan memunculkan bermacammacam
metode pengurutan. Metode tersebut diantaranya adalah: 1) Metode
Pengurutan Gelembung (Bubble Sort), 2) Metode Pengurutan Pilih (Selection
Sort), 3) Metode Pengurutan Sisip (Insertion Sort), 4) Metode Pengurutan Shell
(Shell Sort), 5) Heap Sort, 6) Quick Sort, 7) Merge Sort, 8) Radix Sort dan 9)
Tree Sort. Pada modul ini, tidak semua metode pengurutan akan dibahas.
Tidak ada metode yang terbaik untuk pengurutan. Kebanyakan metode
pengurutan sederhana hanya bagus untuk volume data yang kecil tetapi lambat
untuk ukuran data yang besar. Metode pengurutan yang lebih cepat pun (seperti
quick sort dan merge sort) memang bagus untuk mengurutkan data yang banyak,
tetapi tidak bagus untuk ukuran data yang sedikit karena memerlukan beban
tambahan (overhead) yang boros waktu dan memori.
Metode pengurutan dapat diklasifikasikan sebagai berikut:
a. Metode pengurutan internal, yaitu metode pengurutan untuk data yang
disimpan di dalam memori computer. Umumnya struktur internal yang
dipakai untuk pengurutan internal adalah larik, sehingga pengurutan
internal disebut juga pengurutan larik.
b. Metode pengurutan eksternal, yaitu metode pengurutan untuk data
yang disimpan di dalam disk storage, disebut juga pengurutan arsip
(file), karena struktur eksternal yang dipakai adala