Sorting Algorithm

Sorting adalah proses pengurutan suatu barisan secara ascending (a-z) atau descending (z-a). Algorithma adalah cara untuk menyelesaikan suatu masalah. Dalam tulisan ini akan saya bahas 3 algoritma pengurutan yaitu Buble Sort, Insertion sort, dan Selection sort.

Problems:
Diberikan barisan bilangan finite: 91, 76, 33, 12, 3, 77, 78, 81, 9, 0, 11
Urutkan barisan tersebut secara ascending!

Definition:
0. Elemen barisan adalah bilangan bulat/integer.
1. State awal adalah barisan paling awal. Contoh: 91.
2. Jumlah state/kondisi ada n! Contoh: 11! Namun ini tidak efisien.
3. Goal state terdefinisikan sebagai barisan yang terurut secara ascending. Contoh: 0, 3, 9, 11, 12, 33, 76, 77, 78, 81, 91.

Solution:
1. Buble Sort

• Proses sorting dimulai dari bilangan pertama (n), jika bilangan selanjutnya (n+1) lebih kecil maka swap dilakukan 1 kali. Begitu pula untuk bilangan lainnya, proses dilakukan sampai pernyataan n+1 < n tidak berlaku.
• Penerapan algoritma ini dalam c++:

#include<iostream> #include<conio.h> #include<stdlib.h> #include<time.h> using namespace std; main(){ srand(time(NULL)); int arr[100]; int j=0,tmp; bool sorting=true; //entering random data for(int i=0; i<20; i++) {arr[i]=rand()%100+1; cout<<arr[i]<<" ";} cout<<endl<<endl; //sorting process while(sorting){ sorting=false; j++; for(int i=0; i<20-j; i++){ if(arr[i]>arr[i+1]){ tmp=arr[i]; arr[i]=arr[i+1]; arr[i+1]=tmp; sorting=true; } } } for(int i=0; i<20; i++) cout<<arr[i]<<" "; getch(); }

2. Insertion Sort

• Proses sorting dilakukan pertamakali di state 2. Idenya: Akan dilakukan perbandingan, jika bilangan di kiri lebih besar, lakukan swap. Begitu seterusnya sampai bilangan n tidak lebih kecil dari n-1. Untuk worst case, proses membandingkan ini dilakukan sampa n-1 kali. jadi misalnya Head ada di bilangan ke 4, proses membandingkan dilakukan sebanyak 3 kali: bil. ke 4 dengan bil. ke 3, dengan bil. ke 2, ... sampai n=1.
• Penerapan algoritma ini dalam c++:

//sorting insertion #include<iostream> #include<conio.h> using namespace std; main(){ int aray[100],n,tmp; //input cout<<"n= "; cin>>n; for(int i=0; i<n; i++){ cin>>aray[i]; } //sorting for(int i=1; i<n; i++){ int j=i; while(j>0){ if(aray[j]<aray[j-1]){ tmp=aray[j-1]; aray[j-1]=aray[j]; aray[j]=tmp; } j--; } } for(int i=0;i<n;i++) cout<<aray[i]<<" "; getch(); }
3. Selection Sort

• Metode ini sederhana saja. Dilakukan proses sebanyak n buah data/bilangan sampai diperoleh bilangan paling kecil. Setelah berhasil ditemukan, bilangan terkecil tersebut di swap dengan bilangan pertama (atau bilangan ke n=0, untuk akhir proses, n++). Begitu seterusnya sehingga untuk langkah/proses berikutnya dilakukan sebanyak n-1 (berkurang satu langkah).
• Penerapan algoritma ini dalam c++:

#include <iostream> #include <conio.h> using namespace std; main(){ int aray[100], n, minim, posofi; cout<<"jumlah data(n)= ";cin>>n; if(n==0) return 0; cout<<"Masukkan data= "<<endl; //input for(int i=0; i<n; i++){ cout<<i+1<<". "; cin>>aray[i]; } cout<<endl<<endl<<"Data Sorted (asc)\n\a"; minim=aray[0]; //proses sorting for(int i=0; i<n; i++){ for(int j=i+1; j<n; j++){ if(aray[j]<minim){ minim=aray[j]; //posofi=j; BUGS } } //aray[posofi]=aray[i]; BUGS //aray[i]=minim; BUGS for(int k=i; k<n; k++) { if(aray[k]==minim) {aray[k]=aray[i];aray[i]=minim;} } cout<<i+1<<". "<<aray[i]<<endl; minim=aray[i+1]; } getch(); }  

Selesai. 

for more: www.algolist.net/Algorithms

Notes: Catatan ini adalah catatan belajar. Jadi tidak mutlak (100%) tepat, dan program c++ juga adalah hasil latian saya. Sharing dan semoga bermanfaat.