Rencana Kuliah Bulan Ke-3 : Sorting Data Secara Manual Dengan Metode INSERTION SORT

Bismillahirohmanirrohim
Assalamualikum w.w,

Berikut ini adalah materi dari SEARCING AND SORTING. Program yang dibuat yaitu tentang Sorting Data Secara Manual Dengan Metode Insertion Sort

Insertion Sort

     Insertion Sort merupakan algoritma sorting, terutama untuk mengurutkan data dengan jumlah element sedikit. Dimana Input berupa deretan angka jumlah n buah data dan output berupa permutasi (pengurutan) sejumlah n angka dari input, dimana hasilnya berupa data yang sudah terurut secara asceding maupun desceding.
     Proses yang terjadi pada pengurutan dengan Insertion Sort adalah dimulai dari data ke-2 kemudian disisipkan pada tempat yang sesuai. Data pada posisi pertama dianggap memang sudah benar pada tempatanya. Ilustrasinya mirip seperti saat menyisipkan kartu dipermainan kartu. Dimulai dengan tangan kiri yang kosong dan kartunya tertumpuk dimeja. Selanjutnya kita ambil satu persatu kartu di meja dan diletakkan ditangan kiri dengan posisi yang benar (terurut).Untuk menemukan posisi yang benar, maka kita harus membandingkan satu persatu kartu yang ada (ditangan kiri) secara berurutan.
     Demikian juga halnya dalam pengurutan data. Jika data sudah ada, maka pengurutan dimulai dengan mengambil satu data dan membandingkannya dengan data-data yang ada didepannya. Jika data yang diambil memenuhi syarat perbandingan, maka data yang diambil tersebut akan diletakan di depan data yang dibandingkan, kemudian data-data yang dibandingkan akan bergeser mundur.

     Catatan: Dalam hal pengurutan data dengan metode insertion sort ini, data yang diambil pertama adalah data kedua, kemudian data yang diambil akan dibandingkan dengan data – data yang ada disebelah kiri / data sebelumnya (data- data sebelum data yang diambil). Jika proses tersebut selesai, maka akan dilanjutkan dengan data-data selanjutnya (data ke-3, data ke-4… dan seterusnya). Proses akan berlangsung sampai data – data terurutkan dengan benar.

   Berikut adalah simulasi Algoritma Insertion Sort Jika digambarkan secara singkat, maka algoritma Insertion sort ini dapat digambar sebagai berikut.

Ilustrasi konsep insertion sort ini adalah sebagai berikut:

5 [2] 4 6 1 3
2 5 [4] 6 1 3
2 4 5 [6] 1 3
1 2 4 5 6[ 3]
1 2 3 4 5 6

Berikut ini penjelasan menggunakan 5 kaidah :
1. Mengerti masalah :
    Mencari bilangan terkecil ke yang terbesar 
2. Menentukan input dan output nya :
    input = 5 2 4 6 1 3
    output = 1 2 3 4 5 6
3. Menyusun Algoritma dengan Flowchart :

4. Mengelementasikan Dengan C++ :

#include <iostream>

#include <conio.h>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

using namespace std;

class Sorting {

      friend istream& operator>>(istream& in, Sorting& a);

      friend ostream& operator<<(ostream& out, Sorting& a);

public:

       void baca_data();

       void cetak_data();

  void buble_sort();

  void insertion_sort();

  void selection_sort();

private:

        void minimum(int , int, int&);

void tukar (int&, int&);

int data[10], n;

};

  istream& operator>>(istream& in, Sorting& a) {

    cout<<"Banyak data : ";

    in>>a.n;

    for (int i = 0; i < a.n; i++) {

    cout<<"Data ke-" <<i+1<< " : ";

    in>>a.data[i];

}

  return in;

}

  ostream& operator<<(ostream& out, Sorting& a) {

    for (int i = 0; i < a.n; i++)

    out<<a.data[i] << " ";

    out<<"\n";

  return out;

}

  void Sorting::tukar (int &a, int &b){

       int temp;

       temp = a;

  a = b;

  b = temp;

  }

  void Sorting::insertion_sort(){

       int i, j, temp;

  cout<<"Data pertama sudah ada ditangan kiri, yaitu : " << data[0] << '\n';

  for(j = 1; j < n; j++){

           temp = data[j];

  cout<<"\nData ke-" << j+1 << " yaitu " << data[j] << " diambil dari meja\n";

  cout<<"Dilakukan penggeseran elemen :\n";

       for(i = j - 1; (i >= 0) && (data[i] > temp); i--){

           cout<<"data pd posisi ke-[" << i+1 << "] digeser ke posisi [" << i+2 << "]\n";

  data[i+1] = data[i];

       }

        cout<<"Data baru masuk pada posisi ke-[" << i+2 << "]\n";

data[i+1] = temp; //Insert key into proper position

cout<<"Data saat ini adalah : ";

for (int k=0; k<=j; k++) cout << data[k] << " ";

            getch();

}

  }

int main(int argc, char** argv) {

    Sorting angka;

cin>>angka;

angka.insertion_sort();

cout<<"\nHasil akhir adalah : \n";

cout<<angka;

 return 0;

}

    

5. Menguji coba dengan data :

    Setelah diuji coba program nya berjalan. 

Materi Selanjut nya:
Sorting Data Secara Manual Dengan Metode Bubble Sort KETIK DISINI
Sorting Data Secara Manual Dengan Metode Selection Sort KLIK DISINI

Alhamdulillah

Selamat mencoba dan semoga bermanfaat :)

Wassalamualikum w.w.