Sortir Penyisipan (Insertion Sort)

Nama : Rayhan Fadhillah

NPM  : 45118943

Kelas : 1DC02

Mata Kuliah : Algoritma & Pemrograman A

Dosen : Kunto Bayu A, ST

Sorting adalah proses menyusun elemen – elemen dengan tata urut tertentu dan proses tersebut terimplementasi dalam bermacam aplikasi. Pengaplikasian sorting banyak kita jumpai diberbagai aktifitas, misal mengurutkan NIM, Nama negara, Kota dan Lain sebagainya.

Secara umum, sortir dapat dilakukan terhadap suatu urutan bilangan, ataupun urutan abjad.

Ada 2 kategori sortir berdasarkan media yang digunakan, yaitu :

1. Sortir Internal

    Data yang akan disortir kecil, sehingga proses Sortir tidak membutuhkan tempat yang besar di memori utama komputer.

2. Sortir Eksternal

    Data yang disortir cukup besar , sehingga membutuhkan media atau alat tambahan, seperti Magnetik tape, disket dan sebagainya.
Dua hal yang sangat mempengaruhi kecepatan Algoritma Sortir, yaitu :

1. Jumlah operasi perbandingan yang dilakukan.

2. Jumlah operasi pemindahan data dilakukan.

Ada beberapa teknik yang dapat dilakukan dalam melakukan Sortir, yaitu :

1. Sortir Penyisipan (Insertion Sort)

2. Sortir Pemilihan (Selection Sort)

3. Sortir Penukaran (Exchange Sort)
4. Merge Sort
5. Heap Sort
6. Quick Sort
7. Bucket Sort
8. Radix Sort
9. Shell Sort
10. Shuffle Sortf

1. Sortir Penyisipan (Insertion Sort)

Prinsip dasar metode ini adalah secara berulang-ulang memasukkan setiap data ke dalam tempatnya yang benar.

Algoritmanya :

          For i := 2 to n do

                Begin

                x := a[i]

                Lalu letakkan x pada tempat yang benar dalam urutan a[1] .. a[i]

                End

Untuk memasukkan x ke dalam tempat yang sebenarnya maka harus dilakukan perbandingan-perbandingan dan pemindahan-pemindahan secara bergantian.

Jadi x akan bergeser ke kiri dengan membandingkan  nilai x dengan nilai a[j] berikutnya dan kemudian x di-insert ke dalam tempatnya atau a[j] dipindahkan ke kanan.

Hal ini diteruskan untuk unsur-unsur di sebelah kiri a[j].

Proses ini akan  berhenti bila salah satu dari kedua hal ini berlaku, yaitu :

1. Salah satu unsur a[j] mempunyai key yang lebih kecil dari x.

2. Bagian ujung kiri tabel telah dicapai.

Prosedur Insertion :

Kompleksitas Algoritma Sortir Penyisipan

	C  (Jumlah Operasi    Perbandingan)	M (Jumlah Pemindahan           Data)
Hal Terbaik (Best Case)	n - 1	2 (n -1)
Rata-rata (Average Case)	(n2 + 3n - 4) / 4	(n2 + 7n - 8) / 4
Hal Terburuk (Worst Case)	(n2 + n ) / 2-1	(n2 + 3n - 4) / 2

Keadaan terbaik bila data awal sudah terurut dari kecil ke besar.

Keadaan terburuk terjadi bila data pada saat awal mempunyai urutaan terbalik dari besar ke kecil.

Sumber : sariny.staff.gunadarma.ac.id/Downloads/files/.../BAB+6+TSORTIR.DOC
                 http://includeryokom.blogspot.com/2012/04/jenis-jenis-penyortiran-beserta.html