Bahasa C : Searching, Sequential Search

Pencarian beruntun (Sequential) adalah proses membandingkan setiap elemen larik satu per satu secara beruntun, mulai dari elemen pertama sampai elemen yang dicari ditemukan atau seluruh elemen sudah diperiksa. 

Sequential adalah suatu teknik pencarian data dalam array ( 1 dimensi ) yang akan menelusuri semua elemen-elemen array dari awal sampai akhir, dimana data-data tidak perlu diurutkan terlebih dahulu.  Kemungkinan terbaik (best case) adalah jika data yang dicari terletak di indeks array terdepan (elemen array pertama) sehingga waktu yang dibutuhkan untuk pencarian data sangat sebentar (minimal). Sedangkan kemungkinan terburuk (worst case) adalah jika data yang dicari terletak di indeks array terakhir (elemen array terakhir) sehingga waktu yang dibutuhkan untuk pencarian data sangat lama (maksimal).Sequential search memiliki proses sebagai berikut:

Pencarian beruntun terbadi dua :

1. Pencarian beruntun pada larik tidak terurut;

2. Pencarian beruntun pada larik terurut.

Pencarian Beruntun Pada Larik Tidak Terurut

13

16

14

21

76

21

Pencarian dilakukan dengan memeriksa setiap elemen larik mulai dari

elemen pertama sampai elemen yang dicari ditemukan atau sampai

seluruh elemen sudah diperiksa.

Contoh:

Misal nilai yang dicari adalah X = 21, maka elemen yang

diperiksa : 13, 16, 14, 21 (ditemukan!)

Indeks larik yang dikembalikan: IX = 4

Misal nilai yang dicari adalah X = 15, maka elemen yang

diperiksa : 13, 16, 14, 21, 76, 21 (tidak ditemukan!)

Indeks larik yang dikembalikan: IX = 0

Algoritma Pencarian Beruntun Pada Larik Yang Tidak Terurut

Kamus

Const Nmaks : integer = 100

Type Larik100 = array [1..Nmaks] of integer

Procedure CariRuntun(input L: larik, input n:integer, input X: integer,

input/output IX:integer)

Algoritma

I ← 1

while (I < N) and (L[I] ≠ X) do

I ← I + 1

endwhile

if (L[I] ≠ X) then

IX ← 0

else

IX ← I

endif

Pencarian Beruntun Pada Larik Yang Terurut

Jika larik sudah terurut (misal terurut menaik, yaitu untuk setiap I=1..N, Nilai[I-1]<Nilai[I] atau terurut mengecil, yaitu untuk setiap I=1..N, Nilai[I-1]>Nilai[I]), maka proses pencarian lebih singkatdibandingkan pencarian larik yang tidak terurut.

Procedur Pencarian Terurut

Procedure CariRuntunurut(input L: larik, input n:integer,

input X: integer, input/output IX:integer)

Algoritma

I ← 1

while (I < N) and (L[I] < X) do

I ← I + 1

endwhile

if (L[I] = X) then

IX ← I

else

IX ← 0

contoh Program 
  #include <stdio.h>
int main()
{
    //deklarasi variabel
    int A[10],index[10], i,j,k;
    //proses penginputan data
    for(i=0;i<10;i++)
    {
        printf("Data ke-%d:",i+1);
        scanf("%d",&A[i]);
    }
//memasukkan data yang akan dicari ke dalam K
    printf("Masukkan data yang akan anda cari:");
    scanf("%d",&k);
    //proses pencarian data
    j=0;
    for (i=0;i<10;i++)
    {
        if(A[i]==k)
        {
            index[j]=i;
            j++;
        }
    }
    //jika data ditemukan dalam array
    if (j>0)
    {
        printf("Data %d yang dicari ada %d buah\n",k,j);
        printf("Data tersebut terdapat dalam index ke :");
        for(i=0;i<j;i++)
        {
            printf(" %d ",index[i]);
        }
        printf("\n");
    }
    //jika tidak ditemukan
    else
    {
        printf("Data tidak ditemukan dalam array\n");
    }
getch();
return 1;
}


