Skip to content Skip to sidebar Skip to footer
Home / Pengertian dan Contoh dari Teknik Sorting dan Teknik Searching (Beserta Program dalam C++)

Pengertian dan Contoh dari Teknik Sorting dan Teknik Searching (Beserta Program dalam C++)

Assalammu‘alaikum wr. wb.

Hello guys, Kembali lagi bersama Inzaghi's Blog! Jika kalian belajar Algoritma Pemrograman, pastinya yang kamu pelajari adalah Teknik Sorting dan Teknik Searching. Kali ini saya akan membahasnya lebih lanjut.



TEKNIK SORTING


Salah satu bagian penting dari struktur data adalah proses pengurutan data. Data terkadang akan berada dalam bentuk yang tidak berpola ataupun dengan pola tertentu yang tidak kita inginkan. Namun dalam penggunaannya, kita akan selalu ingin menggunakan data tersebut dalam bentuk yang rapi atau berpola sesuai dengan yang kita inginkan. Maka dari itu proses sorting adalah proses yang sangat penting dalam struktur data. Proses pengurutan banyak ditemukan dalam pemrosesan komputer. Data yang sudah terurut memiliki beberapa keuntungan. Selain mempercepat pencarian, data yang sudah terurut juga dapat dengan mudah menentukan Nilai terbesar atau terkecil.

Pengurutan data memang sangat relevan dan merupakan aktivitas yang sangat penting berkaitan dengan pemrosesan data. Bahkan pengurutan data telah banyak dilakukan dengan bantuan alat. Adanya kebutuhan terhadap peroses pengurutan memunculkan bermacam-macam metode pengurutan yang bertujuan untuk memperoleh metode pengurutan yang optimal.

1. Definisi Sorting

Pengurutan (sorting) adalah proses mengatur sekumpulan objek menurut urutan atau susunan tertentu. Urutan objek tersebut dapat menaik (ascending), yaitu urutan objek yang disusun mulai dari Nilai terkecil hingga terbesar atau menurun (descending), yaitu urutan objek yang disusun mulai dari Nilai terbesar hingga terkecil. Jika N buah objek atau data disimpan di dalam array Nilai, maka pengurutan menaik berarti menyusun elemen array sedemikian sehingga :

NILAI[0] ≤ NILAI[1] ≤ NILAI[2] ≤ … ≤ NILAI[N-1]

Sedangkan pengurutan menurun  berarti menyusun elemen array sedemikian sehingga :

NILAI[0] ≥ NILAI[1] ≥ … ≥ NILAI[N-1]

Data yang diurut dapat berupa data bertipe data dasar atau tipe data bentukan. Jika data bertipe bentukan (structure), maka harus disebutkan berdasarkan field apa data tersebut akan diurutkan.

Sama halnya dengan pencarian, pengurutan juga dibedakan menjadi 2 (Dua) Kelompok, yaitu :
  1. Pengurutan Internal, yaitu pengurutan terhadap sekumpulan data yang disimpan di dalam memori komputere. Umumnya struktur internal yang dipakai untuk pengurutan ini adalah array, sehingga pengurutan internal disebut dengan pengurutan array.
  2. Pengurutan Eksternal, yaitu pengurutan data yang disimpan di dalam memori sekunder. Biasanya data dengan berjumlah besar sehingga tidak mampu dimuat semuanya dalam memori komputer. Struktur eksternal yang dipakai adalah arsip (file), maka pengurutan ini juga sering disebut dengan pengurutan arsip.
Karena pengaksesan memori utama lebih cepat dari pada pengaksesan memori sekunder, maka pengurutan internal lebih cepat dibanding dengan pengurutan eksternal.

Beberapa metode yang dapat digunakan untuk pengurutan antara lain :
  1. Bubble Sort
  2. Selection Sort
  3. Quick Sort
  4. Merge Sort
  5. Heap Sort
  6. Shell Sort
  7. Radix Sort
  8. Tree Sort
  9. Maximum Sort
  10. Insertion Sort
Banyaknya metode pengurutan yang tersedia menimbulkan pertanyaan: algoritma manakah yang memiliki kinerja yang baik? Kinerja pengurutan data sangat menentukan kinerja sistem, karena itu pemilihan metode pengurutan yang cocok akan berperan dalam suatu aplikasi. Metode pengurutan yang akan dibahas adalah metode pengurutan Bubble Sort, Quick Sort, Maximum/Minimum Sort, Shell Sort, Merge Sort, dan Insertion.

2. Bubble Sort

Bubble Sort adalah metode yang membandingkan elemen yang sekarang dengan elemen-elemen berikutnya. Pembandingan elemen dapat dimulai dari awal atau mulai dari paling akhir. Apabila elemen yang sekarang lebih besar (untuk urut menaik) atau lebih kecil (untuk urut menaik) dari elemen berikutnya, maka posisinya ditukar, tetapi jika tidak maka posisinya tetap.

Contoh : Misalkan kita mempunyai array Nilai sebanyak 8 elemen akan diurutkan secara menaik dengan metode Bubble Sort 25, 72, 30, 45, 20, 15, 6, 50. Urutan langkah pengurutannya yang dimulai dari belakang seperti berikut.


Anda juga bisa memasukkan Programnya di sini secara bebas :

