Fighting....!!!!!

Fighting....!!!!!

Sabtu, 16 Juni 2012

INTERRUPT

                Interupsi atau bisa disebut Interrupt adalah kejadian yang menyebabkan mikrokontroler berhenti sejenak untuk melayani interupsi tersebut  atau memiliki pengertian suatu permintaan khusus kepada mikroprosessor untuk melakukan sesuatu. Bila terjadi interupsi, mikroprosesor akan menghentikan dahulu apa yang sedang dikerjakannya dan mengerjakan permintaan khusus tersebut. Program yang dijalankan pada saat melayani interupsi disebut Interrupt Service Routine. Setelah selesai melayani interupsi maka program yang tadi terhenti dilanjutkan kembali.

Mikrokontroler AT89C51 menyediakan 5 sumber interupsi, yaitu:
-          2 interupsi eksternal,
-          2 interupsi timer, dan
-          satu interupsi port serial.

Register yang mengontrol interupsi yaitu :
-          IE (Interrupt enable) dan
-          IP (Interrupt priority).

Jenis-jenis interrupt:
a. Software, interrupt jenis ini juga disebut System call. Misalnya, suatu program ingin mencetak
hasil dengan printer
b. Hardware, terjadi karena adanya aksi pada perangkat keras, seperti penekanan tombol
keyboard atau menggerakkan mouse.
Interrupt ini terbagi lagi menjadi dua,yaitu:
-          Maskable Interrupt(terjadi karena aksi luar) dan
-          Non Maskable Interrupt(terjadi karena memori atau kesalahan parity pada program)
Penyebab terjadinya Interrupt:
a. Program, terjadi akibat eksekusi suatu instruksi
b. Timmer, disebabkan oleh timmer prosessor
c. I/O, disebabkan oleh I/O controller baik sebagai tanda bahwa operasi telah selesai maupun
memberi tanda eror.
d. Kegagalan hardware, disebabkan oleh kesalahan hardware seperti power failure dan memori parity eror.
Ada dua aksi yang diberikan saat terjadi interrupt:
a. Syncronous I/O. I/O dijalankan, I/O selesai digunakan, kontrol menginformasikan kembali ke user
proses. Untuk menunggu selesai digunakannya I/O, digunakan perintah wait.
b. Asyncronous I/O. Kembali ke user program tanpa harus menunggu I/O.
Interrupt Service Routine.
Interrupt adalah suatu kejadian atau peristiwa yang menyebabkan mikrokontroler berhenti sejenak untuk melayani interrupt tersebut.
Analoginya adalah sebagai berikut, seseorang sedang mengetik laporan, mendadak telephone berdering dan menginterrupsi orang tersebut sehingga menghentikan pekerjaan mengetik dan mengangkat telephone. Setelah pembicaraan telephone yang dalam hal ini adalah merupakan analogi dari Interrupt Service Routine selesai maka orang tersebut kembali meneruskan pekerjaanya mengetik.
Demikian pula pada sistem mikrokontroler yang sedang menjalankan programnya, saat terjadi interrupt, program akan berhenti sesaat, melayani interrupt tersebut dengan menjalankan program yang berada pada alamat yang ditunjuk oleh vektor dari interrupt yang terjadi hingga selesai dan kembali meneruskan program yang terhenti oleh interrupt tadi. Seperti yang terlihat Gambar di bawah, sebuah program yang seharusnya berjalan terus lurus, tiba-tiba terjadi interrupt dan harus melayani interrupt tersebut terlebih dahulu hingga selesai sebelum ia kembali meneruskan pekerjaannya.

>> Enable Interrupt  &  Disable Interrupt

Enable Interrupt
Kelima sumber interupsi yang dimiliki AT89C51 dapat di-enable atau di-disable
melalui register IE (Interrupt Enable) yang terletak di alamat A8H.

Disable Interrupt
-          Solusi paling sederhana adalah memiliki setiap proses menonaktifkan semua interrupts hanya setelah memasuki nya CS dan mengaktifkan kembali mereka sebelum meninggalkannya.
-          Dengan interupsi dinonaktifkan, tidak mengganggu jam dapat terjadi (CPU hanya beralih dari proses ke proses sebagai hasil dari jam atau interupsi lainnya)
-          Dengan interupsi dimatikan CPU tidak akan dialihkan ke proses lain!  Jadi, sekali proses telah menonaktifkan interupsi, dapat memeriksa dan memperbarui memori bersama tanpa takut bahwa proses lainnya akan campur tangan.
-          Pendekatan ini umumnya tidak menarik karena tidak bijaksana untuk memberikan proses pengguna kekuatan untuk mematikan interupsi.  Misalkan salah satu dari mereka melakukannya dan tidak pernah mengubahnya lagi. Itu bisa menjadi akhir dari sistem.
-          Di sisi lain, sering nyaman untuk kernel itu sendiri untuk menonaktifkan interupsi untuk beberapa instruksi ketika sedang memperbarui variabel atau daftar.

Jika driver Anda menangani interupsi perangkat, maka harus menyediakan EvtInterruptEnable dan EvtInterruptDisable fungsi callback yang mengaktifkan dan menonaktifkan interupsi.  Biasanya, fungsi-fungsi callback dijalankan pada perangkat DIRQL dan harus melakukan apapun yang diperlukan untuk mengaktifkan dan menonaktifkan mekanisme interrupt sebuah perangkat.  Untuk pasif tingkat interupsi, fungsi-fungsi callback dijalankan pada IRQL = PASSIVE_LEVEL sambil memegang kunci pasif tingkat interupsi.
 Jika driver Anda harus melakukan operasi tambahan yang terkait dengan mengaktifkan atau menonaktifkan menyela, dan jika operasi tambahan tidak dapat dilakukan pada IRQL = DIRQL, pengemudi juga dapat memberikan EvtDeviceD0EntryPostInterruptsEnabled dan EvtDeviceD0ExitPreInterruptsDisabled fungsi callback.  Kedua fungsi callback dijalankan pada IRQL = PASSIVE_LEVEL tanpa kunci interupsi diadakan, dan dapat memanggil metode objek kerangka yang tidak tersedia di IRQL = DIRQL.
                Kerangka panggilan driver  EvtInterruptEnable dan EvtDeviceD0EntryPostInterruptsEnabled fungsi callback setiap kali perangkat masuk kerja nya (D0) menyatakan, setelah kerangka telah memanggil driver  EvtDeviceD0Entry fungsi callback.
                Kerangka panggilan driver  EvtDeviceD0ExitPreInterruptsDisabled dan EvtInterruptDisable fungsi callback setiap kali perangkat meninggalkan negaranya bekerja, sebelum kerangka panggilan driver  EvtDeviceD0Exit fungsi callback.  Untuk informasi lebih lanjut tentang kapan kerangka memanggil fungsi callback driver , melihat PnP dan Skenario Power Management .
Anda tidak harus mengasumsikan bahwa perangkat akan menggunakan sumber daya interupsi yang sama setiap kali kerangka panggilan driver Anda EvtInterruptEnable fungsi callback.  Kadang-kadang manajer PnP mendistribusikan kembali sumber daya sistem , dan dapat menetapkan sumber interupsi baru ke perangkat.
Driver dapat menghubungi WdfInterruptGetInfo untuk menentukan sumber interupsi sebuah perangkat.  Driver dapat menghubungi WdfInterruptGetDevice untuk menentukan perangkat yang mengganggu obyek milik.  (A beberapa driver sebut WdfInterruptWdmGetInterrupt .)
 Untuk mengaktifkan dan menonaktifkan interrupts langsung, driver  dapat memanggil objek mengganggu yang WdfInterruptEnable dan WdfInterruptDisable metode, yang memanggil driver  EvtInterruptEnable dan EvtInterruptDisable fungsi event callback.  Namun, sebagian besar drivers  hanya harus memungkinkan kerangka untuk memanggil fungsi callback EvtInterruptEnable dan EvtInterruptDisable pada waktu yang tepat.

>> Paralel Interrupt
         
Menangani banyak perangkat:
                Pada suatu request diterima melalui jalur interrupt request, informasi tambahan diperlukan untuk mendefinisikan perangkat  tertentu yang membengkitkan jalur tersebut. Informasi yang diperlukan untuk menentukan apakah suatu perangkat meminta interrupt tersedia dalam status registernya. Pada saat suatu perangkat memunculkan suatu interrupt request, maka salah satu skema paling mudah untuk diimplementasikan kerugian utamanya adalah waktu yang dihabiskan mengetahui bit IRQ semua perangkat yang mungkin tidak meminta pelayanan apapun. Pendekatan alternatife adalah dengan menggunakan vector interrupt.


>> Vektor Interrupt

 Vektor Interupsi Vector interupsi merupakan 4 byte data yang disimpan pada 1024 byte pertama memori (000000h-0003FFFh) jika mikroprosesor dijalankan dalam real mode. Setiap vector interupsi ini berisi alamat procedure layanan interupsi, yaitu suatu procedure khusus yang dipanggil oleh vector interupsi. Dua byte pertama dari vector tersebut berisi alamat IP dan 2 byte terakhir berisi alamat CS dari procedure layanan interupsi tersebut.
ADa 256 vektor interupsi yang dimiliki mikroprosesor intel. Intel menyediakan 32 vektor interupsi untuk 8086-80486 dan kebutuhan-kebutuhan pengembangan di masa mendatang, sedangkan sisanya disediakan untuk dimanipulasi untuk digunakan untuk keperluan pengguna.





Sorting (pengurutan)


 PENGURUTAN BILANGAN

Pengurutan data (sorting) didefinisikan sebagai suatu proses untuk menyusun
kembali humpunan obyek menggunakan aturan tertentu. Mnurut Microsoft Book-shelf,
definisi algoritma pengurutan adalah algoritma untuk meletakkan kumpulan elemen data ke dalam urutan tertentu berdasarkan satu atau beberapa kunci dalam tiap-tiap elemen. Ada dua macam urutan yang biasa digunakan dalam proses pengurutan yaitu:

  Urut naik (ascending) yaitu dari data yang mempunyai nilai paling kecil sampai paling
besar
  Urut turun (descending) yaitu data yang mempunyai nilai paling besar sampai paling
kecil.

Contoh : data bilangan 5, 2, 6 dan 4 dapat diurutkan naik menjadi 2, 4, 5, 6 atau diurutkan turun menjadi 6, 5, 4, 2. Pada data yang bertipe char, nilai data dikatakan lebih kecil ataulebih besar dari yang lain didasarkan pada urutan relatif (collating sequence) seperti dinyatakan dalam tabel ASCII

Keuntungan dari data yang sudah dalam keadaan terurutkan antara lain :

Data mudah dicari (misalnya dalam buku telepon atau kamus bahasa), mudah untuk
dibetulkan, dihapus, disisipi atau digabungkan. Dalam keadaan terurutkan, kita
mudah melakukan pengeekan apakah ada data yang hilang
Melakukan komppilasi program komputer jika tabel-tabel simbol harus dibentuk
Mempercepat proses pencarian data yang harus dilakukan berulang kali.

Data yang diurutkan sangat bervariasi, dalam hal jumlah data maupun jenis data
yang akan diurutkan. Tidak ada algoritma terbaik untuk setiap situasi yang kita hadapi,
bahkan cukup sulit untuk menentukan algoritma mana yang paling baik untuk situasi
tertentu karena ada beberapa faktor yang mempengaruhi efektifitas algoritma pengurutan. Beberapa faktor yang berpengaruh pada efektifitas suatu algoritma pengurutan antara lain:

Banyak data yang diurutkan
Kapasitas pengingat apakah mampu menyimpan semua data yang kita miliki
Tempat penyimpanan data, misalnya piringan, pita atau kartu, atau media penyimpan
yang lain.
Pemilihan algoritma sangat ditentukan oleh struktur data yang digunakan. Metode
pengurutan yang digunakan dapat diklasifikasikan menjadi dua katagori yaitu :
Pengurutan internal, yaitu pengurutan dengan menggunakan larik (array). Larik
tersimpan dalam memori utama komputer
Pengurutan eksternal, yaitu pengurutan dengan menggunakan berkas (sequential
access file). Berkas tersimpan dalam pengingat luar, misalnya cakram atau pita
magnetis.

Untuk menggambarkan pengurutan dengan larik, bisa kita bayangkan semua kartu terletak di hadapan kita sehingga semua kartu terlihat dengan jelas nomornya. Pada penyusunan kartu sebagai sebuah berkas, kita bayangkan semua kartu kita tumpuk
sehingga hanya kartu bagian atas saja yang bisa kita lihat nomornya.
Pada Pembahasan  ini akan dijelaskan beberapa metode pengurutan beserta analisanya.

Metode Bubble Sort

PROSES PENGURUTAN

Untuk mengurutkan bilangan diperlukan variabel array untuk menampung semua bilangan yang akan diurutkan. Proses pengurutan dilakukan dengan membandingkan semua elemen array satu per satu. 

Dimetode bubble sort, proses pengurutan dimulai dengan membandingkan elemen pertama untuk mendapatkan angka terbesar. Lalu angka tersebut ditempatkan pada elemen terakhir.  Sebagai langkah awal, isi elemen pertama dibandingkan dengan elemen ke-2. Jika isi elemen ke-2 lebih kecil dari elemen pertama, maka isi kedua elemen tersebut ditukar. Sehingga isi array berubah menjadi :

Lalu elemen ke-2 dibandingkan dengan elemen ke-3. jika isi elemen ke-3 lebih besar, maka isi kedua elemen tersebut tidak ditukar.

Perbandingan selanjutnya dilakukan terhadap elemen ke-3 dengan ke-4. Karena elemen ke-4 lebih kecil, maka isi kedua elemen tersebut ditukar. Sehingga isi array sebelumnya berubah menjadi :

Proses perbandingan seperti diatas dilakukan secara berulang sampai pada elemen terakhir. Sehingga pada akhirnya akan dihasilkan bilangan terbesar yang ditempatkan pada posisi elemen terakhir. Dibawah ini kondisi array setelah perbandingan elemen terakhir.

Proses diatas hanya mencari bilangan terbesar pertama. Ulangi proses tersebut untuk mencari bilangan terbesar lainnya setelah bilangan terbesar pertama tadi. Namun proses perbandingan hanya dilakukan mulai dari elemen pertama sampai elemen ke-7.
Isi elemen pertama dibandingkan dengan elemen ke-2. Karena isi elemen ke-2 lebih besar, maka isi kedua elemen tersebut tidak ditukar.
Kemudian elemen ke-2, dibandingkan dengan elemen ke-3. Karena elemen ke-3 lebih kecil. Lanjutkan proses diatas sampai pada elemen ke-7. 
           
            Kini isi elemen ke-7 dan ke-8 sudah urut berdasarkan bilangan kecil ke besar. Namun elemen lainnya belum terurut. Untuk itu ulangi proses diatas, namun elemen yang dibandingkan hanya sampai pada elemen ke-6 saja. Setelah itu, proses perbadingan diulangi lagi sampai elemen terakhir yang dibandingkan yaitu elemen ke-2. 
IMPLEMENTASI DALAM BENTUK FLOWCHART

Seperti telah dijelaskan sebelumnya, proses pengurutan memakai variabel array untuk menampung semua bilangan yang akan diurutkan. Oleh karena itu sebelum proses pengurutan dilakukan, terlebih dahulu dibuat proses untuk mengisi semua bilangan ke dalam array. Setelah array tersebut terisi, barulah proses pengurutan dilakukan untuk mengurutkan isinya.
Seperti diketahui, jika salah satu elemen array diisi dengan nilai baru, maka nilai lama akan terhapus. Oleh sebab itu untuk mempertukarkan isi elemen array harus mengggunakan satu variabel cadangan. Variabel ini digunakan untuk menyimpan isi array yang akan ditukar.

