Definisi Sorting atau Pengurutan

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