Algoritma Searching

Pengertian Algoritma Searching

Searching merupakan proses dasar dalam pengolahan data. Yaitu untuk menemukan nilai tertentu dalam sekumpulan data yang bertipe sama. Algoritma searching dijelaskan secara luas sebagai algoritma yang menerima masukan berupa sebuah masalah dan menghasilkan sebuah solusi untuk masalah tersebut. Algoritma searching menerima sebuah argument kunci dan dengan langkah-langkah tertentu akan mencari rekaman dengan kunci tersebut. Setelah melakukan proses pencarian, akan diperoleh salah satu dari dua kemungkinan, yaitu data yang dicari ditemukan atau tidak ditemukan.
Macam-macam Algoritma Searching
1. Pencarian Beruntun (Sequential Search)
Konsep
a)      Membandingkan setiap elemen larik satu per satu secara urut (beruntun), mulai dari elemen pertama sampai dengan elemen yang terakhir sampai data ditemukan atau tidak ditemukan.
b)      Proses pencarian akan dihentikan jika data yang dicari sudah ditemukan.
c)      Merupakan metode yang paling sederhana
d)     Kelemahan pada kasus ini adalah, untuk N elemen data harus dilakukan pencarian sebanyak N kali pula.
Algoritma
Algoritma pencarian beruntun dapat dituliskan sebagai berikut:
(1)   i ← 0
(2)   ketemu ← false
(3)   selama (tidak ketemu) dan (i <= N) kerjakan baris 4
(4)   jika (Data[i] = x) maka ketemu ← true, jika tidak i ← i + 1
(5)   jika (ketemu) maka i adalah indeks dari data yang dicari, jika data tidak ditemukan.
Contoh
#include <stdio.h>
#include <conio.h>
void main()
{
  int data[8] = {8,10,6,-2,11,7,1,100};
  int cari;
  int flag=0;
  printf(“masukkan data yang ingin dicari = “);scanf(“%d”,&cari);
  for(int i=0;i<8;i++)
 {
   if(data[i] == cari) flag=1;
  }
  if(flag==1) printf(“Data ada!\n”);
  else printf(“Data tidak ada!\n”);
  getch();
  return 1;
}

Dari program di atas, terlihat bahwa dilakukan perulangan untuk mengakses semua elemen array data satu per satu berdasarkan indeksnya.
a)      Program menggunakan sebuah variable flag yang berguna untuk menandai ada atau tidaknya data yang dicari dalam array data. Hanya bernilai 1 atau 0.
b)      Flag pertama kali diinisialisasi dengan nilai 0.
c)      Jika ditemukan, maka flag akan diset menjadi 1, jika tidak ada maka flag akan tetap bernilai 0.
d)     Semua elemen array data akan dibandingkan satu per satu dengan data yang dicari dan diinputkan oleh user.
2. Pencarian Beruntun dengan sentinel
Konsep
a)      Pencarian bertujuan untuk menambahkan elemen baru setelah elemen terakhir larik, maka terdapat sebuah varian dari metode pencarian berurutan. NIlai x yang akan dicari sengaja ditambahkan terlebih dahulu. Data yang ditambahkan setelah elemen larik ini disebut dengan sentinel.
b)      Perhatikan array berikut ini:

0	1	2	3	4	5	6	indeks
3	12	9	-4	21	6
ffea	ffeb	ffec	ffed	ffef	fffa	fffb	alamat