#include <iostream>
#include <conio.h>
using namespace std;

void prosesPerpindahan(int data[],int y){
    int x;
        for(x=0;x<y;x++){
        cout<<data[x]<<" ";
        }
    cout<<endl;
}

void prosesSorting(int data[],int y){
    int proses,x,tampung;
 
    for(proses=1;proses<y;proses++){
        for(x=0;x<y-proses;x++) {
            if(data[x]>data[x+1]){
                tampung=data[x];
                data[x]=data[x+1];
                data[x+1]=tampung;
            }
        }
    cout<<"Tahap Ke-"<<proses<<" : ";
    prosesPerpindahan(data,y);
    }
}

int main(){
    int Nilai[20];
    int i, N;
    cout<<"Masukkan Banyak Bilangan : ";
    cin>>N;
    for(i=0; i<N; i++){
        cout<<"Elemen ke-"<<i<<" : ";
        cin>>Nilai[i];
    }
    
    prosesSorting(Nilai,N);
    
    cout<<endl;
    cout<<"Setelah Di Urutkan dengan Bubble Sort : "<<endl;
    prosesPerpindahan(Nilai,N);
}

3. Quick Sort

Quick Sort merupakan metode tercepat dalam proses pengurutan data dengan menggunakan prinsip rekursif. Metode ini menggunakan strategi “pecah-belah” dengan mekanisme berikut ini.

Misalkan kita mempunyai array Nilai[k..l]. Array dipartisi menjadi dua bagian array kiri Nilai[k..m] dan array kanan Nilai[m+1..l]. Dasar mempartisi array menjadi dua adalah dengan mengambil elemen pertama sebagai elemen pivot. Letakkan semua elemen array yang lebih kecil dari pivot ke sebelah pivot dan semua elemen array yang lebih besar dari pivot ke sebelah kanan pivot. Elemen-elemen yang di sebelah kiri elemen pivot merupakan elemen-elemen array Nilai[k..m] sedangkan elemen-elemen array Nilai[m+2..l] adalah semua elemen yang lebih besar dari pivot. Lakukan hal yang sama seperti di atas terhadap array Nilai[k..m] dan Nilai[m+1..l] hingga tidak dapat dipartisi lagi.

Contoh : Misalkan kita mempunyai array Nilai sebanyak 8 elemen akan diurutkan secara menaik dengan metode Maximum Sort yaitu 25, 72, 30, 45, 20, 15, 6, 50. Urutan langkah pengurutannya seperti berikut dan programnya dapat dilihat pada program Lat_Sorting_02a.

1. Ambil elemen pertama sebagai elemen pivot, letakkan semua elemen array yang lebih kecil dari pivot ke sebelah kiri elemen pivot dan letakkan semua elemen array yang lebih besar dari pivot ke sebelah kanan elemen pivot.


2. Gunakan array Nilai[0..2]. Ambil elemen pertama sebagai elemen pivot, letakkan semua elemen array yang lebih kecil dari pivot ke sebelah kiri elemen pivot dan letakkan semua elemen array yang lebih besar dari pivot ke sebelah kanan elemen pivot.


Perhatikan array Nilai[2] tidak dapat lagi dipartisi maka berhenti sampai disana.

3. Gunakan array Nilai[0..1]. Ambil elemen pertama sebagai elemen pivot, letakkan semua elemen array yang lebih kecil dari pivot ke sebelah kiri elemen pivot dan letakkan semua elemen array yang lebih besar dari pivot ke sebelah kanan elemen pivot.


Perhatikan array Nilai[0] dan Nilai[1] tidak dapat lagi dipartisi maka berhenti sampai di sana.

4. Gunakan array Nilai[4..7]. Ambil elemen pertama sebagai elemen pivot, letakkan semua elemen array yang lebih kecil dari pivot ke sebelah kiri elemen pivot dan letakkan semua elemen array yang lebih besar dari pivot ke sebelah kanan elemen pivot.


5. Gunakan array Nilai[4..6]. Ambil elemen pertama sebagai elemen pivot, letakkan semua elemen array yang lebih kecil dari pivot ke sebelah kiri elemen pivot dan letakkan semua elemen array yang lebih besar dari pivot ke sebelah kanan elemen pivot.


6. Gunakan array Nilai[5..6]. Ambil elemen pertama sebagai elemen pivot, letakkan semua elemen array yang lebih kecil dari pivot ke sebelah kiri elemen pivot dan letakkan semua elemen array yang lebih besar dari pivot ke sebelah kanan elemen pivot.


Karena semua elemen array sudah tidak dapat dipartisi maka proses pengurutan berakhir dan hasilnya diperoleh seperti berikut (Gabungkan mulai Nilai[0] hingga Nilai[7]) :


Untuk melakukan proses pengurutan data secara menurun dengan metode Quick Sort dilakukan dengan meletakkan semua elemen array yang lebih kecil dari pivot ke sebelah kanan pivot dan semua elemen array yang lebih besar dari pivot ke sebelah kiri pivot.

Untuk menjalankan Program, bisa memasukkan nilainya secara bebas di bawah ini :

#include <iostream>
#include <conio.h>
#include <iomanip>
#include <iostream>
#include <conio.h>
#include <iomanip>
using namespace std;