hasilnya 

Bahasa C : Searching, Sequential With Sentinel Search

Yang dimaksud dengan sentinel adalah elemen fiktif yang sengaja ditambahkan sesudah elemen terakhir larik. Jika elemen larik terakhir L[N], maka sentinel dipasang pada elemen L[N+1]. Sentinel ini harganya sama dengan elemen yang dicari. Akibatnya proses pencarian selalu berhasil menemukan data yang dicari. Walaupun demikian harus diperiksa lagi letak data tersebut ditemukan, apakah:

1. Di atara elemen-elemen larik sesungguhnya, yaitu L[1]…L[N]

2. Pada elemen fiktif (L[N+1]) berarti X sesungguhnya tidak terdapat di dalam larik L.

Pencarian Bagidua

• Pencarian bagidua atau pencarian biner adalah metode pencarian yang diterapkan pada sekumpulan data yang sudah terurut (terurut menaik atau terurut menurun).

• Data yang terurut syarat mutlak penerapan algoritma ini.

• Salah satu keuntungan data terurut adalah memudahkan pencarian, dalam hal ini pencarian bagidua.

Langkah-langkah Pencarian Bagidua

Misalkan indeks kiri adalah Ia dan indeks kanan adalah Ib. Kondisi awal Ia=1 dan Ib = N. Langkah 1. Bagi dua elemen larik pada elemen tengah. Elemen tengah adalah elemen dengan indeks k = (Ia+Ib) div 2  (elemen tengah , L[k], membagi larik menjadi dua bagian, yaitu bagian kiri  L[Ia..k-1] dan bagian kanan L[K+1..Ib]) Kamis, 25 Mei 2006 Algoritma dan Pemrograman II 13 Langkah 2. Periksa apakah L[k] = X. jika L[k] = X, pencarian dihentikan sebab X sudah ditemukan. Tetapi, jika L[k] ≠ X, harus ditentukan apakah

pencarian akan dilakukan di larik bagian kiri atau di bagian kanan. Jika L[k] < X, maka pencarian dilakukan pada bagian kiri. Sebaliknya, jika L[k] > X, pencarian dilakukan pada larik bagian kanan. Langkah 3. Ulangi langkah 1 sampai X ditemukan atau Ia > Ib (ukuran larik sudah nol).

#include <stdio.h>

int main(){
    int data[7] = {3,12,9,-4,21,6};
    int cari,i;
    printf("masukkan data yang ingin dicari = ");
    scanf("%d",&cari);
    data[6] = cari;
    i=0;
        while(data[i] != cari){
        i++;
        }
            if(i<6){
                printf("Data ada!\n");
            }
            else{
                printf("Data tidak ada!\n");
            }
getch();
return 1;
}

Bahasa C : Searching, Interpolation Search

 

Pengertian

Proses pencarian data ini hampir sama dengan proses pencarian binary search, pencarian ini juga dilakukan pada kumpulan data yang sudah urut. Akan tetapi jika pada binary search kita membagi data menjadi 2 bagian tiap prosesnya, pada interpolation search kita akan membagi data menurut rumus sebagai berikut:

Posisi = ( kunci – data[low] / data[high] – data[low] ) * ( high – low ) + low

Singkatnya proses pencarian interpolation search hampir mirip dengan proses pencarian kata dikamus, yaitu kita mencari data yang dimaksud dengan cara memperkirakan letak data

Contoh Programnya

