- Output : permutasi (pengurutan) sejumlah n angka dari input yang sudah terurut secara ascending maupun descending
> Metode penyisipan (Insertion sort) bertujuan untuk menjadikan bagian sisi kiri array terurutkan sampai dengan seluruh array berhasil diurutkan.
Metode ini mengurutkan bilangan-bilangan yang telah dibaca; dan berikutnya secara
berulang akan menyisipkan bilangan-bilangan dalam array yang belum terbaca ke sisi kiri array yang telah terurut.
> Insertion Sort bekerja seperti banyak orang yang sedang mengurutkan kartu di tangan. Dimulai dengan tangan kiri yang kosong dan kartunya tertumpuk di meja. Selanjutnya kita ambil satu persatu kartu di meja dan diletakkan di tangan kiri dengan posisi yang benar (terurut). Untuk menemukan posisi yang banar, maka kita harus membandingkan satu persatu kartu yang ada (di tangan kiri) secara berurutan.
Konsep dasarnya bisa kita praktekan dalam permainan kartu Remi, dimana kita harus menyusun angka yang kecil di kiri dan yang besar di sebelah kanan.
Berikut Algoritma dan program C++ yang saya coba , Silahkna fahami .
Algoritma nya :
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
Berikut ini adalah Gambar Program Flowchart yang menggunakan Aplikasi RAPTOR :
Dan yang ini Gambar Program C++ yang Menggunakan Aplikasi Dev 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;
}
Sebelumnya jika kurang faham dengan penjelasan saya bisa kunjungi juga Blog Saudara saya :
atau ini
0 komentar:
Posting Komentar