void Cetak(int data[], int n){
    int i;
    for(i=0; i<n; i++)
        cout<<setw(3)<<data[i];
    cout<<"\n";
}

int Partisi(int data[], int p, int r){
    int x, i, j, temp;
    x = data[p];
    i=p;
    j=r;
    while(1){
        while(data[j]>x)
        j--;
        while(data[i]<x)
        i++;
        if(i<j){
            temp = data[i];
            data[i] = data[j];
            data[j] = temp;
        }
        else
            return j;
    }
}

void Quick_Sort(int data[], int p, int r){
    int q;
    if(p<r){
        q=Partisi(data, p, r+1);
        Quick_Sort(data, p, 1);
        Quick_Sort(data, q+1, r);
    }
}

int main(){
    int Nilai[20];
    int i, N;
    cout<<"Program Quick Sort         "<<endl;
    cout<<"                           "<<endl;
    cout<<"Masukkan Banyak Bilangan : ";
    cin>>N;
    for(i=0; i<N; i++){
        cout<<"Elemen ke-"<<i<<" : ";
        cin>>Nilai[i];
    }
    cout<<"Data Sebelum di urut : ";
    Cetak(Nilai, N);
    cout<<endl;
    Quick_Sort(Nilai, 0, N-1);
    cout<<"Data Setelah di urut : ";
    Cetak(Nilai, N);
    getch();
}

4. Selection Sort

Kalau untuk metode selection sort ini, berbeda dengan bubble sort. Perbedaannya terletak pada dimana data terbesar berhenti. Metode selection sort, data 1 pertama akan di bandingkan dengan data kedua, apabila data tersebut bernilai lebih besar di banding data pertama. Maka, data tersebut akan bergeser dan akan berhenti hingga data n+1 lebih besar dari data tersebut.

Contohnya ada pada Gambar berikut ini.


Untuk Selection Sort, bisa juga memasukkan Programnya di sini secara bebas :

#include <iostream>
using namespace std;
 
int main(){
    int Nilai[20];
    int i,j,x,N,posisi,tampung;
    
    cout<<"Masukkan Banyak Bilangan : ";
    cin>>N;
    for(i=0; i<N; i++){
        cout<<"Elemen ke-"<<i<<" : ";
        cin>>Nilai[i];
    }
    
    cout<<"Sebelum Di Urutkan : ";
        for (int i=0; i<N; i++){
            cout<<Nilai[i]<<" ";
        }
    
    cout<<endl;
    cout<<endl;
    
    for (int i=0;i<N-1;++i){
        posisi=i;
        for (int j=i+1;j<N;++j){
            if (Nilai[j]<Nilai[posisi]){
                posisi=j;   
            }
        }
    
        if (posisi!=i){
                tampung=Nilai[posisi];
            Nilai[posisi]=Nilai[i];
            Nilai[i]=tampung;
         }
        
        cout<<"Tahap Ke-"<<i+1<<" : ";
            for (int x=0;x<N;++x){
                cout<<Nilai[x]<<" ";
            }
            cout<<endl;
    }
    cout<<endl;
  
    cout<<"Setelah Di Urutkan Menggunakan Metode Selection Sort : ";
    for (int i=0;i<N;++i){
        cout<<Nilai[i]<<" ";
    }
}

5. Metode Insertion Sort

Metode Insertion Sort merupakan metode pengurutan dengan cara menyisipkan elemen array pada posisi yang tepat. Pencarian yang tepat dilakukan dengan melakukan pencarian beruntun di dalam array. Selama pencarian posisi yang tepat dilakukan pergeseran elemen array. Algoritma pengurutan ini tepat untuk persoalan menyisipkan elemen baru ke dalam array yang sudah terurut. Misalnya dalam permainan kartu, kartu yang dicabut biasanya disisipkan oleh pemain pada posisi yang tepat sehingga penambahan kartu tersebut membuat semua kartu tetap terurut.

Misalkan kita memiliki suatu array dengan N maka pengurutan secara menaik dengan metode Insertion Sort sebagai berikut :

Langkah -1 : Elemen pertama Nilai[0] diasumsikan telah sesuai tempatnya.

Langkah -2 : Ambil elemen ke dua (Nilai[1]), cari lokasi yang tepat pada Nilai[0..0] untuk Nilai Nilai[1]. Lakukan pergeseran ke kanan jika Nilai[0..1] lebih besar (untuk urut menaik) atau lebih kecil (untuk urut menurun) dari Nilai[1]. Misalnya posisi yang tepat adalah j, maka sisipkanlah Nilai[1] pada Nilai[j].

Langkah -3 : Ambil elemen ke tiga (Nilai[2]), cari lokasi yang tepat pada Nilai[0..1] untuk Nilai[2]. Lakukan pergeseran ke kanan jika Nilai[0..2] lebih besar (untuk urut menaik) atau lebih kecil (untuk urut menurun) dari Nilai[2]. Misalnya posisi yang tepat adalah j, maka sisipkanlah Nilai[2] pada Nilai[j].

Langkah -4 : Ambil elemen ke empat (Nilai[3]), cari lokasi yang tepat pada Nilai[0..3] untuk Nilai Nilai[3]. Lakukan pergeseran ke kanan jika Nilai[0..2] lebih besar (untuk urut menaik) atau lebih kecil (untuk urut menurun) dari Nilai[3]. Misalnya posisi yang tepat adalah j, maka sisipkanlah Nilai[3] pada Nilai[j].

…

Langkah –N : Ambil elemen ke N (Nilai[N]), cari lokasi yang tepat pada Nilai[0..N-1] untuk Nilai Nilai[N]. Lakukan pergeseran ke kanan jika Nilai[0..N-1] lebih besar (untuk urut menaik) atau lebih kecil (untuk urut menurun) dari Nilai[N]. Misalnya posisi yang tepat adalah j, maka sisipkanlah Nilai[N] pada Nilai[j].

Contoh : Misalkan kita mempunyai array Nilai sebanyak 8 elemen akan diurutkan secara menaik dengan metode Insertion Sort: 25, 72, 30, 45, 20, 15, 6, 50. Urutan langkah pengurutannya seperti berikut:

Langkah-1 : Nilai[0] diasumsikan telah terurut.


Langkah-2 : Cari lokasi yang tepat untuk Nilai[1] pada Nilai[0..0]. Dalam hal ini, ternyata 72 tidak lebih besasr dari 25 maka tidak terjadi pergeseran, sehingga diperoleh array seperti berikut :


Langkah-3 : Cari lokasi yang tepat untuk Nilai[2] pada Nilai[0..1]. Dalam hal ini, ternyata lokasi yang tepat adalah 1, maka Nilai[1] digeser ke kanan sehingga Nilai[2] di posisi ke 1, sehingga diperoleh array sebagai berikut :


Langkah-4 : Cari lokasi yang tepat untuk Nilai[3] pada Nilai[0..2]. Dalam hal ini, ternyata lokasi yang tepat adalah 2, maka Nilai[2] digeser ke kanan sehingga Nilai[3] di posisi ke 3, sehingga diperoleh array seperti berikut :


Langkah-5 : Cari lokasi yang tepat untuk Nilai[4] pada Nilai[0..3]. Dalam hal ini, ternyata lokasi yang tepat adalah 0, maka Nilai[0], Nilai[1], Nilai[2], Nilai[3] digeser masing-masing satu posisi ke kanan sehingga Nilai[4] di posisi ke 0, sehingga array seperti berikut :


Langkah-6 : cari lokasi yang tepat untuk Nilai[5] pada Nilai[0..4]. Dalam hal ini, ternyata lokasi yang tepat adalah 0, maka Nilai[0], Nilai[1], Nilai[2], Nilai[3] dan Nilai[4] digeser masing-masing satu posisi ke kanan sehingga Nilai[6] di posisi ke 0, diperoleh array seperti berikut :


Langkah-7 : cari lokasi yang tepat untuk Nilai[6] pada Nilai[0..5]. Dalam hal ini, ternyata lokasi yang tepat adalah 0, maka Nilai[0], Nilai[1], Nilai[2], Nilai[3], Nilai[4] dan Nilai[5] digeser masing-masing satu posisi ke kanan sehingga Nilai[6] di posisi ke 0, diperoleh array seperti berikut :


Langkah-8 : cari lokasi yang tepat untuk Nilai[7] pada Nilai[0..6]. Dalam hal ini, ternyata lokasi yang tepat adalah 6, maka Nilai[6] digeser satu posisi ke kanan sehingga Nilai[7] di posisi ke 6, diperoleh array seperti berikut :


Untuk Insertion Sort, bisa juga memasukkan Programnya di sini secara bebas :

#include <iostream>
using namespace std;

int main(){
    int Nilai[20];
    int i, j, k, tampung, N;
    cout<<"Masukkan Banyak Bilangan : ";
    cin>>N;
    for(i=0; i<N; i++){
        cout<<"Elemen ke-"<<i<<" : ";
        cin>>Nilai[i];
    }
    cout<<endl;
    
    cout<<"Data Sebelum Di Urutkan :";
    for(i=0;i<N;i++){
        cout<<"  "<<Nilai[i];
    }
    cout<<endl;
    
    for(int i=1; i<N; i++){
        tampung = Nilai[i];
        j = i-1;
        while(j>=0 && Nilai[j] > tampung){
            Nilai[j+1] = Nilai[j];
            j--;
        }
        Nilai[j+1]=tampung;
        
        cout<<"Tahap Ke-"<<i<<" : ";
        for(k=0; k<N; k++){
            cout<<"  "<<Nilai[k];
        }
        cout<<endl;
    }
    cout<<"Setelah Di Urutkan dengan Insertion Sort : ";
    for(i=0;i<N;i++){
     cout<<"  "<<Nilai[i];
    }
}

6. Metode Shell Sort

Metode ini dinamakan sesuai dengan penciptanya, yaitu D.L. Shell. Metode ini mirip dengan metode Bubble Sort, hanya saja perbandingan dilakukan bukan antara dua bilangan yang berurutan, akan tetapi antara dua bilangan dengan jarak tertentu. Jarak ditentukan dengan N Div 2, dimana N adalah banyaknya elemen array. Lakukan pertukaran tempat jika setiap kali perbandingan dipenuhi (lebih besar untuk urut menaik dan lebih kecil untuk urut menurun). Setiap kali perbandingan terhadap keseluruhan elemen selesai dilakukan, maka perbandingan yang baru dilakukan kembali dimana jarak diperoleh dengan Jarak Div 2 (jarak diperoleh dari Nilai jarak sebelumnya). Perbandingan keseluruhan dilakukan sampai Nilai jarak sama dengan 1 (Satu). Pada saat jarak berNilai 1, maka metode Shell Sort sama dengan metode Bubble Sort.

Contoh : Misalkan kita mempunyai array Nilai sebanyak 8 elemen akan diurutkan secara menaik dengan metode Shell Sort yaitu 25, 72, 30, 45, 20, 15, 6, 59. Urutan langkah pengurutannya seperti berikut.

Untuk pertama kalinya Nilai jarak (K) = 8 div 2 = 4 dan kita buat suatu counter C=0. Kemudian proses perbandingan dilakukan berturut-turut antara Nilai[0] dengan Nilai[4], jika Nilai[0]>Nilai[4] maka lakukan pertukaran tempat dan jika tidak lanjutkan terhadap Nilai[1] dengan Nilai[5], jika Nilai[1]>Nilai[5] maka lakukan pertukaran tempat dan jika tidak lanjutkan terhadap Nilai[2] dengan Nilai[6], jika Nilai[2]>Nilai[6] maka lakukan pertukaran tempat dan jika tidak lanjutkan terhadap Nilai[3] dengan Nilai[7], jika Nilai[3]>Nilai[7] maka lakukan pertukaran tempat kemudian Nilai C=1.


Karena Nilai K masih sama dengan 4 dan Nilai C=1, maka lakukan kembali proses perbandingan dengan menghitung Nilai jarak (K) sama dengan 4 div 2 = 2 dan membuat Nilai C=0, sekarang proses perbandingan dilakukan berturut-turut antara Nilai[0] dengan Nilai[2], jika Nilai[0]>Nilai[2] maka lakukan pertukaran tempat dan jika tidak lanjutkan terhadap Nilai[1] dengan Nilai[3], jika Nilai[1]>Nilai[3] maka lakukan pertukaran tempat dan jika tidak lanjutkan terhadap Nilai[2] dengan Nilai[4], jika Nilai[2]>Nilai[4] maka lakukan pertukaran tempat dan jika tidak lanjutkan terhadap Nilai[3] dengan Nilai[5], jika Nilai[3]>Nilai[5] maka lakukan pertukaran dan jika tidak lanjutkan terhadap Nilai[4] dengan Nilai[6], jika Nilai[4]>Nilai[6] maka lakukan pertukaran dan jika tidak lanjutkan terhadap Nilai[5] dengan Nilai[7], jika Nilai[5]>Nilai[7] maka lakukan pertukaran tempat kemudian Nilai C=1.


Karena Nilai K masih sama dengan 2 dan Nilai C=1, maka lakukan kembali proses perbandingan dengan menghitung Nilai jarak(K) sama dengan 2 div 2 = 1 dan membuat Nilai C=0, sekarang proses perbandingan dilakukan berturut-turut antara Nilai[0] dengan Nilai[1], Nilai[1] dengan Nilai[2], Nilai[2] dengan Nilai[3], Nilai[3] dengan Nilai[4], Nilai[4] dengan Nilai[5], Nilai[5] dengan Nilai[6], dan Nilai[6]>Nilai[7], kemudian Nilai C=1 akan diperoleh hasil pertukaran setelah perbandingan seperti berikut.

6         15       20       25       45       30       50       72

Walaupun K telah berNilai sama dengan satu, tetapi Nilai C masih berNilai sama dengan 1 maka perbandingan harus diulang kembali dengan memberi Nilai C=0 dan Nilai K sama seperti sebelumnya yaitu sama dengan 1. Setelah dilakukan perbandingan maka hasilnya dapat diperoleh seperti berikut :

6         15       20       25       30       45       50       72

Karena Nilai C tidak lagi berubah menjadi 1 maka perbandingan telah berakhir dan hasil terakhir merupakan hasil pengurutan yang diharapkan.

Untuk Shell Sort, inilah Program-nya dalam C++ :

#include <iostream>
#include <conio.h>
#include <iomanip>
using namespace std;

int main(){
    int Nilai[20];
    int i, N, l, k;
    int temp, jarak, s;
    cout<<"Masukkan Banyak Bilangan : ";
    cin>>N;
    for(i=0; i<N; i++){
        cout<<"Elemen ke-"<<i<<" : ";
        cin>>Nilai[i];
    }
      
    cout<<"\nData sebelum diurut : ";
    for(i=0; i<N; i++)
        cout<<setw(4)<<Nilai[i];
        
    jarak = N / 2;
    cout<<"\nJarak = "<<jarak;
        while(jarak >=1){
            do{
              s=0;
                for(i=0; i<=(N-jarak)-1; i++){
                    k=i+jarak;
                    if(Nilai[i] > Nilai[k]){
                        temp = Nilai[i];
                        Nilai[i] = Nilai[k];
                        Nilai[k] = temp;
                        s=1;
                        for(l=0; l<N; l++)
                            cout<<setw(4)<<Nilai[i];
                        cout<<"\n\t";
                        getch();
                    }
                }
            }
            while(s!=0);
            jarak /= 2;
            cout<<"\nJarak= "<<jarak;
        }
    cout<<"\nData Setelah di urut dengan Shell Sort : ";
    for(i=0; i<N; i++)
        cout<<setw(4)<<Nilai[i];
    getch();
}