#include<stdio.h>
int main()
{
  //deklarasi variable
  int A[10], i,j,k,tkr,low,high,pos,tm;
  //proses penginputan data
  for(i=0;i<10;i++)
  {
    printf("data ke-%d:",i+1);
    scanf("%d",&A[i]);
  }
  //Input data yang akan dicari
  printf("Masukkan data yang akan anda cari:");
  scanf("%d",&k);
  //proses pengurutan data
  for(i=0;i<10;i++)
  {
    for(j=i+1;j<10;j++)
    {
        if (A[i]>A[j])
        {
            tkr=A[i];
            A[i]=A[j];
            A[j]=tkr;
        }
    }
  }
  //proses pencarian data
  tm=0;
  high=9;
  low=0;
  do
  {
      pos = ((k - A[low]) / (A[high] - A[low]))*(high-low) + low;
      if (A[pos] == k)
        {
            tm++;
            break;
        }
      if (A[pos] > k)
      high = pos-1;
            else
      if (A[pos] < k)
      low = pos + 1;
  }
  while(k >= A[low] && k <= A[high]);
  if (tm>0)
  {
     printf("data %d yang dicari ada dalam array\n",k);
  }
  //jika tidak ditemukan
  else
  {
     printf("data tidak ditemukan dalam array\n");
  }
 getch();
 return 1;
}

Hasilnya ..

 

Bahasa C : Searching, Binary Search

Jika kita mempunyai sebuah file dari record-record yang telah dijalankan, kita dapat melanjutkan  menghapuskan memory pemeriksaan yang diperlukan untuk mendapatkan kembali sebuah record yang telah dipakai oleh suatu teknik binary search. Suatu binary search dibandingkan dengan kunci dari pencarian record dengan record tengah dari sebuah file. Kemudian masing-masing pencarian record yang telah ditempatkan atau setengah dari file yang telah dihilangkan dengan pertimbangan yang lebih lanjut. Dalam kasus yang sebelumnya, proses pembandingan dari record tengah dilanjutkan dalam record-record selanjutnya. Jika kita harus menghilangkan bagian atas dari sebuah file termasuk record yang telah dibandingkan berlawanan. Selanjutnya jika kita harus menghilangkan bagian bawah dari sebuah file termasuk record yang telah dibandingkan berlawanan. Dalam pengulangan proses dari pembandingan berlawanan dari record tengah, kita akhirnya akan menempatkan record yang kita inginkan atau menentukan bahwa itu tidak ada dalam file ketika tidak ada record-record selanjutnya.

Contoh Program Binary Search..

#include<stdio.h>
int main()
{
    //deklarasi variabel
    int A[10], i,j,k,tkr,top,bottom,middle,tm;
    //proses penginputan data
    for(i=0;i<10;i++)
    {
        printf("Data ke-%d:",i+1);
        scanf("%d",&A[i]);
    }
    printf("Masukkan data yang akan anda cari:");
    scanf("%d",&k);
    //proses pengurutan data
   
    for(i=0;i<10;i++)
    {
        for(j=i+1;j<10;j++)
        {
            if (A[i]>A[j])
            {
                tkr=A[i];
                A[i]=A[j];
                A[j]=tkr;
            }
        }
    }
    //proses pencarian data
    tm=0;
    top=9;
    bottom=0;
    while(top>=bottom)
    {
        middle=(top+bottom)/2;
        if(A[middle]==k)
        {
            tm++;
        }
        if(A[middle]<k)
        {
            bottom=middle+1;
        }
        else
        {
            top=middle-1;
        }
    }
    if (tm>0)
    {
      printf("Data %d yang dicari ada dalam array\n",k);
    }
    //jika tidak ditemukan
    else
    {
      printf("Data tidak ditemukan dalam array\n");
   
    }
getch();
return 1;
}

hasilnya....

Searching

Algoritma searching adalah algoritma untuk mencari sebuah nilai dari sekumpulan nilai yang bertipe sama. Kumpulan data yang dimaksud dalam kuliah Algoritma dan Pemrograman II adalah array (larik). Algoritma searching dapat dikelompokkan menjadi 2, yaitu pencarian terhadap kumpulan data yang belum terurut dan pencarian terhadap kumpulan data yang sudah terurut. Salah satu contoh algoritma searching untuk data tidak terurut adalah Sequential Search, sedangkan contoh algoritma searching untuk data terurut adalah Binary Search.

