Pengurutan Data
Pengantar Pengurutan DataProses pengurutan banyak ditemukan dalam komputer. Hal itu karena data yang sudah urut akan lebih cepat untuk dicari. Untuk membentuk data yang tidak urut menjadi data yang urut terdapat berbagai algoritma yang bisa digunakan.
Perlu diketahui bahwa pengurutan sendiri dapat dilakukan terhadap data yang secara keseluruhan diletakkan dalam memori ataupun terhadap data yang tersimpan pada pengingat eksternal.
Di dalam pengurutan data terdapat istilah ascending dan descending. Pengurutan dengan dasar dari nilai yang kecil menuju ke nilai yang besar disebut ascending (urut naik), sedangkan yang disusun atas dasar dari nilai besar ke kecil disebut descending (urut turun).
|
5
|
4
|
6
|
3
|
1
|
2
|
9
|
7
|
8
|
Data
tidak urut
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
Urut
naik (ascending)
|
9
|
8
|
7
|
6
|
5
|
4
|
3
|
2
|
1
|
Urut
turun (descending)
- Metode Bubble Sort
25 57 48 37 12 92 80 33
Contoh proses pengurutan dengan urut
naik:
Tahap Pertama
|
25
|
57
|
48
|
37
|
12
|
92
|
80
|
33
|
25 < > 57
48 < > 57
37 < > 57
12 < > 57
57 <
> 92
80 < > 92
33
< > 92
Contoh proses pengurutan dengan urut
naik:
TahapKedua
|
25
|
48
|
37
|
12
|
57
|
80
|
33
|
92
|
25 < > 48
37 < > 48
12 < > 48
48 < > 57
57 <
> 80
33 < > 80
Jika jumlah data adalah n maka terjadi n-1 tahap pengurutan. Berarti pada contoh di atas diperlukan 7 tahap pengurutan. Berikut ini merupakan data yang memperlihatkan keadaan setelah 7 tahap pengurutan dilakukan.
|
Awal
|
25
|
57
|
48
|
37
|
12
|
92
|
80
|
33
|
|
Tahap 1
|
25
|
48
|
37
|
12
|
57
|
80
|
33
|
92
|
|
Tahap 2
|
25
|
37
|
12
|
48
|
57
|
33
|
80
|
92
|
|
Tahap 3
|
25
|
12
|
37
|
48
|
33
|
57
|
80
|
92
|
|
Tahap 4
|
12
|
25
|
37
|
33
|
48
|
57
|
80
|
92
|
|
Tahap 5
|
12
|
25
|
33
|
37
|
48
|
57
|
80
|
92
|
|
Tahap 6
|
12
|
25
|
33
|
37
|
48
|
57
|
80
|
92
|
|
Tahap 7
|
12
|
25
|
33
|
37
|
48
|
57
|
80
|
92
|
- Metode Pengurutan Seleksi
Pengurutan seleksi (selection sort) mempunyai mekanisme
seperti berikut: Mula-mula suatu penunjuk (diberi nama posAwal),
yang menunjuk ke lokasi awal pengurutan data, diatur agar berisi indeks pertama
dalam larik. Selanjutnya, dicari bilangan terkecil yang terletak antara posisi sesudah
yang ditunjuk oleh penunjuk tersebut hingga elemen yang terakhir dalam larik.
Lokasi bilangan ini ditunjuk oleh posMin. Lalu, tukarkan nilai bilangan
terkecil tersebut dengan nilai yang ditunjuk oleh posAwal.
Proses seperti itu diulang dari posAwal bernilai 0 hingga n-1, dengan n
menyatakan jumlah elemen dalam larik.
- Metode Quick Sort
Quick sort adalah metode pengurutan data yang ditemukan
pertama kali oleh C. A.R. Hoare pada tahun 1962. Metode ini menggunakan
strategi “pecah-belah” dengan mekanisme seperti berikut: Larik L[p..r] (dengan
indeks terkecil adalah p dan indeks terbesar, yaitu r), disusun ulang
(dipartisi) menjadi dua larik A[p..q] dan A[q+1..r] sehingga setiap elemen
dalam A[p..q] selalu bernilai lebih kecil daripada setiap nilai elemen pada A[q+1..r].
Selanjutnya, kedua larik tersebut diurutkan secara rekursif. Dengan sendirinya
kombinasi kedua larik tersebut membentuk larik dengan data yang telah urut.
Tidak ada komentar:
Posting Komentar