Pengertian Pengurutan Penyisipan Insertion Sort

Document Details:
  • Uploaded: May, 26th 2015
  • Views: 196 Times
  • Downloads: 0 Times
  • Total Pages: 7 Pages
  • File Format: .pdf
  • File size: 220.24 KB
  • Uploader: amanda
  • Category: Miscellaneous
 add to bookmark | report abuse
BAB V
Pengurutan Penyisipan (Insertion Sort)
Deskripsi :
Pada bab ini akan dibahas tentang pengertian pengurutan penyisipan.
Manfaat :
Memberikan pemahaman teknik pengurutan data yang dipakai untuk mengurutkan sejumlah data yang
tersimpan di memori dengan cara penyisipan.
Relevansi :
Untuk memproses data untuk keperluan tertentu diperlukan suatu data yang urut. Ada beberapa cara
pengurutan data. Salah satu teknik pengurutan data adalah pengurutan penyisipan (Insertion Sort).
Learning Outcome :
Mahasiswa memahami teknik pengurutan data-data secara pengurutan penyisipan untuk kepentingan
tertentu.
MATERI :
The bubble sort, yang dibahas pada bab 4, adalah jenis pengurutan yang paling mudah untuk dipahami,
cara tsb merupakan tahap awal yang baik dalam pembahasan kita tentang penyortiran. Namun, metode tsb
kurang canggih. Kita bisa memperbaikinya dengan beberapa kompleksitas tambahan. Hasilnya adalah
insertion sort. Pada bab ini akan kita bahas:
Algoritma insertion sort
C++ kode untuk insertion sort
Mengurutkan obyek dan bukan mengurutkan variabel sederhana
Insertion sort jauh lebih baik dibandingkan bubble sort (dan berbagai variasi pengurutan yang tidak
dibahas di sini). Ini masih menjalankan dalam O (N2) waktu, tapi ini adalah tentang dua kali lebih cepat
sebagai bubble sort. Hal ini juga tidak terlalu rumit, meskipun sedikit lebih terlibat daripada jenis bub-ble.
Ini sering digunakan sebagai tahap akhir dari jenis yang lebih canggih, seperti quicksort.
49
Pengurutan Penyisipan (Insertion Sort) pada Pemain
Baseball
Mulailah dengan pemain bisbol yang berbaris dalam urutan acak. (Mereka ingin bermain game, tapi jelas
tidak ada waktu untuk itu.) Lebih mudah untuk berpikir tentang insertion sort jika kita mulai di tengah-
tengah proses, ketika tim sebagian sudah urut.
Penyisipan Parsial
Anda akan membutuhkan penanda untuk menunjuk satu pemain. Mungkin Anda melempar kaus merah di
tanah di depan pemain. Para pemain di sebelah kiri (bukan kanan, seperti dalam bubble sort) penanda ini
sebagian diurutkan (atau internal diurutkan). Ini berarti mereka urut sendiri; masing-masing adalah lebih
tinggi dari orang disebelah kirinya. Namun, mereka tidak selalu dalam posisi terakhir mereka karena
mereka mungkin masih perlu dipindahkan ketika ada pemain dimasukkan di antara mereka. Para pemain
di sebelah kanan dari T-shirt yang dipilah.
Perhatikan bahwa pemilahan parsial tidak terjadi dalam bubble sort. Dalam algoritma tersebut bahwa
sekelompok item data benar-benar diurutkan pada waktu tertentu, dalam insertion sort, hanya sekelompok
item yang diurutkan.
Memasukkan Ditandai Pemain di lokasi yang tepat
Pemain yang mana ada penandanya, akan kita sebut pemain “ditandai” dan semua pemain di sebelah
kanannya, yang belum diurutkan. Hal ini ditunjukkan dalam bagian A pada Gambar 5.1.
Gambar 5.1: Insertion Sort pada pemain baseball.
50
Apa yang akan kita lakukan adalah memasukkan pemain ditandai di tempat yang tepat dalam (secara
parsial) kelompok yang sudah urut. Namun, untuk melakukan hal ini, kita harus menggeser beberapa
pemain diurutkan ke kanan untuk mendapatkan ruang(space). Untuk memberikan ruang bagi perubahan
ini, kita mengambil pemain ditandai keluar dari barisan. (Dalam program ini item data disimpan dalam
variabel sementara.) Hal ini ditunjukkan dalam bagian B pada Gambar 5.1.
Sekarang kita menggeser pemain diurutkan untuk mendapatkan ruang. Pemain yang tertinggi diurutkan
bergerak ke kanan, ke tempat yang pemain yang ditandai. Kemudian pemain tertinggi-berikutnya
bergerak satu ruang ke dekat pemain tertinggi, dan seterusnya.
Kapan proses ini pergeseran berhenti? Bayangkan bahwa Anda dan pemain yang ditandai akan berjalan
menyusuri jalur ke kiri. Pada setiap posisi Anda menggeser pemain lain ke kanan, tetapi Anda juga
membandingkan pemain yang ditandai dengan pemain hendak bergeser. Proses pergeseran berhenti ketika
Anda sudah menggeser pemain terakhir yang lebih tinggi dari pemain ditandai. Pergeseran terakhir
membuka ruang dimana pemain yang ditandai, ketika dimasukkan, akan berada di (secara parsial) bagian
yang terurut. Hal ini ditunjukkan dalam bagian C pada Gambar 5.1.
Sekarang bagian yang sudah urut memiliki satu pemain lagi, dan kelompok yang tidak terurut memiliki
lebih sedikit pemain. Penanda T-shirt dipindahkan satu ruang ke kanan, jadi di depan paling kiri, pemain
diurutkan. Proses ini diulang sampai semua pemain yang belum urut telah disisipkan (makanya nama
insertion sort) ke tempat yang tepat dalam kelompok sebagian diurutkan.
Sekarang kita pelajari bagaimana insertion sort bekerja, dan diterapkan di C ++.
Menerapkan Insertion Sort dengan C++
Listing 5.1 menunjukkan fungsi anggota yang melaksanakan insertion sort, diambil dari program
insertSort.cpp
Masukan LISTING 5.1 Fungsi anggota insertionSort()
void insertionSort()
{
int in, out;
for(out=1; out<nElems; out++) //out is dividing line
{
double temp = v[out]; //remove marked item
in = out; //start shifts at out
while(in>0 && v[in-1] >= temp) //until one is smaller,
{
v[in] = v[in-1]; //shift item to right
--in; //go left one position
}
v[in] = temp; //insert marked item
} //end for
} //end insertionSort()
5.1. PENGURUTAN PENYISIPAN PEMAIN BASEBALL 51
Analisa
Kalang (Loop) for bagian luar dimulai pada 1 dan bergerak ke kanan, itu menandai data tidak terurut
paling kiri. Di dalam kalang while, di mulai pada out dan bergerak kiri, sampai temp lebih kecil dari
elemen array di sana, atau tidak bisa pergi meninggalkan lebih jauh. Setiap melewati kalang while
menggeser elemen terurut lain ke satu ruang ke kanan. Gambar 5.4 menyajikan diagram alir
insertSort.cpp sedangkan Listing 5.2 menunjukkan program insertSort.cpp lengkapnya.
Figue 5.4
Diagram alir insertSort.cpp
MasukanListing 5.2 Program insertSort.cpp
//insertSort.cpp
//demonstrates insertion sort
#include <iostream>
#include <vector>
using namespace std;
//--------------------------------------------------------------
class ArrayIns
{
private:
vector<double> v; //vector v
int nElems; //number of data items
//--------------------------------------------------------------
public:
ArrayIns(int max) : nElems(0) //constructor
{
5.2. MENERAPKAN INSERTION SORT DENGAN C++ 52
v.resize(max); //size the vector
}
//--------------------------------------------------------------
void insert(double value) //put element into array
{
v[nElems] = value; //insert it nElems++;
//increment size
}
//--------------------------------------------------------------
void display() //displays array contents
{
for(int j=0; j<nElems; j++) //for each element, cout << v[j] << “ “; //display it
cout << endl;
}
//--------------------------------------------------------------
void insertionSort()
{
Int in, out;
for(out=1; out<nElems; out++) //out is dividing line
{
double temp = v[out]; //remove marked item
in = out; //start shifts at out
while(in>0 && v[in-1] >= temp) //until one is smaller,
{
v[in] = v[in-1]; //shift item to right
--in; //go left one position
}
v[in] = temp; //insert marked item
} //end for
} //end insertionSort()
//--------------------------------------------------------------
}; //end class ArrayIns
////////////////////////////////////////////////////////////////
int main()
{
int maxSize = 100; //array size
ArrayIns arr(maxSize); //create array
arr.insert(77); //insert 10 items
arr.insert(99);
arr.insert(44);
arr.insert(55);
arr.insert(22);
arr.insert(88);
arr.insert(11);
arr.insert(00);
arr.insert(66);
arr.insert(33);
arr.display(); //display items arr.insertionSort(); //insertion-sort them
arr.display(); //display them again return 0;
} //end main()
5.2. MENERAPKAN INSERTION SORT DENGAN C++ 53
Displaying 5 of 7 pages, to read the full document please DOWNLOAD.
Tags: