Metode insertion sort array dengan C++

ALPRO HOME

Selamat datang. Disini saya akan menjelaskan apa yang dimaksud insertion sort

Untuk menjelaskan algoritma pengurutan dengan metode penyisipan, bayangkan
setumpuk kartu ada di meja, dengan nomor :
[8, 4, 7, 3, 1, 2, 6, 5]
Pertama, kartu 8, diperoleh di tangan kiri :
[8]
Kedua, diambil kartu nomor 4, karena lebih kecil dari 8, ditaruh di sebelah kiri, sehingga
diperoleh :
[4, 8]
Ketiga, diambil kartu nomor 7, dibandingkan dengan kartu pertama, 7 lebih besar dari 4 dan
lebih kecil dari 8, sehingga 7 diletakkan di antara 4 dan 8 :
[4, 7, 8]
Mulai langkah ketiga ini, kita dapat menarik kesimpulan, bahwa “tempat yang tepat” berarti
“kartu yang saat ini diambil akan diletakkan berada di antara yang kecil dan yang besar dari
kartu yang diambil tersebut”.
Urutan selengkapnya adalah sebagai berikut :
Data awal : [8, 4, 7, 3, 1, 2, 6, 5]
fase 1, 4 masuk [4, 8, 7, 3, 1, 2, 6, 5]
fase 2, 7 masuk [4, 7, 8, 3, 1, 2, 6, 5]
fase 3, 3 masuk [3, 4, 7, 8, 1, 2, 6, 5]
fase 4, 1 masuk [1, 3, 4, 7, 8, 2, 6, 5]
fase 5, 2 masuk [1, 2, 3, 4, 7, 8, 6, 5]
fase 6, 6 masuk [1, 2, 3, 4, 6, 7, 8, 5]
fase 7, 5 masuk [1, 2, 3, 4, 5, 6, 7, 8]
fase 8 [1, 2, 3, 4, 5, 6, 7, 8]




Dibawah ini saya akan menjelaskan insertion sort :

#include <iostream>
#include <conio.h>
using namespace std;
class Sorting { //membuat class sorting
friend istream& operator>>(istream& in, Sorting& a);
friend ostream& operator<<(ostream& out, Sorting& a);
public:
 //mengeset fungsi kedalam method yang bersifat public
void baca_data(); //berfungsi untuk membaca data
void cetak_data(); //berfungsi untuk mencetak data
void buble_sort();
void insertion_sort();
void selection_sort();
private: //mengeset fungsi kedalam method yang bersifat private
void minimum(int , int, int&); //menulis fungsi untuk menentukan nilai minimum
void tukar (int&, int&); //menulis fungsi untuk menukar nilai dari 2 parameter
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; //membuat variabel sebagai tempat nilai pertukaran
temp = a; //menempatkan nilai a di variabel temp
a = b; //mengeset a = b
b = temp; //menukarkan b sebagai template
}
void Sorting::insertion_sort()
{
int i, j, temp; //membuat variabel
cout << "Data pertama sudah ada ditangan kiri, yaitu : " << data[0] << '\n';
for(j = 1; j < n; j++) //membuat perulangan dengan batas kurang dari n
{
temp = data[j]; //mengeset temp dengan nilai data[j] dimana j akan bertambah nilai nya
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();
}
}
main(){
Sorting angka; //deklarasi class sorting
cin >> angka; //memasukkan nilai ke variabel angka
angka.insertion_sort(); //memanggil fungsi insertion sort
cout << "\nHasil akhir adalah : \n";
cout << angka; //hasil dari pengurutan akan ditampilkan menggunakan variabel angka
}

raptor : klik

Bagikan

Jangan lewatkan

Metode insertion sort array dengan C++

4/ 5

Oleh Bayu Ambika

May 14, 2016 Komentar