Misalnya isi elemen ke-2 dari variabel BILARR akan ditukar dengan elemen ke-3. Maka isi elemen ke-2 disimpan terlebih dahulu ke variabel cadangan ( misalnya untuk variabel ini diberi nama TEMP). Setelah itu, isi elemen ke-3 dipindahkan ke elemen ke-2, lalu isi dari variabel TEMP dipindahkan ke elemen ke-3. Ilustrasi dibawah ini memperlihatkan pertukaran kedua elemen tersebut.

 Berdasarkan flowchart
proses pengurutan bilangan dari kecil ke besar dapat 
dirangkum sebagai berikut :
1. persiapan variabel yang dipakai dalam proses, yaitu :
N : variabel untuk menyatakan jumlah elemen array. Jumlah ini diketahui
berdasarkan banyaknya bilangan yang diinputkan melalui keyboard.

              I, J : variabel indeks untuk membandingkan isi array
2. prose pertama yang dilakukan adalah mengisi semua bilangan yang akan diurutkan ke array. Pada flowchart diatas, array tersebut diberi nama BILARR. Bilangan diinput melalui keyboard dan disimpan didalam variabel BIL.
3. periksa isi variabel BIL. Pada flowchart diatas, diasumsikan pengisian bilangan berakhir jika operator mengetik 0 untuk bilangan yang diinput. Oleh karena itu, jika BIL = 0 maka proses dilanjutkan ke langkah 7 untuk mulai pengurutan bilangan. Jika BIL tidak sama dengan 0 berarti pengisian bilnagan belum berakhir, maka proses dilanjutkan ke langkah 4.
4. variabel N ditambah 1. variabel ini untuk menentukan elemen array yang akan diisi nilai dari variabel BIL.
5. isi elemen array dengan nilai yang tersimpan di variabel BIL. Posisi elemen tersebut ditentukan berdasarkan harga N.
6. kembali ke langkah 2 untuk menginput bilangan lainnya.
7. variabel J ditambah 1.
8. variabel I ditambah 1.
9. bandingkan isi elemen array pada posisi sesuai dengan nilai variabel I atau BILARR (I) dengan elemen array didepannya yaitu posisi I+1 atau BILARR (I+1). Jika isi BILARR(I) lebih kecil dari BILARR (I+1) maka isi kedua elemen tersebut tidak ditukar. Untuk itu proses dilanjutkan ke lankah 11. namun juka isi BILARR(I) > dari BILARR(I+1) lanjutkan ke langkah 10 untuk menukar isi kedua elemen tersebut.
10. pindahkan isi BILARR(I) ke variabel sementara yaitu TEMP.
pindahkan isi BILARR(I+1) ke BILARR(I).
pindahkan isi TEMP ke BILARR(I+1).
11. periksa isi variabel I. jika I sama dengan N-J maka proses perbandingan untuk mencari bilangan terbesar pertama selesai. Untuk itu proses dilanjutkan ke langkah 12. jika isi I belum sama, maka proses perbandingan untuk mencari bilangan terbesar belum selesai. Untuk itu proses selanjutnya kembali ke langkah 8.
12. periksa isi variabel J. jika J sama dengan N-1, maka semua elemen telah diperbandingkan dan proses pengurutan telah selesai. Untuk itu proses dilanjutkan ke langkah 15 untuk mencetak seluruh isi arrray. Jika isi J masih belum sama dengan N-1 maka semua bilangan belum terurut. Proses dilanjutkan ke langkah 13 untuk mencari bilangan terbesar lainnya.
13. variabel I diisi nilai 0.
14. kembali ke langkah 7 untuk mencari bilangan terbesar lainnya.
15. Variabel I diisi nilai 0.
16. variabel I ditambah 1.
17. cetak isi BILARR(I).
18. periksa isi I. jika I sama dengan N berarti semua elemen array telah dicetak maka proses selesai. Jika isi I belum sama dengan N berarti semua elemen array belum tercetak. Untuk itu kembali ke langkah 16 untuk mencetak elemen lainnya.

Metode Selection Sort

