Pengurutan (Sorting)
Pengurutan data (sorting) didefinisikan sebagai suatu proses untuk menyusun kembali humpunan obyek menggunakan aturan tertentu. Mnurut Microsoft Book-shelf, definisi algoritma pengurutan adalah algoritma untuk meletakkan kumpulan elemen data ke dalam urutan tertentu berdasarkan satu atau beberapa kunci dalam tiap-tiap elemen.
Ada dua macam urutan yang biasa digunakan dalam proses pengurutan yaitu
• urut naik (ascending) yaitu dari data yang mempunyai nilai paling kecil sampai paling besar
• urut turun (descending) yaitu data yang mempunyai nilai paling besar sampai paling kecil.
Contoh : data bilangan 5, 2, 6 dan 4 dapat diurutkan naik menjadi 2, 4, 5, 6 atau diurutkan turun menjadi 6, 5, 4, 2. Pada data yang bertipe char, nilai data dikatakan lebih kecil atau lebih besar dari yang lain didasarkan pada urutan relatif (collating sequence) seperti dinyatakan dalam tabel ASCII (Lampiran)
Keuntungan dari data yang sudah dalam keadaan terurutkan antara lain :
• data mudah dicari (misalnya dalam buku telepon atau kamus bahasa), mudah untuk dibetulkan, dihapus, disisipi atau digabungkan. Dalam keadaan terurutkan, kita mudah melakukan pengeekan apakah ada data yang hilang
• melakukan komppilasi program komputer jika tabel-tabel simbol harus dibentuk
• mempercepat proses pencarian data yang harus dilakukan berulang kali.
Data yang diurutkan sangat bervariasi, dalam hal jumlah data maupun jenis data yang akan diurutkan. Tidak ada algoritma terbaik untuk setiap situasi yang kita hadapi, bahkan cukup sulit untuk menentukan algoritma mana yang paling baik untuk situasi tertentu karena ada beberapa faktor yang mempengaruhi efektifitas algoritma pengurutan. Beberapa faktor yang berpengaruh pada efektifitas suatu algoritma pengurutan antara lain:
• banyak data yang diurutkan
• kapasitas pengingat apakah mampu menyimpan semua data yang kita miliki
• tempat penyimpanan data, misalnya piringan, pita atau kartu, atau media penyimpan yang lain.
Pemilihan algoritma sangat ditentukan oleh struktur data yang digunakan. Metode pengurutan yang digunakan dapat diklasifikasikan menjadi dua katagori yaitu :
• pengurutan internal, yaitu pengurutan dengan menggunakan larik (array). Larik tersimpan dalam memori utama komputer
• pengurutan eksternal, yaitu pengurutan dengan menggunakan berkas (sequential access file). Berkas tersimpan dalam pengingat luar, misalnya cakram atau pita magnetis.
Untuk menggambarkan pengurutan dengan larik, bisa kita bayangkan semua kartu terletak di hadapan kita sehingga semua kartu terlihat dengan jelas nomornya. Pada penyusunan kartu sebagai sebuah berkas, kita bayangkan semua kartu kita tumpuk sehingga hanya kartu bagian atas saja yang bisa kita lihat nomornya.
Pada bab ini akan dijelaskan beberapa metode pengurutan beserta analisanya.
6.1 Deklarasi Larik
Pada pengurutan larik, ada beberapa aspek yang perlu dipertimbangkan, antara lain aspek menyangkut kapasitas pengingat yang ada dan aspek waktu, yaitu waktu yang diperlukan untuk melakukan permutasi sehingga semua elemen akhirnya menjadi terurutkan.
Deklarasi larik yang digunakan adalah larik dimensi satu (vektor) dengan elemennya bertipe integer.
#define Max 100;
int Data[Max];
Pada deklarasi diatas, Max adalah banyaknya elemen vektor. Anda bisa mengubah nilai konstantaa Max sesuai kebutuhan. Indeks larik dimulai dari 0. Data yang sebenarnya disimpan mulai dari indeks 0.
Selain deklarasi diatas, proses yang juga selalu digunakan pada algoritma pengurutan adalah proses menukarkan elemen. Di bawah ini satu prosedur sederhana untuk menukarkan nilai dua buah elemen A dan B.
void Tukar (int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
Program 6.1 Prosedur Penukaran 2 Bilangan
Prosedur tukar diatas akan digunakan pada beberapa prosedur pengurutan yang akan dijelaskan dibawah ini
6.2 Metode Penyisipan Langsung (Straight Insertion Sort)
Proses pengurutan dengan metode penyisipan langsung dapat dijelaskan sebagai berikut :
Data dicek satu per satu mulai dari yang kedua sampai dengan yang terakhir. Apabila ditemukan data yang lebih kecil daripada data sebelumnya, maka data tersebut disisipkan pada posisi yang sesuai. Akan lebih mudah apabila membayangkan pengurutan kartu. Pertama-tama anda meletakkan kartu-kartu tersebut di atas meja, kemudian melihatnya dari kiri ke kanan. Apabila kartu di sebelah kanan lebih kecil daripada kartu di sebelah kiri, maka ambil kartu tersebut dan sisipkan di tempat yang sesuai.
Algoritma penyisipan langsung dapat dituliskan sebagai berikut :
1 i ← 1
2 selama (i < N) kerjakan baris 3 sampai dengan 9
3 x ← Data[i]
4 j ← i – 1
5 selama (x < Data[j]) kerjakan baris 6 dan 7
6 Data[j + 1] ← Data[j]
7 j ← j – 1
8 Data[j+1] ← x
9 i ← i + 1
Untuk lebih memperjelas langkah-langkah algoritma penyisipan langsung dapat dilihat pada tabel 6.1. Proses pengurutan pada tabel 6.1 dapat dijelaskan sebagai berikut:
• Pada saat i=1, x sama dengan Data[1] = 35 dan j=0. Karena Data[0] = 12 dan 35 > 12 maka proses dilanjutkan untuk i=2.
• Pada saat i=2, x = Data[2] = 9 dan j=1. Karena Data[1] = 35 dan 9 < 35, maka dilakukan pergeseran sampai ditemukan data yang lebih kecil dari 9. Hasil pergeseran ini, Data[1] = 12 dan Data[2] = 35 sedangkan Data[0] = x = 9.
• Pada saat i=3, x = Data[3] = 11 dan j=3. Karena Dataa[2] = 35 dan 11 < 35, maka dilakukan pergeseran sampai ditemukan data yang lebih kecil dari 11. Hasil pergeseran ini, Data[2] = 12 dan Data[3] = 35 sedangkan Data[1] = x = 11.
• Dan seterusnya.
Tabel 6.1 Proses Pengurutan dengan Metode Penyisipan Langsung
Iterasi
|
Data[0]
|
Data[1]
|
Data[2]
|
Data[3]
|
Data[4]
|
Data[5]
|
Data[6]
|
Data[7]
|
Data[8]
|
Data[9]
|
Awal
|
12
|
35
|
9
|
11
|
3
|
17
|
23
|
15
|
31
|
20
|
i=1
|
12
|
35
|
9
|
11
|
3
|
17
|
23
|
15
|
31
|
20
|
i=2
|
12
|
35
|
9
|
11
|
3
|
17
|
23
|
15
|
31
|
20
|
i=3
|
9
|
12
|
35
|
11
|
3
|
17
|
23
|
15
|
31
|
20
|
i=4
|
9
|
11
|
12
|
35
|
3
|
17
|
23
|
15
|
31
|
20
|
i=5
|
3
|
9
|
11
|
12
|
35
|
17
|
23
|
15
|
31
|
20
|
i=6
|
3
|
9
|
11
|
12
|
17
|
35
|
23
|
15
|
31
|
20
|
i=7
|
3
|
9
|
11
|
12
|
17
|
23
|
35
|
15
|
31
|
20
|
i=8
|
3
|
9
|
11
|
12
|
15
|
17
|
23
|
35
|
31
|
20
|
i=9
|
3
|
9
|
11
|
12
|
15
|
17
|
23
|
31
|
35
|
20
|
Akhir
|
3
|
9
|
11
|
12
|
15
|
17
|
20
|
23
|
31
|
35
|
Di bawah ini merupakan prosedur yang menggunakan metode penyisipan langsung.
void StraighInsertSort()
{
int i, j, x;
for(i=1; i<Max; i++){
x = Data[i];
j = i - 1;
while (x < Data[j]){
Data[j+1] = Data[j];
j--;
}
Data[j+1] = x;
}
}
Program 6.2 Prosedur Pengurutan dengan Metode Penyisipan Langsung
Dari algoritma dan prosedur diatas, jumlah perbandingan (=C) minimum, rata-rata dan maksimum pada metode penyisipan langsung adalah
Cmin = N – 1
Crata-rata = (N2 + N + 2) / 4
Cmax = (N2 + N – 2) / 2
Jumlah perbandingan minimum terjadi jika data sudah dalam keadaan urut, sebaliknya jumlah perbandingan maksimum terjadi jika data dalam keadaan urut terbalik.
Cara menghitung Cmin adalah dengan melihat kalang paling luar yaitu i, pengulangan ini dimulai dari 1 sampai dengan N-1 atau sama dengan N-1
Cara menghitung Cmax dengan menganggap selalu terjadi pergeseran. Kalang dalam (while) diatas akan melakukan pengulangan dari 0 sampai dengan i. Apabila hal ini dilakukan sebanyak N-1 kali, maka Cmax adalah jumlah dari deret aritmetik 2, 3, 4, ..., N atau (N – 1) / 2 . (2 + N)
Cara menghitung Crata-rata adalah dengan menjumlahkan Cmin dan Cmax dan dibagi dengan 2.
Jumlah penggeseran (=M) minimum, rata-rata dan maksimum untuk metode penyisipan langsung adalah :
Mmin = 2(N – 1)
Mrata-rata = (N2 + 7N - 8) / 4
Mmax = (N2 + 3N – 4) / 2
6.3 Metode Penyisipan Biner (Binary Insertion Sort)
Metode ini merupakan pengembangan dari metode penyisipan langsung. Dengan cara penyisipan langsung, perbandingan selalu dimulai dari elemen pertama (data ke-0), sehingga untuk menyisipkan elemen ke i kita harus melakukan perbandingan sebanyak i-
1 kali. Ide dari metode ini didasarkan pada kenyataan bahwa pada saat menggeser data ke-i, data ke 0 s/d i-1 sebenarnya sudah dalam keadaan terurut. Sebagai contoh pada
tabel 6.1 diatas, pada saat i=4, data ke 0 s/d 3 sudah dalam keadaan urut : 3, 9, 12, 35.
Dengan demikian posisi dari data ke-i sebenarnya dapat ditentukan dengan pencarian
biner.
Misalnya pada saat i = 7, data yang akan dipindah adalah 15 sedangkan data di sebelah kiri 15 adalah sebagai berikut :
Pertama-tama dicari data pada posisi paling tengah diantara data diatas. Data yang terletak di tengah adalah data ke-3, yaitu 12. Karena 12 < 15, berarti 15 harus disisipkan di sebelah kanan 12. Oleh karena itu, proses pencarian dlanjutkan lagi untuk
data berikut
17 23 35
Dari hasil ini, didapat data tengahnya adalah data 23. Karena 15 < 23, berarti 15 harus disisipkan di sebelah kiri 23. Proses dilanjutkan kembali untuk data
Karena 17 > 15, berarti 15 harus disisipkan di sebelah kiri 17
Algoritma penyisipan biner dapat dituliskan sebagai berikut :
1 i ← 1
2 selama (i < N) kerjakan baris 3 sampai dengan 14
3 x ← Data[i]
4 l ← 0
5 r ← i – 1
6 selama (l<=r) kerjakan baris 7 dan 8
7 m ← (l + r) / 2
8 jika (x < Data[m]) maka r ← m – 1, jika tidak l ← m + 1
9 j ← i – 1
10 selama ( j >=l) kerjakan baris 11 dan 12
11 Data[j+1] ← Data[j]
12 j ← j – 1
13 Data[l] ← x
14 I ← i + 1
Di bawah ini merupakan prosedur yang menggunakan metode penyisipan biner.
void BinaryInsertSort()
{
int i, j, l, r, m, x;
for (i=1; i<Max; i++){
x = Data[i];
l = 0;
r = i - 1;
while(l <= r){
m = (l + r) / 2;
if(x < Data[m])
r = m - 1;
else
l = m + 1;
}
for(j=i-1; j>=l; j--) Data[j+1] = Data[j];
Data[l]=x;
}
}
Program 6.3 Prosedur Pengurutan dengan Metode Penyisipan Biner
Dari algoritma dan prosedur diatas, jumlah perbandingan (=C) untuk metode penyisipan biner adalah :
C = ∑ 2log(i)
Sedangkan jumlah penggeseran (=M) untuk metode penyisipan biner sama dengan metode penyisipan langsung.
6.4 Metode Seleksi (Selection Sort)
Metode seleksi melakukan pengurutan dengan cara mencari data yang terkecil kemudian menukarkannya dengan data yang digunakan sebagai acuan atau sering dinamakan pivot.
Proses pengurutan dengan metode seleksi dapat dijelaskan sebagai berikut : langkah pertama dicari data terkecil dari data pertama sampai data terakhir. Kemudian data terkecil ditukar dengan data pertama. Dengan demikian, data pertama sekarang
mempunyai nilai paling kecil dibanding data yang lain. Langkah kedua, data terkecil kita
cari mulai dari data kedua sampai terakhir. Data terkecil yang kita peroleh ditukar dengan data kedua dan demikian seterusnya sampai semua elemen dalam keadaan terurutkan.
Algoritma seleksi dapat dituliskan sebagai berikut :
1 i ← 0
2 selama (i < N-1) kerjakan baris 3 sampai dengan 9
3 k ← i
4 j ← i + 1
5 Selama (j < N) kerjakan baris 6 dan 7
6 Jika (Data[k] > Data[j]) maka k ← j
7 j ← j + 1
8 Tukar Data[i] dengan Data[k]
9 i ← i + 1
Untuk lebih memperjelas langkah-langkah algoritma seleksi dapat dilihat pada tabel 6.2. Proses pengurutan pada tabel 6.2 dapat dijelaskan sebagai berikut:
• Pada saat i=0, data terkecil antara data ke-1 s/d ke-9 adalah data ke-4, yaitu 3, maka data ke-0 yaitu 12 ditukar dengan data ke-4 yaitu 3.
• Pada saat i=1, data terkecil antara data ke-2 s/d ke-9 adalah data ke-2, yaitu 9, maka data ke-1 yaitu 35 ditukar dengan data ke-2 yaitu 9.
• Pada saat i=2, data terkecil antara data ke-3 s/d ke-9 adalah data ke-3, yaitu 11, maka data ke-2 yaitu 35 ditukar dengan data ke-3 yaitu 11.
• Pada saat i=3, data terkecil antara data ke-4 s/d ke-9 adalah data ke-4, yaitu 12, maka data ke-3 yaitu 35 ditukar dengan data ke-4 yaitu 12.
• Dan seterusnya.
Tabel 6.2 Proses Pengurutan dengan Metode Seleksi
Iterasi
|
Data[0]
|
Data[1]
|
Data[2]
|
Data[3]
|
Data[4]
|
Data[5]
|
Data[6]
|
Data[7]
|
Data[8]
|
Data[9]
|
Awal
|
12
|
35
|
9
|
11
|
3
|
17
|
23
|
15
|
31
|
20
|
i=0
|
12
|
35
|
9
|
11
|
3
|
17
|
23
|
15
|
31
|
20
|
i=1
|
3
|
35
|
9
|
11
|
12
|
17
|
23
|
15
|
31
|
20
|
i=2
|
3
|
9
|
35
|
11
|
12
|
17
|
23
|
15
|
31
|
20
|
i=3
|
3
|
9
|
11
|
35
|
12
|
17
|
23
|
15
|
31
|
20
|
i=4
|
3
|
9
|
11
|
12
|
35
|
17
|
23
|
15
|
31
|
20
|
i=5
|
3
|
9
|
11
|
12
|
15
|
17
|
23
|
35
|
31
|
20
|
i=6
|
3
|
9
|
11
|
12
|
15
|
17
|
23
|
35
|
31
|
20
|
i=7
|
3
|
9
|
11
|
12
|
15
|
17
|
20
|
35
|
31
|
23
|
i=8
|
3
|
9
|
11
|
12
|
15
|
17
|
20
|
23
|
31
|
35
|
Akhir
|
3
|
9
|
11
|
12
|
15
|
17
|
20
|
23
|
31
|
35
|
Di bawah ini merupakan prosedur yang menggunakan metode seleksi.
void SelectionSort()
{
int i, j, k;
for(i=0; i<Max-1;i++){
k = i;
for (j=i+1; j<Max; j++)
if(Data[k] > Data[j])
k = j; Tukar(&Data[i], &Data[k]);
}
}
Program 6.4 Prosedur Pengurutan dengan Metode Seleksi
adalah
Dari algoritma dan prosedur diatas, jumlah perbandingan (=C) metode seleksi
C = N(N – 1) / 2
Jumlah penukaran (=M) pada metode seleksi tergantung keadaan datanya.
Penukaran minimum terjadi bila data sudah dalam keadaan urut, sebaliknya jumlah penukaran maksimum terjadi bila data dalam keadaan urut terbalik. Jumlah penukaran minimum dan maksimum dapat dirumuskan sebagai berikut :
Mmin = 3(N – 1)
Mmax = N2 / 4 + 3(N – 1)
SEBELUM ANDA ANDA MENGCOPY PASTE SELURUH ARTIKEL INI, MOHON DI SERTAKAN SUMBERNYA
SHARE KLIK ICON FB / TWITTER DI KANAN ATAS