7. Metode Merge Sort

Sumber : Anaktik.com

Metode ini memanfaatkan keteraturan yang diperoleh dari hasil merging dua buah array. Suatu array Nilai yang mempunyai N elemen (Nilai[0..N-1]) dianggap terdiri dari N array yang masing-masing terdiri dari satu elemen. Untuk pasangan array yang berdekatan kita lakukan merging sehingga diperoleh N/2 buah array yang masing-masing array memiliki 2 Elemen (jika N ganjil, akan terdapat sebuah array dengan 1 elemen). Pada saat melakukan proses merging dilakukan pengaturan posisi dengan cara elemen yang lebih kecil diletakkan di posisi awal (untuk pengurutan secara menaik) dan elemen yang lebih besar diletakkan di posisi awal (untuk pengurutan secara menurun). Kemudian dilakukan merging kembali untuk setiap pasanga array seperti cara di atas sehingga kita peroleh N/2 buah array yang masing-masing array memiliki 4 elemen. Langkah ini kita teruskan hingga kita memperoleh sebuah Array yang sudah dalam keadaan terurut.

Misalkan kita memiliki array Nilai[0..13] = {45, 12, 4, 78, 90, 74, 40, 20, 10, 15, 25, 22, 95, 81} maka dengan menggunakan metode Merge Sort secara menaik dapat dilakukan seperti pada Gambar berikut ini.


Berikut, inilah Program C++ untuk Merge Sort :

#include <iostream>
#include <conio.h>
#include <iomanip>
using namespace std;

int main(){
    int Nilai[20];
    int i, N, l, k;
    int temp, jarak, s;
    cout<<"Masukkan Banyak Bilangan : ";
    cin>>N;
    for(i=0; i<N; i++){
        cout<<"Elemen ke-"<<i<<" : ";
        cin>>Nilai[i];
    }
      
    cout<<"\nData sebelum diurut : ";
    for(i=0; i<N; i++)
        cout<<setw(4)<<Nilai[i];
        
    jarak = N / 2;
    cout<<"\nJarak = "<<jarak;
        while(jarak >=1){
            do{
              s=0;
                for(i=0; i<=(N-jarak)-1; i++){
                    k=i+jarak;
                    if(Nilai[i] > Nilai[k]){
                        temp = Nilai[i];
                        Nilai[i] = Nilai[k];
                        Nilai[k] = temp;
                        s=1;
                        for(l=0; l<N; l++)
                            cout<<setw(4)<<Nilai[i];
                        cout<<"\n\t";
                        getch();
                    }
                }
            }
            while(s!=0);
            jarak /= 2;
            cout<<"\nJarak= "<<jarak;
        }
    cout<<"\nData Setelah di urut dengan Shell Sort : ";
    for(i=0; i<N; i++)
        cout<<setw(4)<<Nilai[i];
    getch();
}
Dan sebenarnya masih ada lagi Teknik Sorting, tapi sampai sini saja dulu ya guys!



1. Definisi Searching

Pencarian merupakan proses yang mendasar di dalam pemrograman. Pencarian (Searching) merupakan tindakan untuk mendapatkan suatu data dalam kumpulan data berdasarkan satu kunci (key) atau acuan data. Dalam kehidupan sehari-hari, seringkali kita berurusan dengan pencarian; misalnya untuk menemukan nomor telepon seseorang pada buku telepon atau mencari istilah dalam kamus, dan masih banyak lagi. Pada aplikasi komputer, pencarian kerapkali dilakukan. Misalnya untuk proses penghapusan data/record atau mengubah data/record tertentu di dalam suatu tabel atau file, langkah pertama yang harus dilakukan adalah mencari apakah data tersebut terdapat di dalam tabel/file atau tidak. Jika ada maka dapat dihapus atau diubah.

Kegunaan beberapa struktur data dalam hubungannya untuk menyimpan data sehingga memudahkan proses pencarian kembali tergantung pada :
  • Media penyimpanan data (memori, disk, tape).
  • Karakteristik jenis data yang disimpan (data numerik/character/string).
  • Jumlah data yang akan disimpan dan keperluan untuk akses data secepat-cepatnya.
Contoh struktur data yang dipakai untuk proses penyimpanan data selanjutnya untuk proses pencarian yaitu Array, List, dan Pohon Biner. Di dalam pembahasan ini hanya membahas pencarian data pada array, sedangkan pencarian pada pohon biner dilakukan pada pembahasan Tree.

Terdapat bermacam-macam persoalan pencarian dalam array. Pertama, dari sekumpulan data akan dilakukan pencarian data X, maka hasil pencarian hanya menampilkan suatu pesan “X ditemukan” atau “X tidak ditemukan”. 

Kedua, dari sekumpulan data akan dilakukan pencarian data X, andaikan data X ditemukan di posisi n dalam array maka hasil pencarian akan menampilkan “X ditemukan pada posisi n” dan jika data X tidak ditemukan maka hasil pencarian akan menampilkan “data X tidak ditemukan”. 

