Sorting
Sorting yaitu pengurutan data-data baik dari data yang terkecil ke terbesar, maupun sebaliknya. Proses Pengurutan banyak ditemukan dalam komputer. Hal ini karena data yang sudah urut akan lebih cepat untuk dicari. Untuk membentuk data yang tidak urut menjadi data yang urut, terdapat berbagai metode dan algoritma yang bisa digunakan. Biasanya Sorting data ini digunakan dalam array 1 dimensi.
Metode Sorting :
- Bubble Sort
- Selection Sort
- Insertion Sort
Bubble Sort
Metode/algoritma pengurutan dengan dengan cara melakukan penukaran data dengan tepat disebelah
nya secara terus menerus sampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan. Jika tidak ada perubahan berarti data sudah terurut. Disebut pengurutan gelembung karena masing-masing kunci akan dengan lambat menggelembung ke posisinya yang tepat. Metode pengurutan gelembung (Bubble Sort) diinspirasikan oleh gelembung sabun yang berada dipermukaan air. Karena berat jenis gelembung sabun lebih ringan daripada berat jenis air, maka gelembung sabun selalu terapung ke atas permukaan. Prinsip di atas dipakai pada pengurutan gelembung. Ide dari algoritma ini adalah mengulang proses pembandingan antara tiap-tiap elemen array dan menukarnya apabila urutannya salah. Pembandingan elemen-elemen ini akan terus diulang hingga tidak perlu dilakukan penukaran lagi.
Selection Sort
Selection Sort merupakan metode pengurutan yang menyeleksi satu per satu data yang ada dalam array 1 dimensi. Penyeleksian ini dilakukan dengan cara membandingkan satu data dengan satu data yang lain dalam sebuah array 1 dimensi.
Metode Selection Sort secara ascending (data terkecil ke data terbesar/data terurut naik) :
Mencari data terkecil dari data pertama sampai dengan data yang terakhir, kemudian jika ditemukan data yang lebih kecil dari data yang pertama maka posisinya akan ditukar.
Mencari data terkecil dari data kedua sampai dengan data yang terakhir, kemudian jika ditemukan data yang lebih kecil dari data yang kedua maka posisinya akan ditukar.
Mencari data terkecil dari data ketiga sampai dengan data yang terakhir, kemudian jika ditemukan data yang lebih kecil dari data yang ketiga maka posisinya akan ditukar.
Begitu seterusnya sampai semua data terurut naik. Bila terdapat n buah data yang akan diurutkan maka membutuhkan n-1 langkah pengurutan, dengan data terakhir, yaitu data ke n tidak perlu diurutkan karena menjadi satu-satunya data.
Insertion Sort
Pengurutan dengan Metode Insertion Sort yaitu dengan penyisipan adalah suatu metode yang melakukan pengurutan dengan cara menyisipkan data yang belum urut ke dalam bagian data yang telah terurut secara relatif, penyisipan dilakukan ke bagian sisi kiri. Penyisipan yang dilakukan ini menimbulkan pergeseran data ke bagian kanan array.
Proses
1. Dimulai dengan posisi tangan kosong, dan semua kartu berada diatas meja. Dan anggaplah kita akan menyusun kartu ke tangan kiri kita.
2. Mengamil kartu pertama dari meja dan meletakannya ke tangan kiri.
3. Mengambil kartu kedua dan membandingkannya dengan kartu yang sudah ada di tangan kiri.
4. Jika kartu yang diambil dari meja memenuhi syarat perbandingan, maka kartu tersebut akan diletakan didepan kartu yang dibandingkan, serta kartu yang lain yang telah dibandingkan akan bergeser mundur (ke belakang). Proses ini akan berlangsung sampai semua kartu akan terurutkan dengan benar sesuai criteria pengurutannya.
2. Mengamil kartu pertama dari meja dan meletakannya ke tangan kiri.
3. Mengambil kartu kedua dan membandingkannya dengan kartu yang sudah ada di tangan kiri.
4. Jika kartu yang diambil dari meja memenuhi syarat perbandingan, maka kartu tersebut akan diletakan didepan kartu yang dibandingkan, serta kartu yang lain yang telah dibandingkan akan bergeser mundur (ke belakang). Proses ini akan berlangsung sampai semua kartu akan terurutkan dengan benar sesuai criteria pengurutannya.
Source Code & Program - Contoh Kasus
Sourcode Program :
#include <iostream> //file header input output stream
using namespace std; //menggunakan namespace std
int data[100]; //deklarasi variabel data dengan tipe data interger
int n; //dekla//menampilkan data hasil selection sort
rasi variable n dengan tipe data interger
void bubble_sort(){ //deklarasi dan fungsi void bubble_sort
int tahap,j,tmp;
for(tahap=1;tahap<n;tahap++){ //algoritma program bubble sort
for(j=0;j<n-tahap;j++){
if(data[j]>data[j+1]){
tmp = data[j];
data[j]=data[j+1];
data[j+1]=tmp;
}
}
cout<<"hasil tahap "<<tahap<<" : "; //menampilkan hasil sorting
for(int i=0;i<n;i++){
cout<<data[i]<<" ";
}
cout<<"\n";
}
}
void tukar(int y,int z){ //deklarasi dan fungsi void tukar untuk menukar
int s; //deklarasi variable s
s = data[z]; //algoritma program penukaran
data[z]=data[y];
data[y]=s;
}
void selection_sort(){ //deklarasi dan fungsi void selection_sort
int compare,i,j;
for(i=0;i<n-1;i++){ //algoritma program selection sort
compare = i;
for(j=i+1;j<n;j++){
if(data[j]<data[compare]){
compare = j;
}
}
if(compare!=1){
tukar(compare,i);
}
}cout<<"selection sort selesai !"<<endl;//menampilkan data hasil selection sort
cout<<"data : ";
for(int i=0;i<n;i++){
cout<<data[i]<<" ";
}
cout<<endl;
}
void insertion_sort(){ //deklarasi dan fungsi void insertion sort
int temp,i,j;
for(i=1;i<n;i++){ //algoritma program sorting untuk insertion sort
temp = data[i];
j = i - 1;
while(data[j]>temp && j>=0){
data[j+1] = data[j];
j=j-1;
}
data[j+1] = temp;
}
cout<<"insetion sort selesai!"<<endl;//menampilkan data hasil insertion sort
cout<<"Data : "<<endl;
for(int i=0;i<n;i++){
cout<<data[i]<<" ";
}
cout<<endl;
}
void input(){
cout<<"masukan jumlah data =";
cin>>n;
for(int i=0;i<n;i++){
cout<<"Masukan data ke - "<<(i+1)<<" = ";
cin>>data[i];
}
}
int main(void){ //fungsi utama program yang akan dieksekusi
int pil;
do{
cout<<"--Sorting--------------------"<<endl;//menu yang ditampilkan untuk pilihan sortting dan input data
cout<<"1. Input data"<<endl;
cout<<"2. Bubble Sort"<<endl;
cout<<"3. Selection Sort"<<endl;
cout<<"4. Insertion Sort"<<endl;
cout<<"5. Exit"<<endl;
cout<<"Masukan Pilihan anda = ";
cin>>pil;
cout<<"----------------------------"<<endl;
switch(pil)
{
case 1: input();break; //pemanggilan tiap fungsi
case 2: bubble_sort();break; //pemanggilan tiap fungsi
case 3: selection_sort();break; //pemanggilan tiap fungsi
case 4: insertion_sort();break; //pemanggilan tiap fungsi
}
}while(pil != 5);
return 0; //mengembalikan nilai null dari program utama
}
Hasil Program Diatas :
Download PDF Kumpulan Laporan Struktur Data disini : https://drive.google.com/drive/folders/0BwweuGyQqkVJV2ZSSUpSZDMzcGM?usp=sharing
Tidak ada komentar:
Posting Komentar