PENGURUTAN DATA A. Tujuan Pembahasan dalam bab ini adalah mengenai pengurutan data pada sekumpulan data. Terdapat beberapa metode untuk melakukan pengurutan data yang secara detil akan dibahas didalam bab ini.
Tujuan dari akhir pembahasan ini, pembaca diharapkan: 1. Memahami konsep pengurutan data dengan beberapa metode yaitu buble sort, selection, insertion sort, quick sort, dan merger sort 2. Mampu menganalisa metode-metode pengurutan data sehingga dapat memilih metode yang tepat dalam melakukan pngurutan data. B. Pengurutan (Sorting) Sekumpulan data yang banyak, dalam pemanfaatanya kadang-kadang diperlukan suatu pengrutan (sorting). Dalam kenyataanya, banyak sekali kasus yang dapat dijumpai. Sebagai contoh daftar nama pegawai atau lembar absensi biasanya dicetak berdasarkan urutan abjad. Buku-buku didalam perpustakaan disusun berdasarkan urutan tertentu. Pengurutan data biasanya juga digunakan untuk mempermudah pencarian data. Pengurutan atau sorting merupakan sebuah proses untuk menyusun kembali kumpulan entri-entri data yang telah dimasukan dengan suatu aturan tertentu. secara umum terdapat dua macam pengurutan yaitu pengurutan secara menaik (ascending) dan pengurutan secara menurun (descending). Pada saat data dimasukan kedalam komputer, proses memasukan data tersebut tidak dilakukan pengurutan terlebih dahulu. Beberapa hal yang menyebabkan data tidak diiurutkan pada saat dimasukan adalah proses memasukan data secara keseluruhan tidak selalu dimasukan pada saat yang sama, selain itu dibutuhkan waktu yang cukup lama untuk melakukan pengurutan data secara manual. Proses pengurutan data akan lebih mudah apabila data telah dimasukkan kedalam komputer dan proses pengurutan ini akan dilakukan oleh komputer.
1
C. Metode Pengurutan Data Pengurutan data terdapat beberapa metode yang dapat digunakan. Metode-metode pengurutan data tersebut adalah metode penyisipan (insertion sort), metode gelembung (buble sort), metode seleksi (selection sort), metode penggabungan (merge sort), dan metode quick sort. Metode-metode tersebut akan secara detil dibahas dalam bagianbagian berikutnya.
1. Metode Gelembung(Buble Sort) Metode pengurutan data secara gelembung adalah metode pengurutan data dengan cara menukar data yang memiliki nilai besar akan berpindah pada indeks yang besar sedangkan data dengan nilai kecil akan berpindah pada indeks yang kecil. Proses berpindahnya data yang satu dengan data yang lain dilkukan dengan penukaran. Metode ini sering disebut juga dengan metode exchange (penukaran). Proses pertukaran data pada metode gelembung ini dilakukan mulai data yang pertama. Data yang pertama akan dibandingkan dengan data berikutnya, jika data berikutnya lebih kecil dari data pertama maka dilakukan penukaran. Perbandingan ini dilakukan mulai dari data ke dua sampai dengan data terakhir. Untuk memberikan gambaran yang lebih detil dari algoritma pengurutan data dengan metode gelembung diberikan sebah data yaitu: 10,9,6,8,2,3,1,7 pada fase pertama, data pertama (10) akan dibandingkan dengan data kedua (9), karena data kedua lebih kecil maka data akan ditukar sehingga 9,10,6,8,2,3,1,7. Berikutnya data pertama (9) akan dibandingkan dengan data ketiga (6), karena data ketiga lebih kecil dari data pertama maka dilakukan penukaran sehingga data menjadi 6,10,9,8,2,3,1,7. Selanjutnya data pertama (6) akan dibandingkan dengan data keempat (8) karena data pertama lebih kecil maka tidak dilakukan penukaran dan data masih tetap. Data pertama (6) akan dibandingkan dengan data kelima (2), karena data kelima lebih kecil maka dilakukan penukaran sehingga data menjadi 2,10,9,8,6,3,1,7. Selanjutnya data pertama (2) akan dibandingkan dengan data keenam (3), karena data keenam lebih besar maka tidak dilakukan penukaran. Selanjutnya data pertama (2) akan dibandingkan dengan data ketujuh (1), karena data ketujuh lebih kecil maka dilakukan penukaran sehingga data 2
menjadi 1,10,9,8,6,3,2,7. Akhir dari fase pertama data pertama (1) dibandingkan dengan data terakhir (7), karena data terakhir lebih besar maka tidak dilakukan penukaran. Dari fase yang pertama ini diperoleh sebuah nila terkecil akan menempati pada indeks yang pertama. Pada fase kedua dilakukan perbandingan mulai data kedua terhadap data setelah data kedua sampai data terakhir. Dengan cara yang sama pada fase pertama maka akan diperoleh data terkecil kedua akan menempati indeks kedua. Demikian langkah ini dilakukan sampai pada fase terakhir yaitu n-1. proses penukaran ini akan memperoleh data terurut dari kecil ke besar. Untuk melihat proses lebih detil dapat digambarkan pada penjelasan berikut: Data = 10,9,6,8,2,3,1,7 Tabel 1. Fase pengurutan data dengan metode buble short Fase
Data
Perbandingan
Data Hasil
1
10,9,6,8,2,3,1,7
2
1,10,9,8,6,3,2,7
3
1,2,10,9,8,6,3,7
Ke-1 (10) dengan ke-2 (9) Ke-1 (9) dengan ke-3 (6) Ke-1 (6) dengan ke-4 (8) Ke-1 (6) dengan ke-5 (2) Ke-1 (2) dengan ke-6 (3) Ke-1 (2) dengan ke-7 (1) Ke-1 (1) dengan ke-8 (7) Ke-2 (10) dengan ke-3 (9) Ke-2 (9) dengan ke-4 (8) Ke-2 (8) dengan ke-5 (6) Ke-2 (6) dengan ke-6 (3) Ke-2 (3) dengan ke-7 (2) Ke-2 (2) dengan ke-8 (7) Ke-3 (10) dengan ke-4 (9) Ke-3 (9) dengan ke-5 (8) Ke-3 (8) dengan ke-6 (6) Ke-3 (6) dengan ke-7 (3)
9,10,6,8,2,3,1,7 6,10,9,8,2,3,1,7 6,10,9,8,2,3,1,7 2,10,9,8,6,3,1,7 2,10,9,8,6,3,1,7 1,10,9,8,6,3,2,7 1,10,9,8,6,3,2,7 1,9,10,8,6,3,2,7 1,8,10,9,6,3,2,7 1,6,10,9,8,3,2,7 1,3,10,9,8,6,2,7 1,2,10,9,8,6,3,7 1,2,10,9,8,6,3,7 1,2,9,10,8,6,3,7 1,2,8,10,9,6,3,7 1,2,6,10,9,8,3,7 1,2,3,10,9,8,6,7
Ke-3 (3) dengan ke-8 (7) Ke-4 (10) dengan ke-5 (9) Ke-4 (9) dengan ke-6 (8) Ke-4 (8) dengan ke-7 (6) Ke-4 (6) dengan ke-8 (7) Ke-5 (10) dengan ke-6 (9) Ke-5 (9) dengan ke-7 (8) Ke-5 (8) dengan ke-8 (7)
1,2,3,10,9,8,6,7 1,2,3,9,10,8,6,7 1,2,3,8,10,9,6,7 1,2,3,6,10,9,8,7 1,2,3,6,10,9,8,7 1,2,3,6,9,10,8,7 1,2,3,6,8,10,9,7 1,2,3,6,7,10,9,8
4
1,2,3,10,9,8,6,7
5
1,2,3,6,10,9,8,7
3
Fase
Data
Perbandingan
Data Hasil
6
1,2,3,6,7,10,9,8
7
1,2,3,6,7,8,10,9
Ke-6 (10) dengan ke-7 (9) Ke-6 (9) dengan ke-8 (8) Ke-7 (10) dengan ke 8 (9)
1,2,3,6,7,9,10,8 1,2,3,6,7,8,10,9 1,2,3,6,7,8,9,10
Penjelasan diatas secara detil telah menggambarkan bagaimana langkah-langkah pengurutan data dengan metode gelembung (buble sort). Berikut ini adalah algoritma dan contoh program dari kasus pengurutan data dengan metode gelembung. Algoritma urut_buble. Deklarasi int Data[ ] int tampung, I,j; Deskripsi ulai for i0 to n-1 do for j i+1 to n do
If Data[i] > Data[j] then tampungData[i] Data[i]Data[j] Data[j] tampung Akhir if Akhir for j Akhir for i Selesai Program Pengurutan dengan buble short #include
#include <stdio.h> main() { int Data[10]; int tampung,i,j; for (i=0;i<10;i++) { printf("Inputkan Data angka:");scanf("%d",&Data[i]); } /*mulai pengurutan dengan metode buble sort*/ for (i=0;i<10;i++) { for (j=i+1;j<=10;j++) if (Data[i]>Data[j])//jika Data ke i > data ke j, proses tukar data {tampung=Data[i]; // data ke i disimpan dlm variabel tampung Data[i]=Data[j]; // skrg data ke i diisi dg isi dg data ke j
4
Data[j]=tampung; // skrg data ke j diisi dg data ke i yg disimpan sementara dlm variabel tampung } } /*menampilkan Data yang sudah terurut*/ printf("Data Terurut adalah:"); for (i=0;i<10;i++) printf("\n%d",Data[i]); getch(); }
Hasil output program:
2. Metode Penyisipan (Insertion Sort) Metode penyisipan adalah metode pengurutan data dengan cara menyisipkan data agar menjadi urut. Jika terdapat sebuah larik data yan akan diurutkan ( A1… An), dengan menggunakan metode penyisipan ini data akan disusun pada kelompok yang terurut yaitu dari A1 sampai dengan Ai-1 dengan i dimulai dari 2 dengan pertambahan 1. Penempatan pada kelompok terurut inilah yang menggunakan metode penyisipan. Untuk memberikan ilustrasi yang lebih detil dari metode penyisipan ini diberikan data sebagai berikut: indeks Elemen array A
[0]
[1]
[2]
[3]
[4]
4
3
5
3
2
5
Langkah- langkah urut untuk menyelesaikan pengurutan data diatas adalah: a. Dimulai dari data pada indeks i ke-1 (indeks data kedua) dan indeks j= i. i indeks
j
[0]
[1]
[2]
[3]
[4]
4
3
5
3
2
Lakukan perulangan jika: Kondisi j > 0 AND A[j] < A[j-1] terpenuhi. Karena kondisi terpenui maka lakukan pertukaran data A[j] dan A[j-1] i
j
[0]
[1]
[2]
[3]
[4]
3
4
5
3
2
Lakukan decrement j yaitu j = j -1.
j
i
[0]
[1]
[2]
[3]
[4]
3
4
5
3
2
Setelah decrement j = 0 .karena perulangan syaratnya j > 0 maka perulangan berhenti disini.
b. Indeks i bertambah sehingga menjadi i = 2 , maka j= i , atau j = 2
i
j
[0]
[1]
[2]
[3]
[4]
3
4
5
3
2
Lakukan perulangan jika : 6
kondisi j > 0 AND A[j] < A[j-1] terpenuhi. Karena kondisi tidak terpenuhi maka pertukaran data tidak terjadi. Tidak ada pula decrement j
c. Indeks i bertambah sehingga menjadi i = 3 , maka j= i , atau j = 3
i
j
[0]
[1]
[2]
[3]
[4]
3
4
5
3
2
Lakukan perulangan jika : kondisi j > 0 AND A[j] < A[j-1] terpenuhi?. Karena kondisi terpenuhi maka pertukaran data terjadi yaitu antara data A[j] dg A[j -1] atau A[3] dg A[2]
i [0]
[1]
[2]
[3]
[4]
3
4
3
5
2
decrement j , j = j -1 maka j=3-1 = 2
i
j
j
[0]
[1]
[2]
[3]
[3]
3
4
3
5
2
kondisi j > 0 AND A[j] < A[j-1] terpenuhi?. Karena kondisi terpenuhi maka pertukaran data terjadi yaitu antara data A[j] dg A[j -1] atau A[2] dg A[1] j
i
[0]
[1]
[2]
[3]
[4]
3
3
4
5
2
decrement j , j = j -1 maka j=2-1 = 1 7
j
i
[0]
[1]
[2]
[3]
[4]
3
3
4
5
2
kondisi j > 0 AND A[j] < A[j-1] terpenuhi?. Karena kondisi tidak terpenuhi maka pertukaran data tidak terjadi.
d. Indeks i bertambah sehingga menjadi i = 4 , maka j= i , atau j = 4 j i [0]
[1]
[2]
[3]
[4]
3
3
4
5
2
Lakukan perulangan jika : kondisi j > 0 AND A[j] < A[j-1] terpenuhi?. Karena kondisi terpenuhi maka pertukaran data terjadi yaitu antara data A[j] dg A[j -1] atau A[4] dg A[3]
i [0]
[1]
[2]
[3]
[4]
3
3
4
2
5
j
decrement j , j = j -1 maka j=4-1 = 3 j
i
[0]
[1]
[2]
[3]
[4]
3
3
4
2
5
kondisi j > 0 AND A[j] < A[j-1] terpenuhi?. Karena kondisi terpenuhi maka pertukaran data terjadi yaitu antara data A[j] dg A[j -1] atau A[3] dg A[2]
8
j
i
[0]
[1]
[2]
[3]
[4]
3
3
2
4
5
decrement j , j = j -1 maka j=3-1 = 2
i
j
[0]
[1]
[2]
[3]
[4]
3
3
2
4
5
kondisi j > 0 AND A[j] < A[j-1] terpenuhi?. Karena kondisi terpenuhi maka pertukaran data terjadi yaitu antara A[ j ] dg A[ j -1] atau A[ 2 ] dg A[ 1]
i
j [0]
[1]
[2]
[3]
[4]
3
2
3
4
5
decrement j , j = j -1 maka j=2-1 = 1 j
i
[0]
[1]
[2]
[3]
[4]
3
2
3
4
5
kondisi j > 0 AND A[j] < A[j-1] terpenuhi?. Karena kondisi terpenuhi maka pertukaran data terjadi yaitu antara A[ j ] dg A[ j -1] atau A[ 1 ] dg A[ 0] j
i
[0]
[1]
[2]
[3]
[4]
2
3
3
4
5
9
decrement j , j = j -1 maka j=1-1 = 0 j
i
[0]
[1]
[2]
[3]
[4]
2
3
3
4
5
kondisi j > 0 AND A[j] < A[j-1] terpenuhi?. Karena kondisi tidak terpenuhi maka pertukaran data tidak terjadi. Perulangan berakhir. e. Indeks i bertambah sehingga menjadi i = 5 , maka j= i , atau j = 5. j i [0]
[1]
[2]
[3]
[4]
2
3
3
4
5
Karena indeks elemen hanya sampai i =4 maka loop i berakhir. Algoritma Insertion Sort dalam bentuk pseudecode adalah : Deklarasi: int j, j; int tampung; int A[ ]={4,3,5,3,2}; Deskripsi: Mulai For i=0 to i = n -1 do J=i While (j >0 && A[j]< A[j-1]) , lakukan pertukaran data A[j] dan A[ j-1] tampung A[j]; A[ j ]A[j -1]; A [j -1] tampung; j --; end while end for selesai
10
Program . Pengurutan data dengan metode insertion short #include #include <stdio.h> main( ) { int A[5]; int tampung,i,j; for (i=0;i<5;i++) { printf("Masukkan nilai A:");scanf(" %d",&A[i]); } for (int i = 0; i < 5; i++) { j = i; while (j >0 && A[j]< A[j-1]) { tampung= A[j]; A[j] = A[j-1]; A[j-1] = tampung; j--; } } printf("\nData terurut:"); for( i=0;i<5;i++) { printf(" %d",A[i]); } getch(); }
Output dari Program:
11