Selection Sort salah satu algoritma pengurutan yang mudah untuk dipelajari.
Konsep dasarnya yaitu : “Melakukan pencarian data terkecil/terbesar pada suatu iterasi. Kemudian data tersebut ditukar dengan data[index]. index=iterasi. Jumlah iterasi ditentukan oleh banyaknya data atau ‘N’. Iterasi=N-1.”
Selection Sort adalah sebuah algoritma pengurutan, dimana data terkecil / terbesar akan ditempatkan di awal atau di akhir data. Berbeda dengan Bubble Sort yang langsung menukarkan data jika ditemukan, maka dalam selection sort setelah data yang “nyeleneh” alias tidak terurut ditemukan, tidak akan langsung ditukarkan melainkan akan ditandai terlebih dahulu sebagai data terkecil / terbesar dalam satu iterasi.
Pengurutan Seleksi ada dua macam, yaitu :
1.  Pengurutan Seleksi Minimum
Sesuai dengan namanya, maka yang dijadikan acuan dalam satu iterasi adalah data terkecil. Untuk lebih jelasnya bisa dilihat pada syntax dibawah ini
#include<iostream.h>
#include<conio.h>
 
class seleksi{
static int A[10];
public:
void seleksi_maksimum();
void tampil();
};
 
int seleksi::A[10]={54,23,12,56,78,50,12,89,10,12};
 
void seleksi::tampil(){
   for(int a=0;a<10;a++) cout<<A[a]<<" ";
   cout<<endl<<endl;
}
 
void seleksi::seleksi_maksimum(){
int i,j,imax,temp;
for(i=10;i>=0;i--){
                                         imax=i;
                                         for(j=i-1;j>=0;j--){
                                                             if(A[j]>A[imax]){
                                                                                 imax=j;
                                                             }
                                         }
                                         temp=A[i];
                                         A[i]=A[imax];
                                         A[imax]=temp;
                    }
}
 
main(){
cout<<"SELEKSI MAKSIMUM"<<endl<<endl;
      seleksi x;
                    cout<<"Sebelum diurut : "<<endl<<"A = ";
      x.tampil();
                    x.seleksi_maksimum();
                    cout<<"Setelah diurut : "<<endl<<"A = ";
      x.tampil();
                    getch();
}
 
Pada dasarnya, data paling ujung akan di anggap sebagai data terbesar. Data terbesar ini kemudian akan dibandingkan dengan data sebelumnya. Jika ternyata data sebelumnya lebih besar, maka “gelar” data terbesar / imax akan diwariskan ke data sebelumnya.

imax=i;
for(j=i-1;j>=0;j--){
if(A[j]>A[imax]){
imax=j;
}
}

Begitu seterusnya, sampai pengulangan berhenti. Jika pengulangan sudah berhenti, maka barulah akan terjadi penukaran data

temp=A[i];A[i]=A[imax];

A[imax]=temp;

2. Pengurutan Seleksi Minimum
Ini adalah kebalikan dari Pengurutan Seleksi Maksimum , 
dimana disini yang dijadikan acuan adalah data terkecil. Untuk lebih jelasnya bisa dilihat pada
kode dibawah : 
 
#include<conio.h>
#include<stddef.h>
#include<iomanip.h>
 
class seleksi{
static int bil[8];
public :
void seleksi_minimum();
void tampil();
};
 
int seleksi::bil[8]={5,34,32,25,75,42,22,2};
 
void seleksi::tampil(){
  for( int a=0;a<8;a++) cout<<setw(3)<<bil[a];
  cout<<endl<<endl;
}
 
void seleksi::seleksi_minimum(){
  int i,j,smallest,temp;
  for(i=0;i<8-1;i++){
                      smallest = i;
                      for(j=i+1;j<8;j++){
                                        if(bil[smallest]>bil[j]){
                                                             smallest=j;
         }
     }
     temp=bil[i];
     bil[i]=bil[smallest];
     bil[smallest]=temp;
  }
}
 
