Sorting
•
Pengurutan data dalam struktur data sangat penting untuk
data yang beripe data numerik ataupun karakter.
•
Pengurutan dapat dilakukan secara ascending (urut naik)
dan descending (urut turun)
•
Pengurutan (Sorting) adalah proses menyusun kembali data
yang sebelumnya telah disusun dengan suatu pola tertentu, sehingga tersusun
secara teratur menurut aturan tertentu.
Contoh:
•
Data Acak : 5
6 8 1 3 25 10
•
Ascending : 1
3 5 6 8 10 25
•
Descending : 25
10 8 6 5 3 1
Metode
Pengurutan Data
•
Pengurutan berdasarkan perbandingan (comparison-based
sorting)
•
Bubble sort, exchange sort
•
Pengurutan berdasarkan prioritas (priority queue
sorting method)
•
Selection sort, heap sort (menggunakan tree)
•
Pengurutan berdasarkan penyisipan dan penjagaan
terurut (insert and keep sorted method)
•
Insertion sort, tree sort
•
Pengurutan berdasarkan pembagian dan penguasaan (devide
and conquer method)
•
Quick sort, merge sort
•
Pengurutan berkurang menurun (diminishing increment
sort method)
•
Shell sort (pengembangan insertion)
Deklarasi
Array
•
Deklarasikan:
int data[100];
int n; //untuk jumlah data
•
Fungsi untuk Tukar 2 Buah
Data (by reference):
•
void tukar(int *a,int
*b){
•
int
t=*a;
•
*a=*b;
•
*b=t;
}
Bubble Sort
•
Metode sorting termudah
•
Diberi nama “Bubble” karena proses pengurutan secara
berangsur-angsur bergerak/berpindah ke posisinya yang tepat, seperti gelembung
yang keluar dari sebuah gelas bersoda.
•
Bubble Sort mengurutkan data dengan cara membandingkan
elemen sekarang dengan elemen berikutnya.
•
Bubble Sort (2)
•
Pengurutan Ascending :Jika elemen sekarang lebih besar dari elemen berikutnya
maka kedua elemen tersebut ditukar.
•
Pengurutan Descending: Jika elemen sekarang lebih kecil dari elemen berikutnya,
maka kedua elemen tersebut ditukar.
•
Algoritma ini seolah-olah menggeser satu per satu
elemen dari kanan ke kiri atau kiri ke kanan, tergantung jenis pengurutannya,
asc atau desc.
•
Ketika satu proses telah selesai, maka bubble sort
akan mengulangi proses, demikian seterusnya sampai dengan iterasi sebanyak n-1.
Kapan berhentinya? Bubble sort berhenti jika
seluruh array telah diperiksa dan tidak ada pertukaran lagi yang bisa
dilakukan, serta tercapai perurutan yang telah diinginkan
Bubble Sort
(6)
•
Dengan prosedur diatas, data terurut naik (ascending), untuk
urut turun (descending) silahkan ubah bagian:
if (data[j]<data[j-1])
tukar(&data[j],&data[j-1]);
Menjadi:
if (data[j]>data[j-1])
tukar(&data[j],&data[j-1]);
•
“The bubble sort is an easy algorithm to program, but
it is slower than many other sorts”
Exchange Sort
•
Sangat mirip dengan Bubble Sort
•
Banyak yang mengatakan Bubble Sort sama dengan
Exchange Sort
•
Pebedaan : dalam hal bagaimana membandingkan antar
elemen-elemennya.
•
Exchange sort membandingkan suatu elemen dengan
elemen-elemen lainnya dalam
array tersebut, dan melakukan pertukaran elemen jika perlu. Jadi ada elemen yang selalu menjadi elemen pusat (pivot).
•
Sedangkan Bubble sort akan membandingkan elemen pertama/terakhir dengan elemen sebelumnya/sesudahnya, kemudian
elemen tersebut itu akan menjadi pusat
(pivot) untuk dibandingkan dengan elemen sebelumnya/sesudahnya lagi,
begitu seterusnya.
Selection Sort
•
Merupakan kombinasi antara sorting dan searching
•
Untuk setiap proses, akan dicari elemen-elemen yang
belum diurutkan yang memiliki nilai terkecil atau terbesar akan dipertukarkan
ke posisi yang tepat di dalam array.
•
Misalnya untuk putaran pertama, akan dicari data
dengan nilai terkecil dan data ini akan ditempatkan di indeks terkecil
(data[0]), pada putaran kedua akan dicari data kedua terkecil, dan akan
ditempatkan di indeks kedua (data[1]).
•
Selama proses, pembandingan dan pengubahan hanya dilakukan pada indeks pembanding saja, pertukaran
data secara fisik terjadi pada akhir
proses.
Insertion Sort
•
Mirip dengan cara orang mengurutkan kartu, selembar demi selembar kartu diambil dan disisipkan (insert) ke tempat yang
seharusnya.
•
Pengurutan dimulai dari data ke-2 sampai dengan data
terakhir, jika ditemukan data yang lebih
kecil, maka akan ditempatkan (diinsert)
diposisi yang seharusnya.
•
Pada penyisipan elemen, maka elemen-elemen lain akan
bergeser ke belakang
•
Perbandingan
•
Tabel Perbandingan Kecepatan Metode Pengurutan Data
•
Untuk data sejumlah 10.000 data pada komputer Pentium
II 450 MHz
Tidak ada komentar:
Posting Komentar