DitoX_BloG: sorting

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