void main(){
  seleksi x;
  cout<<"Data sebelum diurutkan : ";
  x.tampil();
  x.seleksi_minimum();
  cout<<"Data setelah diurutkan : ";
  x.tampil();
  getch();
}
Perhatikan bahwa algoritma diatas sama saja dengan pengurutan seleksi maksimum, hanya saja disini yang dijadikan acuan adalah data terkecil (smallest), sehingga “gelar” disini bukan lagi imax, melainkan smallest.
Contoh lain penggunaan algoritma selection sort , kita gunakan PHP, sebagai  berikut :
<html>
<head><title>$ Sorting Algorithm $</title></head>
<body>
<h2>Algoritma Selection Sort</h2>
<font size=4>
<?PHP
//data awal
$data[0]=5; $data[3]=7;
$data[1]=2; $data[4]=6;
$data[2]=4; $data[5]=3;
echo"<b>Jumlah Data : 6</b><br>";
echo"<b>Data Awal : </b>";
//menampilkan data awal
for($i=0;$i<=5;$i++)
{
echo"$data[$i] ";
}
echo"<br><br>";
//——–Algoritma Selection Sort
for($j=0;$j<=5-1;$j++)
{
$BilMin=$data[$j];
for($k=$j+1;$k<=5;$k++)
{
if($data[$k]<$BilMin)
{
$BilMin=$data[$k];
$Posisi=$k;
}
//Algo Tukar…
$Temp=$data[$j];
$data[$j]=$data[$Posisi];
$data[$Posisi]=$Temp;
}
//menampilkan data tiap Iterasi
$NoIte=$j+1;
echo"Iterasi ke-$NoIte : ";
for($i=0;$i<=5;$i++)
{
echo"$data[$i] ";
}
echo"<br>";
//——-
}
?>
</font>
</body>
</html>

Metode Insertion Sort

Metode Insertion Sort ada 2 jenis,yaitu  :
1.    Metode Penyisipan Langsung
2.    Metode Penyisipan Biner

Penjelasan materi tersebut sebagai berikut.

Metode Penyisipan Langsung (Straight Insertion Sort)

Proses pengurutan dengan metode penyisipan langsung dapat dijelaskan sebagai berikut :
Data dicek satu per satu mulai dari yang kedua sampai dengan yang terakhir. Apabila
ditemukan data yang lebih kecil daripada data sebelumnya, maka data tersebut disisipkan
pada posisi yang sesuai. Akan lebih mudah apabila membayangkan pengurutan kartu.
Pertama-tama anda meletakkan kartu-kartu tersebut di atas meja, kemudian melihatnya
dari kiri ke kanan. Apabila kartu di sebelah kanan lebih kecil daripada kartu di sebelah
kiri, maka ambil kartu tersebut dan sisipkan di tempat yang sesuai.
Algoritma penyisipan langsung dapat dituliskan sebagai berikut :
1. i 1
2. selama (i < N) kerjakan baris 3 sampai dengan 9
3. x Data[i]
4. j i – 1
5. selama (x < Data[j]) kerjakan baris 6 dan 7
6. Data[j + 1] Data[j]
7. j j – 1

8. Data[j+1] x
9. i i + 1

Untuk lebih memperjelas langkah-langkah algoritma penyisipan langsung dapat
dilihat pada tabel 6.1. Proses pengurutan pada tabel 6.1 dapat dijelaskan sebagai
berikut:
Pada saat i=1, x sama dengan Data[1] = 35 dan j=0. Karena Data[0] = 12 dan 35 > 12
maka proses dilanjutkan untuk i=2.
Pada saat i=2, x = Data[2] = 9 dan j=1. Karena Data[1] = 35 dan 9 < 35, maka
dilakukan pergeseran sampai ditemukan data yang lebih kecil dari 9. Hasil
pergeseran ini, Data[1] = 12 dan Data[2] = 35 sedangkan Data[0] = x = 9.
Pada saat i=3, x = Data[3] = 11 dan j=3. Karena Dataa[2] = 35 dan 11 < 35, maka
dilakukan pergeseran sampai ditemukan data yang lebih kecil dari 11. Hasil
pergeseran ini, Data[2] = 12 dan Data[3] = 35 sedangkan Data[1] = x = 11.
Dan seterusnya.

