Sorting dengan shell sort tema kita kali ini, baik disini saya akan membahas metode sorting dengan shell sort pada algoritma struktur data ini saya menggunakan bahasa c atau c++ dalam pemrogramannya.
langsung saja ini saya beri source code nya.
=================================================================
#include"stdio.h"
#include<time.h>
#define max 1000000
int key,n,data[max],temp[max],tamp;
long int t1,t2;
int i,j,jarak,n,didswap;
double banding=0,swap=0;
void input(){
printf("\nmasukan jumlah data: ");
scanf("%d",&n);
for(i=0;i<n;i++){
data[i]=rand()%100000;
temp[i]=data[i];
}
}
void inputurut(){
n=99999;
for(i=0;i<n;i++){
data[i]=i;
temp[i]=data[i];
}
}
void print(){
printf("jumlah waktu = %ld\n",t2-t1);
}
void tampil(){
printf("\njumlah waktu = %ld\n",t2-t1);
printf("jumlah perbandingan = %g\n",banding);
printf("jumlah swap = %g\n",swap);
}
void tukar(int *x,int *y){
tamp=*x;
*x=*y;
*y=tamp;
}
void shellsort(){
int k;
jarak=n;
while(jarak>1)
{
jarak=jarak/2;
didswap=0;
while(didswap==0)
{
didswap=1;
for(j=0; j<n-jarak; j++)
{
i=j+jarak;
banding++;
if(data[j]>data[i])
{
tukar(&data[j], &data[i]);
swap++;
didswap=0;
}
}
}
}
}
void insertion(){
for(i=1; i<n; i++)
{
key=temp[i];
j=i-1;
banding++;
while((j>=0)&&(key<temp[j]) )
{ banding++;
if(key<temp[j]){
temp[j+1]=temp[j];
j--;
swap++;
}
}
temp[j+1]=key;
}
}
void tampildata(){
puts("data setelah diurutkan insertion");
for(i=0;i<n;i++){
printf("%d ",data[i]);
}
puts(" ");
}
void tampiltemp(){
puts("data setelah diurutkan shellshort");
for(i=0;i<n;i++){
printf("%d ",temp[i]);
}
puts(" ");
}
void pil1(){
input();
insertion();
tampiltemp();
puts(" ");
shellsort();
tampildata();
}
void pil2(){
input();
puts("\ndata shellsort");
time(&t1);
shellsort();
time(&t2);
tampil();
puts("\ndata insertion");
time(&t1);
insertion();
time(&t2);
tampil();
}
void pil3(){
inputurut();
time(&t1);
puts("\ndata insertion");
insertion();
time(&t2);
tampil();
time(&t1);
puts("\ndata shellsort");
shellsort();
time(&t2);
tampil();
}
main(){
char jawab,pil;
do{
do{ system("cls");
puts("\t PROGRAM SHELL SORT");
puts("\t by: achmad sayfudin\n");
printf("\t MENU \n");
printf("\n 1.cek urutan random\n 2.kinerja data random\n 3.kinerja data urut");
fflush(stdin);
printf("\n masukan pilihan anda: ");
pil=getchar();
if (pil=='1'){
pil1();
}
else if(pil=='2'){
pil2();
}
else if(pil=='3'){
pil3();
}
printf("\n\n apakah ingin kembali: ");
fflush(stdin);
jawab=getchar();
}while(jawab=='y'||jawab=='Y');
printf("\n apakah ingin input lagi(y/t): ");
fflush(stdin);
jawab=getchar();
}while(jawab=='y'||jawab=='Y');
}
/*
1.jalankan dengan input jumlah data tapi dengan data di random
2.output yang pertama
-gunakan insertion
tampil= data terurut
running time
-gunakan shell sort
tampil=data terurut dengan random dan tidak random
running time.
*/
=================================================================
berikut output program nya.