Ketiga, dari sekumpulan data akan dilakukan pencarian data X, ternyata data X terdapat lebih dari satu maka muncul pertanyaan “data yang mana yang akan ditampilkan? Apakah data yang pertama kali yang ditampilkan atau seluruh data yang ditemukan yang ditampilkan?”. Dari ketiga persoalan di atas dapat dilakukan, tergantung kebutuhan masing-masing.

Pencarian dapat dilakukan berdasarkan tempat penyimpanan, yang dibagi atas dua, yaitu pencarian internal dan pencarian eksternal. Pencarian internal yaitu pencarian yang dilakukan terhadap data yang berada dalam memori komputer. Pencarian eksternal yaitu pencarian yang dilakukan terhadap data yang berada dalam memori eksternal. Di dalam pembahasan ini hanya membahas tentang pencarian internal.

Pada umumnya dikenal tiga metode searching, antara lain adalah Sequensial Search, Binary Search, dan Interpolation Search.

2. Sequential Search

Sequential Search (Pencarian Beruntun) adalah metode pencarian yang paling mudah. Pencarian beruntun adalah proses membandingkan setiap elemen array satu per satu secara beruntun yang dimulai dari elemen pertama hingga elemen yang dicari ditemukan atau hingga elemen terakhir dari Array. Pencarian beruntun dapat dilakukan terhadap elemen array yang belum terurut atau terhadap elemen array yang terurut. Perbedaan dari keduanya terletak pada efisiensi operasi pembandingan yang dilakukan.

Dengan kata lain sequential search akan mencari data dengan cara membandingkannya satu-persatu dengan data yang ada. Prosesnya tentu saja akan singkat jika data yang diolah sedikit, dan akan lama jika data yang diolah banyak. Metode ini disarankan untuk digunakan pada data yang sedikit saja.

Contoh : Diberikan suatu array nilai dengan banyak Elemen 8 seperti berikut :


Misalkan nilai yang dicari adalah : X = 15

  • Jika yang diharapkan hanya menyatakan ada atau tidak ada maka pemeriksaan dilakukan terhadap 10 dan 15 maka tampil pesan “15 ditemukan”.
  • Kalau yang diharapkan adalah menampilkan seluruh data yang sama dan posisinya maka pemeriksaan dilakukan terhadap seluruh data 10, 15, 9, 3, 25, 65, 15, dan 30. Pada saat pemeriksaan dilakukan dan ternyata sama maka posisi data yang sama tersebut akan disimpan dalam variabel juga (tipe array) dan hitung banyaknya data yang sama. Sehingga akan tampil pesan “15 ditemukan sebanyak 2 yaitu pada posisi 2 dan 7”.

Berikut, inilah Program Pencarian untuk Kasus Pertama di atas (Sequential Search) :

#include <iostream>
#include <conio.h>
using namespace std;

int main(){
    int Nilai[20];
    int i, N, Bilangan;
    bool ketemu;
   
    cout<<"Program Sequential Search     "<<endl;
    cout<<"                              "<<endl;
    cout<<"Masukkan Banyaknya Bilangan : ";
    cin>>N;
      
    for(i=0; i<N; i++){
        cout<<"Masukkan Elemen ke-"<<i<<" : ";
        cin>>Nilai[i];
    }
      
    cout<<"Deretan Bilangan : ";
    for(i=0; i<N; i++)
    cout<<Nilai[i]<<" ";
    
    cout<<"                                      "<<endl;
    cout<<"Masukkan Bilangan yang akan Dicari : ";
    cin>>Bilangan;
      
    i=0;
    do
    {
        if(Nilai[i]==Bilangan)
        ketemu = true;
        i++;
    }
    while(!(ketemu));
      
    if(ketemu)
        cout<<"Bilangan "<<Bilangan<<" ditemukan";
    else
        cout<<"Bilangan "<<Bilangan<<" tidak ditemukan";
    getch();
}
Berikut, inilah Program Pencarian untuk Kasus Kedua di atas (Sequential Search) :

#include <iostream>
#include <conio.h>
using namespace std;

int main(){
    int Nilai[20];
    int Posisi[20];
    int i, N, Bilangan, Banyak=0;
    bool ketemu;
      
    cout<<"Program Sequential Search     "<<endl;
    cout<<"                              "<<endl;
    cout<<"Masukkan Banyaknya Bilangan : ";
    cin>>N;
    cout<<endl;
      
    for(i=0; i<N; i++){
        cout<<"Masukkan elemen ke-"<<i<<" : ";
        cin>>Nilai[i];
    }
      
    cout<<"Deretan Bilangan : ";
    for(i=0; i<N; i++)
    cout<<Nilai[i]<<" ";
    
    cout<<"                                      "<<endl;
    cout<<"Masukkan Bilangan yang akan Dicari : ";
    cin>>Bilangan;
      
    for(i=0; i<N; i++){
        if(Nilai[i]==Bilangan){
          ketemu = true;
          Posisi[Banyak]=i;
          Banyak++;
        }
    }
    if(ketemu){
        cout<<"Bilangan "<<Bilangan<<" ditemukan sebanyak "<<Banyak;
        cout<<"                                      "<<endl;
        cout<<"Pada posisi ke : ";
        for(i=0; i<Banyak; i++)
        cout<<Posisi[i]<<" ";
    }
    else
        cout<<"Bilangan "<<Bilangan<<" tidak ditemukan";
        getch();
}