Di bawah ini merupakan prosedur yang menggunakan metode penyisipan
langsung.
void StraighInsertSort()
{
int i, j, x;
for(i=1; i<Max; i++){
x = Data[i];
j = i - 1;
while (x < Data[j]){

Data[j+1] = Data[j];
j--;
}
Data[j+1] = x;
}
}

Prosedur Pengurutan dengan Metode Penyisipan Langsung

Dari algoritma dan prosedur diatas, jumlah perbandingan (=C) minimum, rata-rata dan maksimum pada metode penyisipan langsung adalah
Cmin = N – 1
Crata-rata = (N2 + N + 2) / 4
Cmax = (N2 + N – 2) / 2
Jumlah perbandingan minimum terjadi jika data sudah dalam keadaan urut,
sebaliknya jumlah perbandingan maksimum terjadi jika data dalam keadaan urut terbalik.
Cara menghitung Cmin adalah dengan melihat kalang paling luar yaitu i,
pengulangan ini dimulai dari 1 sampai dengan N-1 atau sama dengan N-1
Cara menghitung Cmax dengan menganggap selalu terjadi pergeseran. Kalang
dalam (while) diatas akan melakukan pengulangan dari 0 sampai dengan i. Apabila hal
ini dilakukan sebanyak N-1 kali, maka Cmax adalah jumlah dari deret aritmetik 2, 3, 4, ..., N atau (N – 1) / 2 . (2 + N)
Cara menghitung Crata-rata adalah dengan menjumlahkan Cmin dan Cmax dan dibagi dengan 2. Jumlah penggeseran (=M) minimum, rata-rata dan maksimum untuk metode penyisipan langsung adalah :
Mmin = 2(N – 1)
Mrata-rata = (N2 + 7N - 8) / 4
Mmax = (N2 + 3N – 4) / 2

Metode Penyisipan Biner (Binary Insertion Sort)

Metode ini merupakan pengembangan dari metode penyisipan langsung. Dengan cara penyisipan langsung, perbandingan selalu dimulai dari elemen pertama (data ke-0), sehingga untuk menyisipkan elemen ke i kita harus melakukan perbandingan sebanyak i-1 kali. Ide dari metode ini didasarkan pada kenyataan bahwa pada saat menggeser data ke-i, data ke 0 s/d i-1 sebenarnya sudah dalam keadaan terurut. Sebagai contoh pada tabel 6. Dengan demikian posisi dari data ke-i sebenarnya dapat ditentukan dengan pencarian biner.
Misalnya pada saat i = 7, data yang akan dipindah adalah 15 sedangkan data di
sebelah kiri 15. 

Pertama-tama dicari data pada posisi paling tengah diantara data diatas. Data
yang terletak di tengah adalah data ke-3, yaitu 12. Karena 12 < 15, berarti 15 harus
disisipkan di sebelah kanan 12.

Dari hasil ini, didapat data tengahnya adalah data 23. Karena 15 < 23, berarti 15 harus
disisipkan di sebelah kiri 23. 

Karena 17 > 15, berarti 15 harus disisipkan di sebelah kiri 17. Algoritma penyisipan biner dapat dituliskan sebagai berikut :
1. i 1
2. selama (i < N) kerjakan baris 3 sampai dengan 14
3. x Data[i]
4. l 0
5. r i – 1
6. selama (l<=r) kerjakan baris 7 dan 8
7. m (l + r) / 2
8. jika (x < Data[m]) maka r m – 1, jika tidak l m + 1
9. j i – 1
10. selama ( j >=l) kerjakan baris 11 dan 12
11. Data[j+1] Data[j]
12. j j – 1
13. Data[l] x
14. I i + 1

Di bawah ini merupakan prosedur yang menggunakan metode penyisipan biner.

void BinaryInsertSort()
{
int i, j, l, r, m, x;
for (i=1; i<Max; i++){
x = Data[i];
l = 0;
r = i - 1;
while(l <= r){
m = (l + r) / 2;
if(x < Data[m])
r = m - 1;
else
l = m + 1;
}
for(j=i-1; j>=l; j--)
Data[j+1] = Data[j];
Data[l]=x;
}
}