Metode Pengurutan Data

1. Pengurutan Berdasarkan Penyisipan dan Penjagaan Terurut (Insert and Keep Sorted Method) • Insertion Sort Insertion sort adalah sebuah algoritma pengurutan yang membandingkan dua elemen data pertama, mengurutkannya, kemudian mengecek elemen data berikutnya satu persatu dan membandingkannya dengan elemen data yang telah diurutkan. Karena algoritma ini bekerja dengan membandingkan elemen-elemen data yang akan diurutkan, algoritma ini termasuk pula dalam comparison-based sort. Ide dasar dari algoritma Insertion Sort ini adalah mencari tempat yang "tepat" untuk setiap elemen array, dengan cara sequential search. Proses ini kemudian menyisipkan sebuah elemen array yang diproses ke tempatnya ang seharusnya. Proses dilakukan sebanyak N-1 tahapan (dalam sorting disebut sebagai "pass"), dengan indeks dimulai dari 0. Proses pengurutan dengan menggunakan algoritma Insertion Sort dilakukan dengan cara membandingkan data ke-i (dimana i dimulai dari data ke-2 sampai dengan data terakhir) dengan data berikutnya. Jika ditemukan data yang lebih kecil maka data tersebut disisipkan ke depan sesuai dengan posisi yang seharusnya. contoh: #include #include 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 insertion_sort() { int temp,i,j; for(i=1;i<=n;i++) { temp = data[i]; j = i -1; while(data[j]>temp && j>=0) { data[j+1] = data[j]; j--; } data[j+1] = temp; } } void main() { cout<<" PROGRAM INSERTION SORT"<>n; for(int i=1;i<=n;i++) { cout<<"Masukkan data ke "<>data[i]; data2[i]=data[i]; } insertion_sort(); cout<<"Data Setelah di Sort : "; for(i=1; i<=n; i++) { cout<<" "<item = itembaru; //baru di tunjuk oleh pointer item & di isi dengan item baru baru->kiri = NULL; //baru ditunjuk dengan pointer kiri ,dan jika masihh kosong baru->kanan = NULL; //baru ditunjuk dengan pointer kanan & jika kosong (*akar) = baru; //pointer akar = variabel baru dengan alamat baru (*akar)->kiri = NULL; (*akar)->kanan = NULL; cout<<"Item bertambah!"; } else if(itembaru < (*akar)->item) tambah(&(*akar)->kiri,itembaru); // jika item yang ditambah di kiri else if(itembaru > (*akar)->item) tambah(&(*akar)->kanan,itembaru); //jika item yang ditambah item ke kanan else if(itembaru == (*akar)->item) //jika item yang di input sama dengan item yang ditambah sebelumnya cout<<"Item sudah ada!"; } void tampil(Node *akar) //fungsi menampilkan seluruh item yang telah di imput { if(akar != NULL){ cout<item<<" "; tampil(akar->kiri), //rekursif dengan fungsi tampil dengan mengarah ke kanan tampil(akar->kanan); //rekursif dengan fungsi tampil dengan mengarah ke kanan }} void preOrder(Node *akar) //fungsi cetak preOrder { if(akar != NULL){ cout<< akar->item<<" "; //cetak item akar preOrder(akar->kiri), //cetak di subtree kiri preOrder(akar->kanan); //cetak di subtree kanan }} void inOrder(Node *akar) //fungsi cetak inOrder { if(akar != NULL){ inOrder(akar->kiri), //cetak di subtree kiri cout<< akar->item<<" "; //cetak item akar inOrder(akar->kanan); //cetak di subtree kanan }} void postOrder(Node *akar) //fungsi cetak postOrder { if(akar != NULL){ postOrder(akar->kiri), //cetak di subtree kiri postOrder(akar->kanan); //cetak di subtree kanan cout<< akar->item<<" "; //cetak item akar }} main() { int item; Node *phn; //pointer phn untuk menghubungkan dengan link Node phn = NULL; //alamat pointer phn pada NULL char pil; do { system("cls"); cout<<"\tTREE SORT\n"; cout<<"1. Tambah\n"; cout<<"2. Pre-order\n"; cout<<"3. In-order\n"; cout<<"4. Post-order\n"; cout<<"5. Keluar\n"; cout<<"Silahkan masukkan pilihan anda (1-5)... "; pil=getche(); if(pil=='1') { cout<<"\n"; cout<<"\nItem baru : ";cin>>item; tambah(&phn,item); //fungsi tambah dengan menggunakan alamat pointer phn dengan variabel } if(pil=='2') { if(phn!=NULL) { //jika phn tidak kosong cout<< "\n-->Item yang masuk : ";tampil (phn); //cetak item yang masuk cout<<"\n-->preOrde : ";preOrder(phn); //cetak preOrder } else cout<<"\n-->Masih kosong!"; getch(); } if(pil=='3') { if(phn!=NULL) { cout<< "\n-->Item yang masuk : ";tampil(phn); //cetak item yang masuk cout<<"\n-->inOrder : ";inOrder (phn); //cetak item inOrder } else cout<<"\n-->Masih kosong!"; getch(); } if(pil=='4') { if(phn!=NULL) { cout<< "\n-->Item yang masuk : ";tampil (phn); //cetak item yang masuk cout<<"\n-->postOrder : ";postOrder(phn); //cetak item postOrder } else cout<<"\n-->Masih kosong!"; getch(); } } while(pil!='5'); cout<<"\n"; } 2. Pengurutan Berdasarkan Perbandingan (Comparison Based Sorting) • Bubble Short Bubble sort adalah proses pengurutan sederhana yang bekerja dengan cara berulang kali membandingkan dua elemen data pada suatu saat dan menukar elemen data yang urutannya salah. Ide dari Bubble sort adalah gelembung air yang akan "mengapung" untuk table yang terurut menaik (ascending). Elemen bernilai kecil akan "diapungkan" (ke indeks terkecil), artinya diangkat ke "atas" (indeks terkecil) melalui pertukaran. Karena algoritma ini melakukan pengurutan dengan cara membandingkan elemenelemen data satu sama lain, maka bubble sort termasuk ke dalam jenis algoritma comparison-based sorting. Proses dalam Bubble sort dilakukan sebanyak N-1 langkah (pass) dengan N adalah ukuran array. Pada akhir setiap langkah ke – I , array L[0..N] akan terdiri atas dua bagian, yaitu bagian yang sudah terurut L[0..I] dan bagian yang belum terurut L[I+1..N-1]. Setelah langkah terakhir, diperoleh array L[0..N-1] yang terurut menaik. contoh: #include #include void main () { int nilai[8]; int temp; cout<<"Data sebelum diurutkan"<>nilai[ctr]; } cout<nilai[ii+1]) { temp=nilai[ii]; nilai[ii]=nilai[ii+1]; nilai[ii+1]=temp; } } } cout<<"Data setelah diurutkan"<#include void v_SelAsc(int A[],int N); void v_Tukar(int *P,int *M); main() { int L[5]; int i,N; //input data array printf(“Banyak Data: “);scanf(“%i”,&N); for(i=0;i=0;k–) { maks=0; for(j=0;j<=k;j++) { if (A[j] > A[maks]) { maks=j; } //endif } //end loop j v_Tukar(&A[k],&A[maks]); } //end loop k } //end procedure v_SelAsc void v_Tukar(int *P,int *M) { int temp; temp = *P; *P = *M; *M = temp; } //end procedure v_Tukar • Heap Sort Heap Sort mengurutkan dengan memanfaatkan sifat yang dimiliki oleh struktur data heap. Heap adalah suatu strutur data berbentuk pohon biner (binary tree) dimana root dari tree tersebut adalah nilai tertinggi, dan nilai dari parent selalu lebih tinggi dari nilai child.. Ketika suatu array dengan urutan acak ingin dibuat bentuk heapnya, maka diperlukan fungsi untuk pembentukan heapify pada setiap elemen non leaf. Contoh : #include //Fungsi Tukar void tukar(int &a, int &b) { int temp; temp=a; a=b; b=temp; } //Fungsi Heapify void heapify(int val[], int l, int r) { int temp, idx; temp = val[r]; idx = r * 2 + 1; if ((idx < l) && (val[idx] < val[idx+1])) //Note 1 idx++; while ((idx <= l) && (val[idx] > temp)) //Note 2 { val[r] = val[idx]; r = idx; idx = idx * 2 + 1; if ((idx < l) && (val[idx] < val[idx+1])) //Note 3 idx++; } val[r] = temp; } //Fungsi Heap Sort void heapsort(int val[], int n) { for (int x = n/2 - 1; x >= 0; x--) { heapify(val, n - 1, x); } for (int y = n - 1; y > 0; y--) { tukar(val[0], val[y]); heapify(val, y - 1, 0); } } void main() { //Deklarasi variabel int nilai[100]; int z, n; //Input cout<<"Jumlah Data : "; cin>>n; cout<<"--------------------------------\n"; for(z = 0; z < n; z++) { cout<<"Nilai ke-"<<1+z<<" : "; cin>>nilai[z]; } //Memanggil fungsi Heap Sort heapsort(nilai, n); //Mencetak data setelah diurutkan cout<<"--------------------------------\n"; cout<<" HEAP SORT \n"; cout<<"--------------------------------\n"; for(z=0; z" Note 2 = Pengurutan secara ascending menggunakan tanda ">", sedangkan pengurutan secara descending menggunakan tanda "<" Note 3 = Pengurutan secara ascending menggunakan tanda "<", sedangkan pengurutan secara descending menggunakan tanda ">" 4. Pengurutan Berdasarkan Pembagian dan Penguasaan (Devide and Conquer Method) • Quick Short Ide dasar quick sort (pengurutan cepat) yaitu membandingkan hasil setiap perbandingan sebagai penunjuk ke perbandinga berikutnya. Selama perbandingan, kunci dipertukarkan setelah dilengkapi, daftar kemudian dibagi menjadi nilai kunci pada satu partisi (tidak terurut) semuanya kurang dari nilai kunci yang dipilih dan nilai kunci di partisi yang lain semuanya lebih besar dari nilai kunci. Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan (meja pertama), dan yang telah diurutkan (meja kedua). Elemen pertama yang diambil dari bagian array yang belum diurutkan dan kemudian diletakkan pada posisinya sesuai dengan bagian lain dari array yang telah diurutkan. langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang tersisa pada bagian array yang belum diurutkan. void QuickSort(int L, int R) { int i, j; int mid; i = L; j = R; mid = data[(L+R) / 2]; do { while (data[i] < mid) i++; while (data[j] > mid) j–; if (i <= j) { tukar(i,j); i++; j–; }; } while (i < j); if (L < j) QuickSort(L, j); if (i < R) QuickSort(i, R); } void Input() { cout<<“Masukkan jumlah data = “; cin>>n; for(int i=0;i>data[i]; data2[i] = data[i]; } } void Tampil() { cout<<“Data : “< using namespace std; void merge(int low, int mid, int up); void mergeSort(int low, int up); int a[50]; int main() { int jumlahBil,i; cout<<"Masukkan Jumlah element Array"<< endl; cin>>jumlahBil; for(int i=0; i>a[i]; } mergeSort(1,jumlahBil); for(i=1;i<=jumlahBil;i++) cout<mid) { for(k=j;k<=up;k++){ b[i]=a[k]; i++; } } else { for(k=h;k<=mid;k++) { b[i]=a[k]; i++; } } for(k=low;k<=up;k++) a[k]=b[k]; } void mergeSort(int low, int up) { int mid; if(low Sumber: ttp://www.dcc-dp.org/berita404-sort-atau-pengurutan-data--di-c--.html http://puguhjayadi.blogspot.com/2013/05/tree-sort-c.html http://allaboutalgoritma.blogspot.com/2009/06/metode-pemograman-algoritma-exchange.html https://thenurulazizah.wordpress.com/artikel-2/13-metode-sorting/ http://zhuelrainz.blogspot.com/2013/05/heap-sort-c_26.html https://cicink.wordpress.com/2009/06/15/program-sort-komplit-c/ https://7seasons.wordpress.com/tag/merge-sort-c/ http://www.zonaprogram.info/2013/05/contoh-program-mengurutkan-data-dengan.html