insertion sort

Assalamuallaikum wr. wb.

     Kali ini saya akan membahas tentang insertion sort. Dimana insertion sort merupakan algoritma pengurutan dengan metode pergeseran.
Langsung saja ke pengembangan masalah dari insertion sort :
1. Identifikasi masalah
     Mengurutkan angka dengan metode insertion sort.
2. Menentukan input dan output
     Input n.
     Ouput data urut.
3. Membuat flowchart

4. Test menggunakan data

Untuk menjelaskan algoritma pengurutan dengan metode penyisipan, bayangkan 

setumpuk kartu ada di meja, dengan nomor : 

[2,1,3,4,5,] 

Pertama, kartu 2 : 

[2] 

Kedua, diambil kartu nomor 1, karena lebih kecil dari 2, ditaruh di sebelah kiri, sehingga 

diperoleh : 

[1,2] 

Ketiga, diambil kartu nomor 3, dibandingkan dengan kartu pertama, 3 lebih besar dari 1 dan 3 lebih besar dari 2, sehingga 3 diletakkan di sebelah kanan 1,2 diperoleh: 

[1,2,3] 

Keempat, diambil kartu nomor 4, dibandingkan dengan kartu pertama, 4 lebih besar dari 1, 4 lebih besar dari 2 dan 4 lebih besar dari 3 sehingga 4 diletakkan di sebelah kanan 1,2,3 diperoleh :

[1,2,3,4]

Kelima, diambil kartu nomor 5, dibandingkan dengan kartu pertama, 5 lebih besar dari 1, 5 lebih besar dari 2, 5 lebih besar dari 3 dan 5 lebih besar dari 4 sehingga 5 diletakkan di sebelah kanan 1,2,3,4 diperoleh :

[1,2,3,4,5]

note= jadi jika lebih besar dari angka sebelumnya di geser ke kanan jika lebih kecil di geser ke kiri. jika keduanya dari 2 nilai di antaranya.

5. Implementasi C++

#include <iostream>

/* 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 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] << " "; 

   

  } 

} 

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

Sorting angka; 

  cin >> angka; 

  angka.insertion_sort(); 

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

  cout << angka; 

return 0;

}

 6. Eksekusi

jadi pertama kita msukan banyak data yang mw kita urutkan. misalkan 5, dengan data [2,1,3,4,5]

cara pengerjaannya sama persis sama cara pengerjaan di atas tadi saat uji coba. jadi output sama dengan uji coba kita.

semoga bermanfaat teman. salam sukses.

saya mengerjakan program ini dan aploudnya dalam waktu 2 jam 56 menit.