Bubble dan Insertion Sort (Algoritma dan Flowchart)

BUBBLE SORT

Proses dari bubble sort ini menggunakan 2 kalang , kalang pertama melakukan pengulangan dari elemen ke-2 sampai dengan elemen ke N-1 (misalnya variable a ), sedangkan kalang kedua melakukan pengulangan menurun dari elemen ke N sampai elemen ke a (misalkan variable b). pada setiap pengulangan , elemen ke b-1 dibandingkan dengan elemen ke b . apabila data ke b-1 lebih besar daripada data ke b-1, dilakukan penukaran .

   

   Algoritma :

1.      Dilakukan pembandingan setiap pasangan elemen yang berdekatan , misalnya pada elemen pertama dan kedua .

2.      jika nilai pertama lebih besar daripada nilai kedua maka dilakukan penukaran .

3.      Periksa elemen selanjutnya .

4.      Apakah nilainya sudah lebih kecil atau masih lebih besar . jika masih lebih besar maka akan tetap dan dilanjutkan pemeriksaan elemen lain .

5.      Ulangi langkah tersebut setidaknya satu sudah melakukan satu kali pertukaran .

6.      Sampai semua elemen urut sesuai urutan.

Flowchart :

INSERTION SORT

Insertion sort adalah sebuah algoritma pengurutan yang membandingkan dua elemen data pertama, mengurutkannya, kemudian mengecek elemen data berikutnya satu persatu dan membandingkannya dengan elemen data yang telah diurutkan. Karena algoritma ini bekerja dengan membandingkan elemen-elemen data yang akan diurutkan, algoritma ini termasuk pula dalam comparison-based sort. Ide dasar dari algoritma Insertion Sort ini adalah mencari tempat yang "tepat" untuk setiap elemen array, dengan cara sequential search. Proses ini kemudian menyisipkan sebuah elemen array yang diproses ke tempatnya ang seharusnya.

Algoritma :

1.      Langkah pertama mencari data yang paling terkecil dari data awal sampai akhir.

2.      Data yang paling kecil ditukar ke data pertama .

3.      Sehingga data pertama menjadi data yang paling kecil.

4.      Data terkecil dicari mulai dari data kedua sampai data terakhir .

5.      Data kecil yang diperoleh maka akan ditukar dengan data kedua .

6.      Kemudian seterusnya hingga semua data menjadi urut .

Flowchart :

Pencarian Interpolasi (interpolation searching)

Pencarian Interpolasi (interpolation searching)

Proses pencarian interpolasi (interpolation search) hampir sama dengan proses pencarian dibinary search, dimana pencarian juga dilakukan pada kumpulan data yang sudah urut. Akan tetapi jika pada binary search data dibagi menjadi dua bagian tiap prosesnya. Contoh pencarian dengan metode ini misalnya pencarian nomer telpon pada daftar phonebook. Misalnya nama data yang dicari berawalan huruf F, maka pencariannya tidak akan dilakukan dari awal, namun langsung membuka 2/3 atau 3/4 dari tebal buku. Jadi, data yang dicari relatif terhadap jumlah data.

Secara umum jika dirumuskan, posisi kunci pencarian interpolasi relatif ini adalah:

– Jika data[posisi] > data yg dicari, high = pos – 1
– Jika data[posisi] < data yg dicari, high = pos + 1

Teknik ini dilakukan pada data yang sudah terurut berdasarkan kunci tertentu yang
dilakukan dengan perkiraan letak data.

Algoritma

 

Flowchart 

 

Program pencarian interpolasi

#include <iostream> 
#include <conio.h> 
#include <iomanip>
 
using namespace std; 
int main() 
{ 
    int data[7], x;
    int cari_data, posisi, awal, akhir, proses;
    bool berhenti = false;
   
    cout<<"Masukkan Data =\n";
    for (x=0; x<7; x++)
    {
        cin>>data[x];
    }
   
    cout<<"Data: ";
    for(int x = 0; x<7; x++)
    cout<<setw(3)<<data[x];
    cout<<endl<<endl;

    cout << "Data Yang ingin dicari : ";
    cin >> cari_data;
   
    awal = 0;
    akhir = 6;
    proses = 0;
    while(berhenti != true)
     {
      proses++;
      posisi = (((cari_data-data[awal])*(akhir-awal))/(data[akhir]-data[awal])+awal);
      if(data[posisi] == cari_data) {
         cout << "Data " << cari_data << " pada posisi " << posisi <<endl;
         cout << "Proses pencaharian sebanyak " << proses <<endl;
         berhenti = true;
         }
   
      else if(data[posisi] < cari_data) {
          awal = posisi + 1;
          }
        
       else { 
         cout << "Data " << cari_data << " Tidak ditemukan.\n";
         berhenti = true;
           }
    }

getch(); 
return 0; 
}  

output