(1)   Terdapat enam buah data dalam array (dari indeks 0 s.d. lima dan terdapat 1 indeks array tambahan (indeks ke 6) yang belum berisi data (disebut sentinel)
(2)   Array pada indeks ke-6 berguna untuk menjaga agar indeks data berada pada indeks 0 s.d. 5 saja. Nila pencarian data sudah
mencapai array indeks yang ke-6 maka berarti data TIDAK ADA, sedangkan jika pencarian tidak mencapai indeks ke-6, maka data ADA.
Algoritma
Procedure SeqSearchWithSentinel(input L: LarikInt, input n: integer, input x: integer, output idx: integer)
DEKLARASI
     I: integer
ALGORITMA
L[n+1]  ← X   {sentinel}
I ← 1
While (L[i] ≠ x) do
I ← i+1
Endwhile
If idx = n+1 then
idx  ← -1
else
idx ← 1
endif
Contoh
#include <stdio.h>
#include <conio.h>
void 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;
}
3. Pencarian Bagi Dua (Binary Search)
Konsep
(a)    Merupakan metode pencarian pada data terurut yang paling efisien.
(b)   Metode ini digunakan untuk kebutuhan pencarian dengan waktu yang cepat.
(c)    Prinsip pencarian dengan membagi data atas dua bagian mengilhami metode ini. data yang disimpan didalam larik harus sudah terurut.
Algoritma
Algoritma pencarian biner dapat dituliskan sebagai berikut:
(a)    L ← 0
(b)   R ← N – 1
(c)    Ketemu ← false
(d)   Selama (L <= R) dan (tidak ketemu) kerjakan baris 5 sampai dengan 8
(e)    m ← (L + R) / 283
(f)    jika (Data[m]) maka ketemu ← true
(g)   jika (x < Data[m]) maka R ← m – 1
(h)   jika (x > Data[m]) maka L ← m + 1
(i)     jika (ketemu) maka m adalah indeks dari data yang dicari, jika tidak maka data tidak ditemukan.
Contoh
int binary_search(int cari)
{
 int l,r,m;
  l = 0;
  r = n-1;
  int ktm = 0;
  while(l<=r && ktm==0)
 {
   m = (l+r)/2;
   if(data[m] == cari) ktm=1;
   else if (cari < data[m]) r=m-1;
   else l=m+1;
  {
    if(ktm==1) return 1; else return 0;
   }
  }
}


Sumber Referensi :

http://hadiahdi.wordpress.com/2012/05/11/algoritma-searching/ 

Macam-macam algoritma sorting

Bubble Sort

Bubble sort merupakan algoritma sorting sederhana. Algoritma ini dimulai pada awal set data. Ia membandingkan dua elemen pertama, dan jika yang pertama adalah lebih besar dari yang kedua, maka swap mereka. Terus melakukan hal ini untuk setiap pasangan elemen berdekatan dengan akhir kumpulan data. Ia kemudian mulai lagi dengan dua elemen pertama, mengulang sampai tidak ada swap telah terjadi pada lulus terakhir. Rata-rata Algoritma dan kinerja kasus terburuk adalah O (n2), sehingga jarang digunakan untuk menyortir besar, unordered, set data. Gelembung sort dapat digunakan untuk mengurutkan sejumlah kecil item (dimana inefisiensi adalah bukan hukuman tinggi). Gelembung sort juga dapat secara efisien digunakan pada daftar yang sudah diurutkan kecuali untuk jumlah yang sangat kecil elemen. Misalnya, jika hanya satu unsur yang tidak sesuai, bubble sort hanya akan memakan waktu 2n. Jika dua unsur yang

tidak sesuai, bubble sort hanya akan mengambil paling banyak 3n waktu.

Gelembung sort rata-rata kasus dan kasus terburuk keduanya O (n ²).

Selection Sort

Semacam Seleksi adalah semacam perbandingan di tempat. Ini memiliki O (n2) kompleksitas, sehingga tidak efisien dalam daftar besar, dan umumnya melakukan lebih buruk dari insertion sort serupa. Seleksi semacam terkenal karena kesederhanaan, dan juga memiliki keunggulan kinerja lebih algoritma yang lebih rumit dalam situasi tertentu. Algoritma mencari nilai minimum, swap dengan nilai di posisi pertama, dan mengulangi langkah-langkah untuk sisa daftar. Itu tidak lebih dari swap n, dan dengan demikian berguna dimana swapping sangat mahal.

Insertion Sort

Insertion sort merupakan algoritma sorting sederhana yang relatif efisien untuk daftar kecil dan sebagian besar daftar-disortir, dan sering digunakan sebagai bagian dari algoritma yang lebih canggih. Ia bekerja dengan mengambil unsur-unsur dari satu daftar dengan satu dan memasukkan mereka dalam posisi yang benar mereka ke dalam daftar diurutkan baru. Pada array, daftar baru dan elemen-elemen yang tersisa dapat berbagi ruang array, tetapi penyisipan mahal, membutuhkan menggeser semua elemen-elemen berikut alih oleh satu. Shell sort (lihat di bawah) adalah varian dari insertion sort yang lebih efisien untuk daftar yang lebih besar.

