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 (3)

•          Bubble Sort (4)

•          Bubble Sort (5)

•          Bubble Sort (6)

•          Versi 1

               

•          Versi 2

                 

•          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.

•          Exchange Sort (2)

•          Exchange Sort (3)

•          Exchange Sort (4)

•          Exchange Sort (5)

•          Prosedur Exchange Sort

                 

•          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.

•          Selection Sort (2)

•         
Selection Sort (3)

•          Prosedur Selection Sort

                 

•          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

•          Insertion Sort (2)

•          Insertion Sort (3)

•          Perbandingan

•          Tabel Perbandingan Kecepatan Metode Pengurutan Data

•          Untuk data sejumlah 10.000 data pada komputer Pentium II 450 MHz