3. Binary Search


Binary Search adalah metode pencarian suatu data atau elemen di dalam suatu array dengan kondisi data dalam keadaan terurut. Proses pencarian binary search hanya dapat dilakukan pada kumpulan data yang sudah diurutkan terlebih dahulu (menaik atau menurun). Prinsip dari binary search terhadap N elemen dapat dijelaskan seperti berikut :

1. Tentukan posisi awal = 0 dan posisi akhir = N-1.
2. Hitung posisi tengah = (posisi awal + posisi akhir)/2.
3. Bandingkan data yang dicari dengan elemen posisi tengah.
  • Jika sama maka catat posisi dan cetak kemudian berhenti.
  • Jika lebih besar maka akan dilakukan pencarian kembali ke bagian kanan dengan posisi awal = posisi tengah + 1 dan posisi akhir tetap kemudian ulangi mulai poin 2.
  • Jika lebih kecil maka akan dilakukan pencarian kembali ke bagian kiri dengan nilai posisi awal tetap dan nilai posisi akhir = posisi tengah – 1 kemudian ulangi mulai poin 2.
Dan inilah, Algoritma Pseudocode dari Binary Search :


Misalkan kita mempunyai sederetan data dalam array nilai sebanyak 10 elemen dan akan dilakukan pencarian data 87 terhadap array.

Nilai[0,9] = 12, 45, 23, 87, 90, 55, 15, 25, 40, 21

Urutkan elemen array secara menaik, sehingga diperoleh :

12
15
21
23
25
40
45
55
87
90
0
1
2
3
4
5
6
7
8
9
Aw
 
 
 
T
 
 
 
 
Ak

Nilai[0,9] = 12, 15, 21, 23, 25, 40, 45, 55, 87, 90

Data yang akan dicari : X = 87 (Bilangan)
Tentukan nilai Awal dan Akhir : Aw = 0, Ak = N-1 = 9

Hitung Nilai Tengah T = (0+9) / 2 = 4.5 = 4 (Mendekati 4)

Dicari > Nilai[tengah]
Dicari > Nilai[4]
87 > 25 → True

Karena 87 > 25, maka kita cari datanya dengan cara ditambah 1, Jadinya : 4+1=5

Aw = 5, Ak = 9

Nilai[5,9] = 40, 45, 55, 87, 90

40
45
55
87
90
5
6
7
8
9
Aw
 
T 
 
Ak

T = (5+9) / 2 = 14/2 = 7

Dicari > Nilai[tengah]
Dicari > Nilai[7]
87 > 55 → True

Karena 87 > 55, maka kita cari datanya dengan cara ditambah 1, Jadinya : 7+1=8

Aw = 8, Ak = 9

Berikut, inilah Program untuk Binary Search dalam C++ :

#include <stdio.h>
#include <iostream>
#include <conio.h>
#include <iomanip>
using namespace std;

int main() {
  int Nilai[20];
  int i, j, N;
  int temp, awal, akhir, tengah, Bilangan;
  
  cout<<"Program Binary Search"<<endl;
  cout<<"Banyak Bilangan : ";
  cin>>N;
  for(i=0; i<N; i++) {
    cout<<"Elemen ke-"<<i<<" : ";
    cin>>Nilai[i];
  }
  cout<<"Elemen Sebelum diurut : ";
  for(i=0; i<N; i++)
    cout<<setw(3)<<Nilai[i];
  
  for(i=0; i<N-1; i++) {
    for(j=i+1; j<N; i++) {
      if (Nilai[i] > Nilai[j])
      {
        temp = Nilai[i];
        Nilai[i] = Nilai[j];
        Nilai[j] = temp;
      }
    }
  }
  cout<<"Elemen Setelah diurut : ";
  for(i=0; i<N; i++)
    cout<<setw(3)<<Nilai[i];
    cout<<"indeks Elemen : ";
  for(i=0; i<N; i++)
    cout<<setw(3)<<i;
    cout<<"Masukkan data yang akan anda cari : ";
    cin>>Bilangan;
  
  awal = 0;
  akhir = N-1;
  do {
    tengah = (akhir + awal)/2;
    if(Bilangan < Nilai[tengah])
      akhir = tengah - 1;
    else
      awal = tengah + 1;
  }
  while((akhir >= awal) && (Nilai[tengah] !=Bilangan));
  if(Nilai[tengah] == Bilangan) {
    cout<<"Data "<<Bilangan<<" ada dalam array";
    cout<<" pada posisi "<<tengah;
  }
  else
    cout<<"Data "<<Bilangan<<" tidak ada dalam array";
  getch();
}

Itulah Materi tentang Teknik Sorting dan Teknik Searching yang telah saya sampaikan. Mohon maaf apabila ada kesalahan sedikitpun baik itu Penulisan Kata ataupun kesalahan dalam Program.

Terima Kasih 😄😘👌👍 :)

Wassalammu‘alaikum wr. wb.

Ads