Shell Sort

Shell sort diciptakan oleh Donald Shell pada tahun 1959. Ini meningkatkan atas bubble sort dan insertion sort dengan menggerakkan keluar dari elemen-elemen memesan lebih dari satu posisi pada suatu waktu. Salah satu implementasi dapat digambarkan sebagai mengatur urutan data dalam array dua dimensi dan kemudian menyortir kolom dari array menggunakan insertion sort.

 Comb Sort

Comb Sort adalah semacam algoritma sorting yang relatif sederhana awalnya dirancang oleh Wlodzimierz Dobosiewicz pada tahun 1980. Kemudian ditemukan kembali dan dipopulerkan oleh Stephen Lacey dan Richard Box dengan sebuah artikel majalah Byte diterbitkan pada bulan April 1991. Sisir semacam meningkatkan pada bubble sort, dan algoritma saingan seperti Quicksort. Ide dasarnya adalah untuk menghilangkan kura-kura, atau nilai kecil dekat akhir daftar, karena dalam semacam gelembung menyortir ini sangat melambat. (Kelinci, nilai besar sekitar awal daftar, tidak menimbulkan masalah di bubble sort.).

Merge Sort

Merge sort mengambil keuntungan dari kemudahan penggabungan sudah daftar diurutkan ke daftar diurutkan baru. Dimulai dengan membandingkan setiap dua elemen (yaitu, 1 dengan 2, kemudian 3 dengan 4 ...) dan swapping mereka jika yang pertama datang setelah kedua. Kemudian masing-masing menggabungkan daftar yang dihasilkan dua menjadi daftar empat, kemudian menggabungkan daftar tersebut empat, dan seterusnya, sampai akhirnya dua daftar digabungkan ke dalam daftar diurutkan akhir. Dari algoritma yang dijelaskan di sini, ini adalah yang pertama yang baik daftar skala yang sangat besar, karena kasus terburuk running time adalah O (n log n). Merge sort telah melihat lonjakan yang relatif baru dalam popularitas untuk implementasi praktis, yang digunakan untuk rutin semacam standar dalam bahasa pemrograman Perl, [5] Python (sebagai timsort [6]), dan Jawa (juga menggunakan timsort per JDK7 [7 ]), antara lain. Merge sort telah digunakan di Jawa setidaknya sejak 2000 di JDK1.3.

Heap Sort

Heapsort adalah versi yang jauh lebih efisien selection sort. Ia juga bekerja dengan menentukan elemen (atau terkecil) terbesar daftar, menempatkan bahwa pada akhir (atau awal) dari daftar, kemudian melanjutkan dengan sisa daftar, tapi menyelesaikan tugas ini secara efisien dengan menggunakan struktur data yang disebut tumpukan, tipe khusus pohon biner. Setelah daftar data telah dibuat menjadi tumpukan, simpul akar dijamin menjadi unsur (atau terkecil) terbesar. Ketika dipindahkan dan ditempatkan di akhir daftar, tumpukan adalah ulang sehingga elemen terbesar yang tersisa bergerak ke akar. Menggunakan heap, menemukan elemen terbesar berikutnya membutuhkan O (log n) waktu, bukan O (n) untuk linear scan di selection sort sederhana. Hal ini memungkinkan heapsort untuk menjalankan dalam O (n log n) waktu, dan ini juga merupakan kompleksitas kasus terburuk.

Quick Sort

