Rencana Kuliah Minggu 9

      Insertion Sort 

1.      Identifikasi Masalah

Mengurutkan data dengan menggunakan metode Insertion Sort

misalkan : Ada setumpuk kartu di meja. kartu yang pertama diambil adalah 7. maka kita bisa misalkan 7 adalah i=1.
7
Lalu kartu selanjutnya yang diambil adalah 10. Dengan menggunakan prinsip bublesort maka letakkan kartu bernomor 10 di sebelah kanan kartu bernomor 7. Dengan memisalkan 7 adalah i maka 10 adalah i=2
7,10
Lalu kartu selanjutnya yang diambil adalah 3. 3 lebih kecil dari 7 dan 10, maka kita taruh kartu bernomor 3 di sebelah kiri kartu bernomor 7 dan 10. Dengan demikian nilai i pun berubah. Kartu bernomor 10 bergeser ke kanan dan memiliki i=3. Kartu bernomor 7 bergeser ke kanan dan memiliki i=2. Dan kartu bernomor 3 akan menempati i=1.
3,7,10
Lalu kartu selanjutnya yang diambil adalah 8. posisi delapan berada diantara 7 dan 10 karena 8>3, 8>7 dan 8<10. Kartu bernomor 10 bergeser ke kanan dan memiliki i=4 dan kartu bernomor 8 akan menempati i=3.
3,7,8,10

2.      Menentukan Input

Input : a.n, a.data[i]

Output : data

3.      Membuat Flowchart

4.      Tes menggunakan data

procedure insertion_sort(input/output  data:larik; input n:integer)

Deklarasi

 k, j, temp : integer

Deskripsi 

for k Å 2 to n do 

temp := data [k]; 

j := k-1;

while (temp <= data [j]) and (j > 1) do 

data [j+1] := data [j];

  j := j-1; 

endwhile

  if  (temp >= data [j]) then data [j+1] := temp

  else

  data [j+1] := data [j]; 

data [j] := temp; 

endif 

endfor

5.      Implementasi C++

#include <iostream>

 #include <conio.h>

 using namespace std;

class Sorting { 

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

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

 public: 

            void insertion_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() {

  Sorting angka;

  cin >> angka;

  angka.insertion_sort();

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

  cout << angka;

}

  

6.       Eksekusi

Waktu pengerjaan : sekitar 4 jam
catatan: dikerjakan diantara waktu luang dan dengan sambungan internet yang terputus-putus.

Untuk bagian Bubble Sort dapat dilihat di : http://ratihpuspita29.blogspot.co.id/2016/05/mengurutkan-data-dengan-metode-bubble.html
Untuk bagian Selection Sort dapat dilihat di : http://hiwilmacleta.blogspot.co.id/2016/05/rencana-kuliah-pertemuan-ke-9-selection.html

SEMOGA BERMANFAAT!!