Sorting and Searching
Sorting and Searching
1. Sorting
adalah proses mengurutkan data dari terbesar ke terkecil atau sebaliknya.
contoh:
mengurutkan dari terkecil hingga terbesar
#include<stdio.h>
int angka[100],jumlah;
int swap(int a,int b)
{
int temp;
temp=angka[a];
angka[a]=angka[b];
angka[b]=temp;
}
void bubble()
{
int i,j;
for(i=0;i<jumlah;i++)
{
for(j=i+1;j<jumlah;j++)
{
if(angka[i]>angka[j])
{
swap(i,j);
}
}
}
}
void print()
{
int i;
for(i=0;i<jumlah;i++)
{
printf("%d ",angka[i]);
}
printf("\n");
}
int main()
{
int i;
scanf("%d",&jumlah);
for(i=0;i<jumlah;i++)
{
scanf("%d",&angka[i]);
}
bubble();
print();
return 0;
}
diatas adalah contoh bubblesort.
jenis sorting lain adalah selection sort, insertion sort,dll.
konsep selection sort adalah dari array 0 sampai akhir dicari angka minimum dan diletakan pada array 0, setelah itu dari array 1 sampai akhir dicari minimun nya dan ditaruh di array 1 dan seterusnya sampai semua terurut.
konsep insertion sort adalah menyimpan angka di suatu int tampung dan membandingkan dengan isi array sebelumnya (mulai dari array 1) misal:
ada 5 data : 99 89 72 2 6
temp=kosong
pertama temp diisi dengan 89 lalu dicheck dengan 99 ternyata 89 < 99
lalu
data : 89 99 72 2 6
temp lalu diisi dengan 72 lalu dicheck dengan 99 ternyata 72<99
karena yang dicheck bukan array 0 maka akan pengecheckan dilanjutkan
ternyata 72 < 89
maka data menjadi 72 89 99 2 6
pada saat 72 di check dengan 99 ternyata 72<99 maka 99 mengambil tempat 72 dan sebaliknya 72 mengambil tempat 99 dan 72 dicheck dengan 89 ternyata 72<89 maka mereka berdua ditukar posisinya.
2 akan dicheck dengan 72 89 99
6 akan dicheck dengan 2 72 89 99 dan ternyata 6 tidak lebih kecil dari 2 maka tidak dirubah tempatnya
dan data menjadi 2 6 72 89 99
diatas adalah contoh bubblesort.
jenis sorting lain adalah selection sort, insertion sort,dll.
konsep selection sort adalah dari array 0 sampai akhir dicari angka minimum dan diletakan pada array 0, setelah itu dari array 1 sampai akhir dicari minimun nya dan ditaruh di array 1 dan seterusnya sampai semua terurut.
konsep insertion sort adalah menyimpan angka di suatu int tampung dan membandingkan dengan isi array sebelumnya (mulai dari array 1) misal:
ada 5 data : 99 89 72 2 6
temp=kosong
pertama temp diisi dengan 89 lalu dicheck dengan 99 ternyata 89 < 99
lalu
data : 89 99 72 2 6
temp lalu diisi dengan 72 lalu dicheck dengan 99 ternyata 72<99
karena yang dicheck bukan array 0 maka akan pengecheckan dilanjutkan
ternyata 72 < 89
maka data menjadi 72 89 99 2 6
pada saat 72 di check dengan 99 ternyata 72<99 maka 99 mengambil tempat 72 dan sebaliknya 72 mengambil tempat 99 dan 72 dicheck dengan 89 ternyata 72<89 maka mereka berdua ditukar posisinya.
2 akan dicheck dengan 72 89 99
6 akan dicheck dengan 2 72 89 99 dan ternyata 6 tidak lebih kecil dari 2 maka tidak dirubah tempatnya
dan data menjadi 2 6 72 89 99
2. Searching
digunakan untuk mencari letak suatu nilai yang kita cari.
contoh :
Menggunakan binary search dengan sorting terlebih dahulu.
contoh :
Menggunakan binary search dengan sorting terlebih dahulu.
#include<stdio.h>
int angka[100],jumlah,mid,key;
int swap(int a,int b)
{
int temp;
temp=angka[a];
angka[a]=angka[b];
angka[b]=temp;
}
void bubble()
{
int i,j;
for(i=0;i<jumlah;i++)
{
for(j=i+1;j<jumlah;j++)
{
if(angka[i]>angka[j])
{
swap(i,j);
}
}
}
}
void print()
{
int i;
printf("Sorted array: ");
for(i=0;i<jumlah;i++)
{
printf("%d ",angka[i]);
}
printf("\n");
}
int binarysearch(int a,int b)
{
mid=(a+b)/2;
if(angka[mid]<key)
{
a=mid+1;
return binarysearch(a,b);
}
if(angka[mid]>key)
{
b=mid-1;
return binarysearch(a,b);
}
return mid;
}
int main()
{
int i;
int left,right;
scanf("%d",&jumlah);
left=0;
right=jumlah-1;
for(i=0;i<jumlah;i++)
{
scanf("%d",&angka[i]);
}
bubble();
print();
printf("Enter key : ");
scanf("%d",&key);
binarysearch(left,right);
printf("location at index : %d\n",mid);
return 0;
}
searching digunakan untuk menemukan lokasi key(data yang kita cari)
masih ada beberapa cara searching yaitu linear search dan interpolation search
konsep linear search adalah looping dari 0 sampai array terakhir sampai ketemu nilai dimana = key lalu output indexnya dan break, jika sudah sampai array terakhir dan masih !=key maka data yang sama dengan key tersebut "tidak ada"
konsep interpolation search hampir sama dengan binary search yang berbeda hanya pada rumus mencari midnya yaitu pada interpolation search
mid=((key-data[min]) / (data[max]-data[min]))*(max-min)+min
pada interpolation search juga dibutuhkan sorting terlebih dahulu sama seperti pada binary search.
2201746991
binus.ac.id
skyconnectiva.com
Hermawan
int angka[100],jumlah,mid,key;
int swap(int a,int b)
{
int temp;
temp=angka[a];
angka[a]=angka[b];
angka[b]=temp;
}
void bubble()
{
int i,j;
for(i=0;i<jumlah;i++)
{
for(j=i+1;j<jumlah;j++)
{
if(angka[i]>angka[j])
{
swap(i,j);
}
}
}
}
void print()
{
int i;
printf("Sorted array: ");
for(i=0;i<jumlah;i++)
{
printf("%d ",angka[i]);
}
printf("\n");
}
int binarysearch(int a,int b)
{
mid=(a+b)/2;
if(angka[mid]<key)
{
a=mid+1;
return binarysearch(a,b);
}
if(angka[mid]>key)
{
b=mid-1;
return binarysearch(a,b);
}
return mid;
}
int main()
{
int i;
int left,right;
scanf("%d",&jumlah);
left=0;
right=jumlah-1;
for(i=0;i<jumlah;i++)
{
scanf("%d",&angka[i]);
}
bubble();
print();
printf("Enter key : ");
scanf("%d",&key);
binarysearch(left,right);
printf("location at index : %d\n",mid);
return 0;
}
masih ada beberapa cara searching yaitu linear search dan interpolation search
konsep linear search adalah looping dari 0 sampai array terakhir sampai ketemu nilai dimana = key lalu output indexnya dan break, jika sudah sampai array terakhir dan masih !=key maka data yang sama dengan key tersebut "tidak ada"
konsep interpolation search hampir sama dengan binary search yang berbeda hanya pada rumus mencari midnya yaitu pada interpolation search
mid=((key-data[min]) / (data[max]-data[min]))*(max-min)+min
pada interpolation search juga dibutuhkan sorting terlebih dahulu sama seperti pada binary search.
2201746991
binus.ac.id
skyconnectiva.com
Hermawan
Komentar
Posting Komentar