STRUKTUR DATA
“SORTING (PENGURUTAN)”
PENGANTAR
Pengurutan adalah salah satu bagian terpenting
didalam struktur data
Hal ini disebabkan karena kita selalu ingin
menggunakan data dalam bentuk yang rapi atau
berpola sesuai dengan keinginan kita
PENDAHULUAN
Pengurutan data(sorting) didefinisikan sebagai suatu proses untuk
menyusun kembali himpunan obyek menggunakan aturan tertentu.
Menurut Microsoft Bookshelf, 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 dalam pengurutan yaitu:
Urut naik(ascending) yaitu urutan data dari nilai paling kecil ke
paling besar. Contoh: 2, 4, 5, 6
Urut turun(descending) yaitu urutan data dari nilai paling besar
ke paling kecil. Contoh: 6, 5, 4, 2
Pada data yang bertipe char, nilai data dikatakan lebih kecil atau besar
didasarkan pada urutan relatif (collating squence) seperti yang
dinyatakan pada tabel ASCII
Keuntungan data yang sudah terurut, antara lain:
Data mudah dicari, diupdate, dihapus, disisipi atau digabungkan. Juga
mudah dilakukan pengecekan apakah ada data hilang atau tidak
Melakukan kompilasi program komputer jika tabel-tabel simbol harus
dibentuk
Mempercepat proses pencarian data yang harus dilakukan berulang
kali
Beberapa faktor yang mempengaruhi efektifitas suatu
algoritma pengurutan, antara lain:
Banyaknya data yang diurutkan
Kapasitas memori yang terbatas
Jenis tempat penyimpanan, misalnya piringan, pita atau kartu, atau
media penyimpan yang lain
Metode pengurutan yang digunakan dapat
diklasifikasikan menjadi dua kategori, 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 memori luar, misalnya cakram atau
pita magnetis.
PENGURUTAN LARIK(ARRAY)
Deklarasi larik yang digunakan dibawah ini adalah larik dimensi satu(vektor)
dengan elemennya bertipe integer.
#define MAX 100 /* jumlah maksimal elemen vektor
*/
int data[MAX];
Pada pengurutan, penukaran antar elemen selalu digunakan. Berikut ini
merupakan fungsi dalam bahasa C untuk menukarkan dua elemen:
void tukar(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
DEFENISI SORTING
Pengurutan (Sorting) adalah proses mengatur sekumpulan
objek menurut aturan atau susunan tertentu
Urutan objek tersebut dapat menaik (ascending) atau
menurun (descending)
Jika N buah objek atau data disimpan didalam array Nilai,
maka pengurutan menaik adalah :
Nilai[0]≤Nilai[1] ≤Nilai[2] ≤… ≤Nilai[N-1]
Untuk pengurutan menurun adalah :
Nilai[0]≥Nilai[1] ≥Nilai[2] ≥… ≥Nilai[N-1]
METODE SORTING
Beberapa metode pengurutan yaitu :
Penyisipan Langsung
Penyisipan Biner
Bubble sort
Selection sort
Quick sort
Merge sort
Shell sort
Maximum sort
Insertion sort
METODE PENYISIPAN LANGSUNG
Pengurutan metode penyisipan langsung dapat dijelaskan sebagai berikut:
Data dicek satu per satu mulai dari kedua sampai terakhir. Jika ditemukan ada data
yang lebih kecil dibandingkan dengan data sebelumnya, maka data tersebut
ditempatkan pada posisi yang sesuai .
Algoritma:
1. i1
2. selama (i < N) kerjakan baris 3 sampai dengan 9
3. x data[i]
4. ji–1
5. selama (x < data[j]) kerjakan langkah 6 dan 7
6. data[j+1] data[j]
7. j j – 1
8. data[j+1] x
9. i i + 1
SAMBUNGAN.
Pengurutan dengan metode penyisipan langsung
iter data Data Data Data Data Data Data Data Data Data
I [0] [1] [2] [3] [4] [5] [6] [7] [8] [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 23 20 31 35
Fungsi metode penyisipan langsung
void straightInsertSort()
{
int i, j, x;
for(i=1; i<MAX; i++) {
x = data[i];
j = i – 1;
while (x < data[j]) {
data[j+i] = data[j];
j--;
}
data[j+1] = x;
}
}
Jumlah perbandingan(C) metode diatas dapat dicari dengan rumus:
Cmin = N – 1
Crata-rata = (N2 + N + 2) / 4
Cmax = (N2 + N – 2) / 2
Jumlah perbandingan minimum terjadi jika larik data dalam keadaan urut, sebaliknya perbandingan
maksimum terjadi jika larik data dalam keadaan urut terbalik.
Jumlah pergeseran(M) dapat dihitung dengan rumus:
Mmin = 2(N-1)
Mrata-rata = (N2 + 7N – 8) / 4
Mmax = (N2+ 3N – 4) / 2
METODE PENYISIPAN BINER
Merupakan metode pengembangan metode penyisipan langsung
Pada metode ini, pencarian posisi tidak dilakukan dari 0 tetapi membagi dua
deretan data terurut pada indeks 0:i-1 sehingga didapatkan data tengah. Kemudian
membandingkan data tengah dengan data sisip jika data tengah lebih kecil dari
data sisip maka data akan disisipkan disebelah kanan data sisip. Proses pembagian
dan perbandingan terus dilakukan sampai data sisip mendapat posisi yang sesuai.
Algoritma
1. i1
2. Selama (i < N) kerjakan baris 3 sampai dengan 14
3. x data[i]
4. kiri 0
5. kanan i – 1
6. Selama (kiri <= kanan) kerjakan baris 7 dan 8
7. tengah (kiri + kanan) / 2
8. Jika (x data[tengah]) maka kanan tengah – 1, jika tidak, kiri tengah + 1
9. j i – 1
10. Selama ( j >= kiri) kerjakan baris 11 dan 12
11. Data[i+1] data[j]
12. jj–1
13. Data[kiri] x
14. Kiri i + 1
SAMBUNGAN.
Berikut ini fungsi metode penyisipan biner dalam bahasa C
void sisipLangsungBiner()
{
int i, j, kiri, kanan, tengah, x;
for(i=1; i < MAX; i++) {
x = data[i];
kiri = 0;
kanan = i – 1;
while(kiri <= kanan) {
tengah = (kiri + kanan) / 2;
if (x < data[tengah])
kanan = tengah - 1;
else
kiri = tengah + 1;
}
for (j=i–1; j>=kiri; j--)
data[j+1] = data[j];
data[kiri] = x;
}
}
JUMLAH PERBANDINGAN DAN PENGGESERAN
Jumlah perbandingan(C) adalah
C = ∑ | 2log(i) |
Jumlah pergeseran(M) sama dengan metode
penyisipan langsung
METODE SELEKSI
Metode seleksi merupakan metode pengurutan data dengan cara
mencari data yang terkecil kemudian menukarkannya dengan data
yang digunakan sebagai acuan.
Proses pengurutan dijelaskan sebagai berikut:
Langkah pertama dicari data terkecil dari data pertama sampai
data terakhir. Kemudian data terkecil ditukar dengan data pertama.
Langkah kedua, data terkecil kita cari dari data kedua sampai
terakhir. Data terkecil yang kita peroleh ditukar dengan data kedua
dan demikian seterusnya sampai semua elemen dalam keadaan
terurutkan.
Metode Seleksi
3 10 4 6 8 9 7 2 1 5
Cari dalam keseluruhan array, temukan
nilai terbesar, (10) dan tukar nilai ini
dengan nilai yang tersimpan dalam lokasi
terakhir dari array (5)
3 10 4 6 8 9 7 2 5
1
3 5 4 6 8 9 7 2 1 10
Temukan nilai terbesar kedua dalam
array (9), tukar dengan nilai yang
tersimpan dalam lokasi terakhir kedua(1).
3 5 4 6 8 9 7 2 1 10
1
3 5 4 6 8 1 7 2 9 10
3 5 4 6 8 1 7 2 9 10
Dua nilai terakhir yang bertanda biru merupakan
posisi yang pasti karena keduanya merupakan
nilai terbesar dan nilai terbesar kedua.
Sekarang, ulangi proses “seleksi dan tukar” …
3 5 4 6 8 1 7 2 9 10
8 2
3 5 4 6 2 1 7 8 9 10
7
3 5 4 6 2 1 7 8 9 10
3 5 4 6 2 1 7 8 9 10
6 1
3 5 4 1 2 6 7 8 9 10
3 5 4 1 2 6 7 8 9 10
5 2
3 2 4 1 5 6 7 8 9 10
3 2 4 1 5 6 7 8 9 10
4 1
3 2 1 4 5 6 7 8 9 10
3 2 1 4 5 6 7 8 9 10
3 1
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
ALGORITMA
[Link] langkah 2-7 untuk i=0 s/d n-2
[Link] = data[i]
[Link] langkah 4 untuk j=i+1 s/d n-1
[Link] langkah 5-6 jika data[j]<min
[Link] = data[j]
6.min_id=j
[Link] data[i] dengan data[min_id]
METODE BUBBLE SORT
• Metode bubble sort, merupakan metode pengurutan yang
membandingkan elemen yang sekarang dengan elemen-elemen
berikutnya
Metode gelembung (Bubble Sort) adalah metode yang mengurutkan data
dengan cara membandingkan masing-masing elemen, kemudian
melakukan penukaran bila perlu.
Metode ini metode yang paling mudah tetapi yang paling tidak efisien.
Perbandingan elemen dapat dimulai dari awal atau yang paling akhir
Aturannya :
• Apabila elemen yang sekarang lebih besar (urut menurun), atau lebih
kecil (urut menaik) dari elemen berikutnya, maka posisi ditukar
tetapi jika tidak maka posisinya tetap
METODE BUBBLE SORT
Contoh
• Misalkan kita memiliki array Nilai sebanyak 8 elemen
akan diurutkan secara menaik menggunakan metode
Bubble sort : 25, 72, 30, 45, 20, 15, 6, 50
• Pengurutannya dimulai dari belakang
25 72 30 45 20 15 6 50
25 72 30 45 20 6 15 50
25 72 30 45 6 20 15 50
25 72 30 6 45 20 15 50 Langkah 1
25 72 6 30 45 20 15 50
25 6 72 30 45 20 15 50
6 25 72 30 45 20 15 50
METODE BUBBLE SORT
Langkah 2
6 25 72 30 45 20 15 50
6 25 72 30 45 15 20 50
6 25 72 30 15 45 20 50
6 25 72 15 30 45 20 50
6 25 15 72 30 45 20 50
6 15 25 72 30 45 20 50
Langkah 3
6 15 25 72 30 45 20 50
6 15 25 72 30 20 45 50
6 15 25 72 20 30 45 50
6 15 25 20 72 30 45 50
6 15 20 25 72 30 45 50
METODE BUBBLE SORT
Langkah 4
6 15 20 25 72 30 45 50
6 15 20 25 30 72 45 50
Langkah 5
6 15 20 25 30 72 45 50
6 15 20 25 30 45 72 50
Langkah 6
6 15 20 25 30 45 72 50
6 15 20 25 30 45 50 72
Fungsi dalam bahasa C metode bubble sort
void bubbleSort()
{
int i, j;
for (i=1; i < MAX-1; i++)
for (j=MAX-1; j >=i; j--)
if (data[j-1] > data[j])
tukar(&data[j-1, &data[j]);
}