Quicksort adalah membagi dan menaklukkan algoritma yang mengandalkan operasi partisi: untuk partisi array, kita memilih sebuah elemen, yang disebut pivot, memindahkan semua unsur kecil sebelum poros, dan memindahkan semua elemen yang lebih besar setelah itu. Hal ini dapat dilakukan secara efisien dalam waktu linier dan di tempat. Kami kemudian secara rekursif mengurutkan sublists lebih kecil dan lebih besar. Implementasi Efisien quickSort (dengan partisi di-tempat) biasanya macam stabil dan agak rumit, tetapi adalah salah satu dari algoritma pengurutan tercepat dalam praktek. Bersama dengan sederhana O (log n) penggunaan ruang, ini membuat salah satu quickSort dari algoritma pengurutan yang paling populer, tersedia di perpustakaan banyak standar. Isu paling kompleks di quickSort adalah memilih elemen pivot yang baik; konsisten pilihan yang buruk pivots dapat mengakibatkan drastis lambat O (n ²) kinerja, tetapi jika di setiap langkah kita memilih median sebagai pivot maka ia bekerja dalam O (n log n ). Menemukan median, bagaimanapun, adalah O (n) operasi pada daftar unsorted, dan karena itu menuntut hukuman sendiri.

Counting Sort

Counting Sort berlaku jika setiap masukan diketahui milik set tertentu, S, kemungkinan. Algoritma ini berjalan di O (| S | + n) dan O (| S |) memori di mana n adalah panjang dari input. Ia bekerja dengan membuat sebuah array integer ukuran | S | dan menggunakan bin i untuk menghitung kejadian anggota i S dalam masukan. Setiap masukan kemudian dihitung oleh incrementing nilai bin terkait. Setelah itu, array menghitung adalah dilingkarkan melalui untuk mengatur semua masukan dalam rangka. Algoritma sorting ini tidak bisa sering digunakan karena S harus cukup kecil agar bisa efisien, namun algoritma ini sangat cepat dan menunjukkan perilaku asimtotik besar sebagai meningkat n. Hal ini juga dapat dimodifikasi untuk menyediakan perilaku yang stabil.

Bucket Sort

Bucket sort adalah membagi dan menaklukkan algoritma sorting yang generalizes Counting mengurutkan berdasarkan partisi array ke dalam jumlah terbatas ember. Setiap ember kemudian diurutkan secara individual, baik menggunakan algoritma sorting yang berbeda, atau dengan rekursif menerapkan algoritma sorting ember. Sebuah variasi dari metode ini disebut semacam hitungan satu buffer lebih cepat daripada quickSort dan memakan waktu sekitar waktu yang sama untuk berjalan di setiap set data. Karena kenyataan bahwa semacam ember harus menggunakan sejumlah ember yang terbaik adalah cocok untuk digunakan pada set data lingkup terbatas. Bucket sort akan cocok untuk data seperti nomor jaminan sosial - yang memiliki banyak variasi.

Radix Sort

Radix sort adalah sebuah algoritma yang macam angka dengan digit individu pengolahan. n digit angka yang terdiri dari masing-masing k diurutkan dalam waktu O (n ° K). Radix sort bisa proses digit setiap angka mulai dari angka signifikan paling sedikit (LSD) atau digit yang paling signifikan (MSD). Hasil uji BNT macam algoritma pertama daftar dengan paling signifikan angka sambil menjaga agar relatif mereka menggunakan semacam stabil. Kemudian macam mereka dengan angka berikutnya, dan seterusnya dari paling signifikan yang paling signifikan, berakhir dengan sebuah daftar diurutkan. Sedangkan jenis LSD radix memerlukan penggunaan semacam stabil, MSD algoritma radix sort tidak (kecuali sorting yang stabil yang diinginkan). Di tempat semacam MSD radix tidak stabil. Adalah umum untuk algoritma semacam menghitung untuk digunakan secara internal oleh jenis radix. Hybrid pemilahan pendekatan, seperti menggunakan insertion sort sampah kecil untuk meningkatkan kinerja semacam radix signifikan.

Distribution Sort

Distribution Sort mengacu pada setiap algoritma sorting dimana data didistribusikan dari input untuk struktur antara beberapa yang kemudian dikumpulkan dan ditempatkan pada output. Lihat Bucket sort.

Tim Sort

Distribusi semacam mengacu pada setiap algoritma sorting dimana data didistribusikan dari input untuk struktur antara beberapa yang kemudian dikumpulkan dan ditempatkan pada output. Lihat Bucket sort.


Sumber Referensi :

http://suebzains.blogspot.com/2012/05/macam-macam-sorting.html

ARRAY

