About Me
- Aha Project's Blog
- "WELCOME... Terima Kasih telah bergabung dengan Kami...ENJOY IT"
Kamis, 03 Juni 2010
INSERTION SORT C++
6/03/2010 07:33:00 PM | 
Di.post.kan oleh
Aha Project's Blog
I. INSERTION SORTING
Sorting atau pengurutan data adalah proses yang sering harus dilakukan dalam pengolahan data. Bahkan mesin otomatik yang pertama lahir adalah mesin pengurut, dan masih dipakai sampai saat ini.
Ada 2 macam pengurutan:
a. Pengurutan Internal
Pengurutan terhadap sekumpulan data yang disimpan dalam media internal komputer yang dapat diakses setiap elemennya secara langsung.
Dapat dikatakan sebagai pengurutan tabel.
b. Pengurutan Eksternal
Pengurutan data yang disimpan dalam memori sekunder, biasanya bervolume besar sehingga tidak mampu untuk dimuat semuanya dalam memori.
Macam – macam algoritma pengurutan antara lain:
. Counting Sort . Quick Sort
. Bubble Sort . Maximum Sort, dan
. Selection Sort . Insertion Sort
Kali ini kita akan mencoba teknik sorting integer dengan metode Insertion Sorting. Insertion Sorting idenya adalah mencari tempat yang ‘tepat’ untuk setiap elemen tabel, dengan cara sequential search, kemudian setiap kali menyisipkan sebuah elemen tabel yang diproses ke tempatnya yang seharusnya. Proses dilakukan sebanyak N tahapan (yang dalam Sorting disebut sebagai ‘Pass’).
Berikut merupakan contoh algoritma dari program pengurutan integer dalam metode Insertion Sorting :
“ Algoritma Insertion Sort “
/* KAMUS GLOBAL */
#include
#include
/* ---- PROTOTIPE ---- */
typedef struct
{ int isi[101]; /* wadah elemen */
int len; /* banyak yang terisi */
} tabint;
void createTabel(tabint *T);
/* I.S.: - */
/* F.S.: T[1] .. T[100] terisi nilai 0 */
/* proses: menginisialisasi nilai T[i] dengan 0 */
void printTabel(tabint T);
/* I.S.: T terdefinisi */
/* F.S.: - */
/* proses: mencetak nilai T[1] .. T[T.len] */
void isiTabel(tabint *T, int N);
/* I.S.: T sudah di-create */
/* F.S.: T[1] .. T[N] terisi nilai */
/* proses: mengisi nilai T[1] .. T[N] dari keyboard */
void i_sort_ascending(tabint *T);
/* I.S.: T yang sudah di-isi */
/* F.S.: T yang telah diurutkan dengan metode insertion sort */
/* proses: mengurutkan T[1] .. T[N] */
void i_sort_descending(tabint *T);
/* I.S.: T yang sudah di-isi */
/* F.S.: T yang telah diurutkan dengan metode insertion sort */
/* proses: mengurutkan T[1] .. T[N] */
int main()
{
/* KAMUS MAIN */
int c;
int x;
int pil,lagi;
tabint A; /* A : tabint */
/* ALGORITMA */
cout<<"Halo! Kita akan memanipulasi tabint.\n";
createTabel(&A);
do
{
clrscr();
cout<<"\nMENU UTAMA";
cout<<"\n1. Input Tabel";
cout<<"\n2. Urutkan Data ISORT Ascending";
cout<<"\n3. Urutkan Data ISORT Descending";
cout<<"\n\n Pilihan Anda : "; cin>>pil;
if(pil==1)
{
cout<<"\nMasukkan panjang tabel = "; cin>>x;
isiTabel(&A,x);
printTabel(A);
}
else if (pil==2)
{
cout<<"\n\n Urutkan dengan insertion sort ascending";
i_sort_ascending(&A);
printTabel(A);
}
else if (pil==3)
{
cout<<"\n\n Urutkan dengan insertion sort descending";
i_sort_descending(&A);
printTabel(A);
}
cout<<"\n\nKe Menu lagi [Y/T] : " ; lagi=getche();
} while (lagi=='Y' || lagi=='y');
getch();
return 0;
}
/* ---- BODY/REALISASI PROTOTIPE ---- */
void createTabel(tabint *T)
/* I.S.: - */
/* F.S.: T[1] .. T[100] terisi nilai 0 */
/* proses: menginisialisasi nilai T[i] dengan 0 */
{ /* KAMUS LOKAL */
int i;
/* ALGORITMA */
(*T).len = 100;
for ( i = 1; i <= (*T).len; i++ ) /* mengisi A */
{
(*T).isi[i] = 0;
}
}
void printTabel(tabint T)
/* I.S.: T terdefinisi */
/* F.S.: - */
/* proses: mencetak nilai T[1] .. T[T.len] */
{ /* KAMUS LOKAL */
int i;
/* ALGORITMA */
for ( i = 1; i <= T.len; i++ ) /* mengisi A */
{
cout<<"\n A["<<<"] = "<
}
}
void isiTabel(tabint *T, int N)
/* I.S.: T sudah di-create */
/* F.S.: T[1] .. T[N] terisi nilai */
/* proses: mengisi nilai T[1] .. T[N] dari keyboard */
{ /* KAMUS LOKAL */
int i;
/* ALGORITMA */
(*T).len = N;
for ( i = 1; i <= (*T).len; i++ ) /* mengisi A */
{
cout<<" Elemen ke-"<<<" = " ; cin >>(*T).isi[i];
}
}
void i_sort_ascending(tabint *T)
/* I.S.: T yang sudah di-isi */
/* F.S.: T yang telah diurutkan dengan metode insertion sort */
/* proses: mengurutkan T[1] .. T[N] */
{
int i,j,temp;
i=2;
while(i<=(*T).len)
{
temp=(*T).isi[i];
j=i-1;
while(j>=1 &&(*T).isi[j]>temp)
{
(*T).isi[j+1]=(*T).isi[j];j--;
}
(*T).isi[j+1]=temp;i++;
}
}
void i_sort_descending(tabint *T)
/* I.S.: T yang sudah di-isi */
/* F.S.: T yang telah diurutkan dengan metode insertion sort */
/* proses: mengurutkan T[1] .. T[N] */
{
int i,j,temp;
i=2;
while(i<=(*T).len)
{
temp=(*T).isi[i];
j=i-1;
while(j>=1 &&(*T).isi[j]
{
(*T).isi[j+1]=(*T).isi[j];j--;
}
(*T).isi[j+1]=temp;i++;
}
}
Langganan:
Komentar (Atom)
