Transcription
Pertemuan 6:INF202: Struktur DataPengurutan (Sorting)Dosen: Wayan Suparta, PhD
Sorting Pengurutan data dalam struktur data sangat pentinguntuk data yang beripe data numerik ataupunkarakter. Pengurutan dapat dilakukan secara ascending (urutnaik) dan descending (urut turun) Pengurutan (Sorting) adalah proses menyusunkembali data yang sebelumnya telah disusun dengansuatu pola tertentu, sehingga tersusun secara teraturmenurut 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 (comparisoncomparison--basedsorting))sorting– Bubble sort, exchange sort Pengurutan berdasarkan prioritas (prioritypriority queue sortingmethod))method– Selection sort, heap sort (menggunakan tree) Pengurutan berdasarkan penyisipan dan penjagaan terurut(insertinsert and keep sorted method)method– Insertion sort, tree sort Pengurutan berdasarkan pembagian dan penguasaan (devidedevideand conquer method)method– Quick sort, merge sort Pengurutan berkurang menurun (diminishingdiminishing increment sortmethod)method– Shell sort (pengembangan insertion)
Algoritma pengurutan (sorting) : Bubble sort (gelembung)Selection sort (maksimum/minimun)Insertion sort (sisip)Heap sortShell sortQuick sortMerge sortRadix sortTree sort
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;}
1a. Bubble Sort Diberi nama “Bubble” karenaproses pengurutan secaraberangsur-angsurbergerak/berpindah ke posisinyayang tepat, seperti gelembungyang keluar dari sebuah gelasbersoda. Bubble Sort mengurutkan datadengan cara membandingkanelemen sekarang dengan elemenberikutnya.
Bubble Sort (2) Pengurutan Ascending :Jika elemen sekarang lebih besar darielemen berikutnya maka kedua elemen tersebut ditukar. Pengurutan Descending: Jika elemen sekarang lebih kecil darielemen berikutnya, maka kedua elemen tersebut ditukar. Algoritma ini seolah-olah menggeser satu per satu elemen darikanan ke kiri atau kiri ke kanan, tergantung jenis pengurutannya,asc atau desc. Ketika satu proses telah selesai, maka bubble sort akan mengulangiproses, demikian seterusnya sampai dengan iterasi sebanyak n-1. Kapan berhentinya? Bubble sort berhenti jika seluruh array telahdiperiksa dan tidak ada pertukaran lagi yang bisa dilakukan, sertatercapai perurutan yang telah diinginkan.
Bubble Sort (3)Terjadi penukaran bilaangka di depannya lebihbesar
Bubble Sort (4)
Bubble Sort (5)
Bubble Sort (6) Versi 1: Naik Versi 2: Turun
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]); Teknik bubble sort mudah difahami, namunpelaksanaannya adalah lambat.
1b. Exchange Sort Sangat mirip dengan Bubble Sort Banyak yang mengatakan Bubble Sort sama dengan ExchangeSort Perbedaan : dalam hal bagaimana membandingkan antarelemen-elemennya.– Exchange sort membandingkan suatu elemen denganelemen-elemen lainnya dalam array tersebut, danmelakukan pertukaran elemen jika perlu. Jadi ada elemenyang selalu menjadi elemen pusat (pivot).– Sedangkan Bubble sort akan membandingkan elemenpertama/terakhir dengan elemensebelumnya/sesudahnya, kemudian elemen tersebut ituakan menjadi pusat (pivot) untuk dibandingkan denganelemen sebelumnya/sesudahnya lagi, begitu seterusnya.
Contoh program bubble sort:#include iostream using namespace std;int data[10], data2[10]; int n;void tukar(int a, int b){int t; t data[b]; data[b] data[a];data[a] t; }void bubble sort(){for(int i 1; i n; i ) {for(int j n; j i; j--) {if(data[j] data[j-1]){tukar(j, j-1);}}}}main(){cout "Masukkan jumlah data: ";cin n;cout endl;for(int i 1; i n; i ) {cout "Masukkan data ke-" i ": ";cin data[i];data2[i] data[i]; }bubble sort();cout "\nData Setelah diurutkan" endl;cout "------------------------" endl;for(int i 1; i n; i ){cout data[i] " ";}cout endl;system("pause");}
2. Selection Sort Merupakan kombinasi antara sorting dansearching Untuk setiap proses, akan dicari elemen-elemenyang belum diurutkan yang memiliki nilaiterkecil atau terbesar akan dipertukarkan keposisi yang tepat di dalam array. Misalnya untuk putaran pertama, akan dicari datadengan nilai terkecil dan data ini akanditempatkan di indeks terkecil (data[0]), padaputaran kedua akan dicari data kedua terkecil,dan akan ditempatkan di indeks kedua (data[1]). Selama proses, pembandingan dan pengubahanhanya dilakukan pada indeks pembanding saja,pertukaran data secara fisik terjadi pada akhirproses.
Selection Sort (2)
Selection Sort (3) Prosedur Selection Sort
Program selection sort:#include iostream #include conio.h #include stdio.h #include iomanip using namespace std;int main() {int x[5]; int i; int temp; int minindex;int j;cout " Welcome To The ProgramSelection Sort \n" endl;cout "masukkan nilai x :\n";for(i 0; i 5; i ){ cout "x[" i "] ";cin x[i]; }cout "\n data sebelum di sort :";for(i 0; i 5;i ){ cout setw(4) x[i]; }for(i 0; i 5-1; i ) //perulangan iterasi{minindex i;for(j i 1; j 5; j ) //perulanganmembandingkan data{if(x[minindex] x[j]){minindex j;}}temp x[i];x[i] x[minindex];x[minindex] temp;}cout "\n\nData setelah di sort :";for(i 0; i 5; i ){cout setw(4) x[i];}getch();}
3. 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 dengandata terakhir, jika ditemukan data yang lebih kecil,maka akan ditempatkan (diinsert) diposisi yangseharusnya. Pada penyisipan elemen, maka elemen-elemen lainakan bergeser ke belakang
Flowchart
Algoritma Insertion Sort (1)Terdapat 5 elemen data:1).
Algoritma lanjutan2).3).4).
Insertion Sort (2)
Insertion Sort (3)
ContohData awal: [5, 2, 4, 6, 1, 3]. Jumlah index adalah 6, dimulai dari0 sampai 5. Anggaplah index adalah “I”, dimana untuk setiapproses pengurutan, perbandingan data akan dimulai dari indexkedua (dalam hal ini i 1). Perhatikan algoritmanya.Proses I:i 1, x 1; j 0x j à2 5? — true 2, 5, 4, 6, 1, 3Proses IIi 2, j 1, x 2x j à 4 5 — true 2, 4, 5, 6, 1, 3; j j-1. Artinya jika proses benar,maka “x x-1”x j à4 2 — false 2, 4, 5, 6, 1, 3Proses IIII 3, j 2, x 3x j à6 5 — false 2, 4, 5, 6, 1, 3; j j-1. Artinya jika sebuah prosesbernilai false, maka proses tersebut tidak akan dilanjutkan, karena semuadata yang ada di sebelah kiri sudah terurut dengan benar secara otomatis.
Contoh sambungan .Proses IV:i 4, j 3, x 4x j à1 6 — true 2, 4, 5, 1, 6, 3; j j-1, jika benar maka x x-1x j à 1 5 — true 2, 4, 1, 5,6, 3; j j-1, jika benar maka x x-1x j à1 4 — true 2, 1, 4, 5,6, 3; j j-1, jika benar maka x x-1x j à 1 2 — true 1, 2, 4, 5,6, 3Proses V:i 5, j 4, x 5x j à3 6 — true 1, 2, 4, 5,3, 6x j à3 5 — true 1, 2, 4, 3, 5, 6x j à3 4 — true 1, 2, 3, 4, 5, 6x jà3 2 — false 1, 2, 3, 4, 5, 6j j-1, jika benar maka x x-1j j-1, jika benar maka x x-1j j-1, jika benar maka x x-1j j-1
Programnya:#include iostream #include conio.h int main(){int data[] {5, 2, 4, 6, 1, 3};cout “sebelum disorting: “;for(int i 0; i 6; i )cout data[i] “, “;cout endl endl;for(int i 1; i 6; i ){int j i;while(data[j] data[j-1])Output:{int tmp data[j];data[j] data[j-1];data[j-1] tmp;j–;}}cout “Setelah disorting: “;for(int i 0; i 6; i )cout data[i] “, “;getch();}
LATIHAN 131.Buat program sorting “insertion sort” dengan output:2.Buat algoritma mengurutkan data berikut “8 17 20 11 5”, mengurutkanarray dari angka terendah ke nomor terbesar menggunakan bubble sort.Dalam setiap langkah, unsur-unsur yang ditulis dalam huruf tebalsedang dibandingkan.Buat program pengurutan secara ascending dan descending denganselection sort.3.
–Bubble sort, exchange sort Pengurutan berdasarkan prioritas (priority queue sorting method) . Flowchart . Algoritma Insertion Sort (1) Terdapat 5 elemen data: 1). Algoritma lanjutan 2). 3). 4). Insertion Sort (2) Insertion Sort (3) Contoh Data awal: [5, 2, 4, 6, 1, 3]. Jumlah index adalah 6, dimulai dari 0 sampai 5. Anggaplah index adalah “I”, dimana untuk setiap proses pengurutan .