Array adalah sekelompok data sejenis yang disimpan ke dalam variabel dengan nama yang sama, dengan memberi indeks pada variabel untuk membedakan antara yang satu dengan yang lain.

VARIABEL ARRAY

            nama_variabel[indeks]

ketentuan nama variabel arrray sama dengan nama variabel biasa.

indeks menunjukkan nomor dari variabel .

DEKLARASI VARIABEL ARRAY

BU                  : tipe nama_variabel[indeks];

Contoh           : float bil[10];

            deklarasi variabel array dengan nama bil yang akan menampung 10 data            yang  bertipe  float.  Indeks  10  menunjukkan  variabel  bil  terdiri  dari  10 elemen, dimana setiap elemen akan menampung sebuah data.

Indeks array dimulai dari nol(0) , sedang nomor elemen biasanya dimulai dari satu(1). Nomor elemen dapat dibuat sama dengan nomor indeks untuk mempermudah pembuatan program yaitu dengan memberi indeks satu lebih banyak dari jumlah data yang dibutuhkan, sehingga menjadi :

            float bil[11]

INISIALISASI  ARRAY 1 DIMENSI

Inisialisasi  dapat dilakukan bersama dengan deklarasi atau tersendiri. Inisialisasi suatu array adalah dengan meletakkan elemen array di antara tanda kurung kurawal {}, antara elemen yang satu dengan lainnya dipisahkan koma.

            int bil[2] = {4,1,8}

            bil[0] = 4

            bil[1] = 1

            bil[2] = 8

AUTOMATIC ARRAY adalah Inisialisasi array dilakukan di dalam fungsi tertentu. Hanya  compiler C yang berstandar ANSI C yang dapat menginisialisasikan automatic array.

Cara menginisialisasikan  array dari compiler yg tidak mengikuti standar  ANSI C:

1. Diinisialisasikan di luar fungsi sebagai variabel GLOBAL/EXTERNAL ARRAY.

            int bil[2]={0,0,0};

            main()

           

