Nama : Agung Wijaya Kusuma
NIM : 140010222
Kelas : AB141
Nama
Dosen : Ida Bagus Kadek Surya Arnawa. S.Kom
Nama
Asisten Dosen : Steven Anthony
E. Sorting
Sorting adalah proses mengatur
sekumpulan objek menurut urutan atau susunan tertentu.Urutan objek dapat menaik
( Ascending ), yaitu urutan objek yang disusun mulai dari Nilai terkecil hingga
terbesar atau menurun ( Descending ), yaitu urutan objek yang disusun mulai
dari Nilai terbesar hingga terkecil. Untuk dapat melakukan proses pengurutan
dapat menggunakan beberapa metode seperti :
1.
Selection
sort
2.
Insertion
sort
1. Selection Sort
Selection Sort adalah suatu metode
pengurutan yang membandingkan elemen yang sekarang dengan elemen berikut sampai
ke elemen yang terakhir. Jika ditemukan elemen lain yang lebih kecil dari
elemen sekarang maka dicatat posisinya dan langsung ditukar.
Misalkan ada data-data sebagai berikut
:
2, 34, 22, 1
Daftar bilangan diatas masih belum
urut dari kecil ke besar. Kita ingin melakukan pengurutan dari yang terkecil
sampai yang terbesar dari 3 data tersebut.
Langkah pertama , membandingkan satu
persatu sampai dengan yang terkakhir. Langkah-langkahnya sebagai berikut :
Langkah pertama :
Pembanding Posisi
2<34 1
2<22 1
2<1 4
Tukar data pada posisi 1 dengan data
posisi 4
Hasil sementara : 1, 34,22,2
Langkah Kedua :
Pembanding Posisi
34>22 3
22<5 4
Tukar data pada posisi 2 dengan data
posisi 4
Hasil akhir : 1, 2, 22, 34
Proses pengurutan data di atas
memerlukan 2 kali perulangan.
Contoh Selection Sort dalam coding :
#include<iostream.h>
#include<conio.h>
int data[10];
int n;
void tukar(int a, int b)
{
int
t;
t=data[b];
data[b]=data[a];
data[a]=t;
}
void selection_sort()
{
int
pos,i,j;
for(i=0;i<n-1;i++)
{
pos=i;
for(j=i+1;j<n;j++)
{
if(data[j]<data[pos])pos=j;
}
if(pos!=i)
{
tukar(pos,i);
}
}
cout<<"selection sort selesai !"<<endl;
cout<<"Data : "<<endl;
for(int i=0;i<n;i++)
{
cout<<data[i]<<"
";
}
cout<<endl;
}
void input()
{
cout<<"Masukkan
jumlah data = ";
cin>>n;
for(int i=0;i<n;i++)
{
cout<<"Masukkan
data ke - "<<(i+1)<<" = " ;
cin>>data[i];
}
}
void main()
{
int
pil;
clrscr();
do
{
clrscr();
cout<<"1. Input
Data"<<endl;
cout<<"2.
Selection Sort"<<endl;
cout<<"3.
Exit"<<endl;
cout<<"Masukkan Pilihan anda = ";
cin>>pil;
switch(pil)
{
case 1: input();break;
case 2:
selection_sort();break;
}
getch();
}
while(pil!=3);
}
2. Insertion Sort
Insertion sort merupakan metode
pengurutan dengan cara menyisipkan elemen array pada posisi yang tepat. Selama
pencarian posisi yang tepat dilakukan pergeseran elemen array.
Misalnya dalam permainan kartu, kartu
yang dicabut biasanya disisipkan oleh pemain pada posisi yang tepat sehingga
penambahan kartu tersebut membuat semua kartu tetap terurut.
Contoh :
Program untuk mengurutkan elemen array
secara menaik dengan metode Insertion sort
/*Program Pengurutan metode Insertion
sort
Pengurutan secara Menaik*/
#include <iostream.h>
#include <conio.h>
#include <iomanip.h>
void main()
{
int
Nilai[20];
int i, j, k, N;
int temp;
cout<<”Masukkan Banyak Bilangan
: “;
cin>>N;
for(i=0;i<N;i++)
{
cout<<”Elemen
ke-“<<i<<” : “;
cin>>Nilai[i];
}
//Proses Cetak sebelum diurutkan
cout<<endl;
cout<<”Data sebelum diurut :
“;
for(i=0;i<N;i++)
cout<<setw(3)<<Nilai[i];
//Proses Pengurutan
for(i=1;i<N;i++)
{
temp = Nilai[i];
j=i – 1;
while ((temp <= Nilai[j])
&& (j>=1))
{
Nilai[j+1]=Nilai[j];
j--;
}
If (temp >= Nilai[j])
Nilai[j+1] = temp;
else
{
Nilai[j+1]=Nilai[j];
Nilai[j] = temp;
}
cout<<endl;
for(k=0;k<N;k++)
cout<<setw(3)<<Nilai(k);
}
//Proses Cetak setelah diurutkan
cout<<endl;
cout<<”Data setelah diurut : “;
for(i=0; i<N; i++)
cout<<setw(3)<<Nilai[i];
getch();
}
Sumber : Buku Konsep dan Implementasi
Struktur Data dengan C++
Oleh : Lamhot Sitorus dan David J.M
Sembiring, Andi Kristanto, S.Kom
Penerbit : Andi dan Graha Ilmu
0 komentar:
Posting Komentar