Misakan Larik didefinisikan seperti di bawah ini:

type ElemenLarik : integer

type Larik : array of ElemenLarik

maka algoritma searching dengan metode Sequential Search untuk data yang belum terurut adalah:

Procedure seqSearch(input T : Larik, nElm : integer, x : ElemenLarik; output Ketemu : boolean, iX : integer) {KAw : Larik T terisi mulai indeks 1 s/d nElm, dan x adalah nilai yang dicari} {KAk : Jika ada elemen T bernilai x maka ketemu bernilai true dan iX adalah indeks tempat x ditemukan. Jika tidak ada elemen T bernilai x maka ketemu bernilai false dan iX bernilai 0}

Kamus

Deskripsi if (nElm=0) then ketemu ß false iX ß 0 else iX ß 1 while (T[iX]≠x) and (iX<nElm) do iX ß iX + 1 if (T[iX]=x) then ketemu ß true else ketemu ß false iX ß 0

Sorting

Sorting merupakan sebuah proses untuk mengatur item dalam suatu urutan tertentu ( menaik atau menurun ).




Operasi dasar sorting :

• Membandingkan nilai untuk membandingkan nilai hanya digunakan operator : =, <, >  atau kombinasi diantara operator tersebut untuk membandingka nnilai-nilai yang akan diurutkan. 
•  Memindahkan nilai-nilai dalam daftar ke posisi yang sesuai

Contoh-contoh algoritma sorting:


    * Bubble Sort
    * Insertion Sort
    * Selection Sort
    * Counting Sort
    * Maximum SortShaker Sort
    * Quick Sort
    * Radix Sort
    * Shell Sort
    * Heap Sort
    * Merge Sort

Bahasa C : Sorting Bubble Sort(Season 3)

Sekarang kita lihat bagaimana pengurutan Bubble sort yang di implementasikan pada program pengurutan huruf dalam kalimat dan spasi di hilangkan.

Program Pengurutan Huruf dalam Kalimat

Coding 3 file

• file.h (header)

#include<stdio.h>
#include<string.h>

void swaping();
void CetakArray();
void Bubblesort();

• file.c (prosedure utama dalam program)

 #include "gumi.h"

void CetakArray(char A[225],int n){
    int g;
    for(g=0;g<n;g++){
        A[g]=tolower(A[g]);
        printf("%c",A[g]);
    }
}

void swaping(char A[225], int u, int tmp){
    tmp=A[u];
    A[u]=A[u-1];
    A[u-1]=tmp;
}

void Bubblesort(char A[225],int n){
    int m, u, tmp;
      
      
        for(m=0;m<(n-1);m++){
            for (u=(n-1);u>=(m+1);u--){
                if(A[u]<A[u-1]){
                    swaping(A,u,tmp);
                }
            }
        }
        printf("\n");
}

• main.c (perintah dalam program utama)

 #include "gumi.h"

int main(){
    int  karakter;
    char string[30];
    system("cls");
    printf(".....Bubblesort Kalimat.....\n");
    printf("by : Gumilang Anggun 0905734\n");
    printf("\n");
    printf("\n");
    printf("Masukan Sebuah Kalimat: ");
    printf("\n");
    gets(string);
    int panjang=strlen(string);
    printf("Kalimat Asli: \n");
    CetakArray(string,panjang);
    Bubblesort(string,panjang);
    printf("Hasil AKhir: \n");
    CetakArray(string,panjang);
    do{
        karakter = getche();
        if (isspace(karakter)) break;
        }
// perintah unuk menghilangkan spasi pada kalimat
        while(0);
        return 0;
}

Untuk cara mengcompilenya lihat disini...