2. Diinisialisasikan didlm fungsi sebagai variabel LOKAL/STATIC ARRAY.

            main()

            {

                        static int bil[2]={0,0,0};

                        .........

Pada automatic array yang tidak diinisialisasikan , elemen array akan memiliki nilai yang tidak beraturan. Bila global & static array tidak diinisialisasi maka semua elemen array secara otomatis akan diberi nilai nol(0).

Contoh :

main()

{

            int y;

            int hitung=0;

            int x[0];

            for(y=0;y<5;y++)

            {

                        hitung+=y;

                        x[y]=hitung;

                        printf("%3d - %3d\n",y,x[y]);

            }

}

OUTPUT:

0-  0

1-  1

2-  3

3-  6

4-  10

MENDEFINISIKAN JUMLAH ELEMEN ARRAY DALAM VARIABEL

Besarnya variabel indeks dapat ditentukan dengan menggunakan

preprocessor directives #define

#define N 40

main()

{

            int no[N],gaji[N],gol[N],status[N],juman[N];

Bila besari indeks akan diubah menjadi 50, cukup diganti dengan

#define N 50

ARRAY 2 DIMENSI

            nama_variabel [indeks1][indeks2]

indeks1          : jumlah/nomor baris

indeks2          : jumlah/nomor kolom

Jumlah elemen yang dimiliki array 2 dimensi dapat ditentukan dari hasil perkalian         indeks1 * indeks2

misal : array A[2][3] akan memiliki 2*3 = 6 elemen.

main()

{

            float  bil [5] [5]

            .......

dapat dituliskan dengan #define

#define N 5

main()

{

            float bil [N]  [N]

            .......

INISIALISASI ARRAY 2 DIMENSI

main()

{

            float bil[2] [3] =

            { { 1,2,3},         /*baris 0*/

              { 4,5,6},         /*baris 1*/

            }

elemen bil [0] [0] = 1

elemen bil [0] [1] = 2

elemen bil [0] [2] = 3

elemen bil [1] [0] = 4

elemen bil [1] [1] = 5

elemen bil [1] [2] = 6

Contoh :

main()

{

            int x[3][5];

            int y,z;

            int hitung=0;

            for(y=0;y<3;y++)

            {

                        printf("y = %d\n",y);

                        for(z=0;z<5;z++)

                        {

                                    hitung+=z;

                                    x[y][z] = hitung;

                                    printf("%/t%3d - %3d\n",z,x[y][z]);

                        }

            }

}

OUTPUT:

y = 0

   0-  0

   1-  1

   2-  2

   3-  6

   4-  10

y = 1

   0-  10

   1-  11

   2-  13

   3-  16

   4-  20

y = 2

  0-  20

  1-  21

  2-  23

  3-  26

  4-  30

STRING dan ARRAY

1. Pada string   terdapat karakter null(\0) di akhir string

2. String sudah pasti array, array belum tentu string

CONTOH - CONTOH :

1. array dengan pengisian input melalui keyboard

            baca_input()

            {

                        float nilai[10];

                        for(i=0;i<10;i++)

                        scanf("%d",&nilai[i]);

            }

2. Fungsi yang mencetak isi array dari akhir ke awal

            cetak_array()

            {

                        float nilai[10];

                        for(i=9;i>=0;i--)

                        scanf("%3f",nilai[i]);

            }

3. Menghitung rata - rata isi array nilai

            rata_rata()

            {

                        float nilai[10],jum*rata;

                        for(i=0,jum=0;i<=9;i++)

                                    jum+=nilai[i];

                                    rata=jum/i;

            }

4. Mencari nilai terbesar

            besar()

            float temp,nilai[10];

            {

                        for(temp=nilai[0],i=1;i<=9;i++)

                        if(nilai[i] > temp)

                                    temp=nilai[i];

            }

            return(temp)

 


Array 1 Dimensi

#include <iostream.h>
#include <conio.h>

int data[10];
int n,total;

void main()
{
cout<<"===PROGRAM INPUTAN DATA DARI USER==="<<endl;
cout<<endl;
cout<<"Masukan Jumlah Data (Max 10): ";
cin>>n;
cout<<endl;
if(n<=10)
{
for(int i=1;i<=n;i++)
{
cout<<"Masukkan data ke "<<i<< " : ";
cin>>data[i];
total=total+data[i];
}
cout<<endl;
cout<<"Data yang di Masukan: ";
for(int i=1; i<=n; i++)
{
cout<<" "<<data[i];
}
cout<<endl;
cout<<"Jumlah seluruh data: "<<total;
}
else
cout<<"Inputan Tidak Sesuai";
getch();
}

Tampilannya:


Array 2 Dimensi
#include <iostream.h>
#include <conio.h>

int main()
{
int matrikA[3][4] = {7,6,9,3,5,7,4,2,7,9,2,2};
int matrikB[3][4] = {{3,6,8,6},{7,3,9,1},{8,5,9,4}};
int matrikC[3][4];
int i, j;
//penjumlahan matriks
for (i=0; i<3; i++)
{
for (j=0; j<4; j++)
{
matrikC[i][j] = matrikA[i][j] + matrikB[i][j];
}
}
//menampilkan data masing-masing matriks
cout << "\nData Matriks A : \n";
cout << "================ \n";
for (i=0; i<3; i++)
{
for (j=0; j<4; j++)
cout << matrikA[i][j] << " ";
cout << "\n";
}
cout << "\nData Matriks B : \n";
cout << "================ \n";
for (i=0; i<3; i++)
{
for (j=0; j<4; j++)
cout << matrikB[i][j] << " ";
cout << "\n";
}
cout << "\nData Matriks C = Matriks A + Matriks B : \n";
cout << "======================================== \n";
for (i=0; i<3; i++)
{
for (j=0; j<4; j++)
cout << matrikC[i][j] << " ";
cout << "\n";
}
getch();
return 0;
}

Tampilannya:



Sumber Referensi:
http://www.google.com/url?q=http://wsilfi.staff.gunadarma.ac.id/Downloads/files/1378/BhsC_Array.DOC&sa=U&ei=2PUkUciuGcW4rAfluIDIAg&ved=0CDEQFjAG&sig2=gKqJTR2_uKhPww8YBRUXVA&usg=AFQjCNEBqPdXk4KoldhW3qrYrhsZtVXLew