Insertion Sort

Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan (meja pertama), dan yang telah diurutkan (meja kedua). Elemen pertama yang diambil dari bagian array yang belum diurutkan dan kemudian diletakkan pada posisinya sesuai dengan bagian lain dari array yang telah diurutkan. langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang tersisa pada bagian array yang belum diurutkan.

source code:

void insertsort (int x[], int n)

{

int i, k, y

for (k=1, ky=x [k];
for (i=k-1;i>=0&&y
x[i+1]=y;
}
}

#include <iostream.h>
#include <conio.h>

int data[10],data2[10]; int n;
void tukar(int a, int b) {
 int t;
 t = data[b];
 data[b] = data[a];
 data[a] = t;
}

void insertion_sort()
{
 int temp,i,j;
 for(i=1;i<=n;i++)
 {
  temp = data[i];
  j = i -1;
  while(data[j]>temp && j>=0)
  {
   data[j+1] = data[j];
   j--;
  }
 data[j+1] = temp;
 }
}
void main()
{
 cout<<"===PROGRAM INSERTION SORT==="<<endl;

 //Input Data
 cout<<"Masukkan Jumlah Data : ";
 cin>>n;
 for(int i=1;i<=n;i++)
 {
  cout<<"Masukkan data ke "<<i<<" : ";
  cin>>data[i];
  data2[i]=data[i];
 }

 insertion_sort();

 cout<<"\n\n";
 //tampilkan data
 cout<<"Data Setelah di Sort : ";
 for(int i=1; i<=n; i++)
 {
  cout<<" "<<data[i];
 }
 cout<<"\n\nSorting Selesai";
 getch();
}

Selection Sort

Selection Sort

Merupakan Kombinasi antara sorting dan searching. Metode selection sort merupakan perbaikan dari metode bubble sort dengan mengurangi jumlah perbandingan. Selection sort merupakan metode pengurutan dengan mencari nilai data terkecil dimulai dari data diposisi 0 hingga diposisi N-1. Jika terdapat N data dan data terkoleksi dari urutan 0 sampai dengan N-1. Selama proses, perbandingan dan pengubahan, hanya dilakukan pada indeks permbandingnya saja, pertukaran data secara fisik terjadi pada akhir proses.sesuai dengan itu maka algoritma pengurutan data secara Selection adalah sebagai berikut :

1. Cari data terkecil dalam interval j = 0 sampai dengan j = N-1
2. Jika pada posisi pos ditemukan data yang terkecil, maka tukarkan data diposisi pos dengan data di posisi i jika k.
3. Ulangi langkah 1

misalkan bila diketahui data sebagai berikut :
35,75,69,58,21,40
Maka proses pengurutan datanya akan dijelaskan pada
tabel berikut

1	2	3	4	5	6	POSISI DATA
35	75	69	58	21	40	tukar data 1 dengan 5
21	75	69	58	35	40	tukar data 2 dengan 5
21	35	69	58	75	40	tukar data 3 dengan 6
21	35	40	58	75	68	tukar data 5 dengan 6
21	35	40	58	68	75	Selection Sort Berhenti Bekerja

Berikut ini adalah algoritma dari Selection Lost yang menggunakan jenis sorting asscending dan descending

---

Selection Sort Dengan Asscending

---

Procedure acending_Selection;
Var I,j,pos:byte;
Begin
for i:=1 to max-1 do
begin
pos:=I;
for j:=i+1 to max do
if data[j] < data[pos] then pos:=j;
if ipos then tukardata(data[i],data[pos])
end;
End;

---

Selection Sort Dengan Descending

---

Procedure desending_Selection;
Var I,j,pos:byte;
Begin
 for i:=1 to max-1 do
 begin
  pos:=I;
  for j:=i+1 to max do
  if data[pos] < data[j] then pos:=j;
  if ipos then
  tukardata(data[i],data[pos])
 end;
End;

Bubble Sort

Bubble sort merupakan salah satu jenis sorting. Bubble sort ada metode sorting termudah. Diberikan nama “bubble” karena konsep dari algoritmanya diibaratkan seperti gelembung air untuk elemen struktur data yang seharusnya pada posisi awal. Bubble sort mengurut data dengan cara membandingkan elemen sekarang dengan elemen berikutnya. Dimana cara kerjanya adalah dengan berulang-ulang melakukan proses looping ( perulangan) terhadap elemen-elemen struktur data yang belum diurutkan. Nilai dari masing-masing elemen akan dibandingkan selama proses looping tersebut .jika selama proses looping tersebut ditemukan ada urutannya tidak sesuai dengan permintaan, maka akan dilakukan proses pemukaran (swap). Sesungguhnya secara tidak langsung, algoritma dari program ini seolah-olah menggeser satu demi satu elemen dari kanan ke kiri atau dari kiri ke kanan tergantung pada jenis pengurutannya. Perlu diketahui, jenis pengurutan sorting ada 2 yaitu asscending dan descending. Dimana asscending itu mengurut data dari kecil ke besar dan descending itu mengurut data dari besar ke kecil. Jika semua elemen sudah diperiksa oleh fungsi bubble sort, dan tidak ada pertukaran lagi atau semua nilai sudah sesuai, maka saat itu program bubble sort akan berhenti bekerja. Misalkan jika ada data 22 10 15 3 8 2. Data tersebut masih dalam keadaan acak. Maka ilustrasi pengurutan dengan bubble sortnya akan terlihat seperti pada table dibawah ini :

LANGKAH 1 :

1	2	3	4	5	6	POSISI DATA
22	10	15	3	8	2	Data Awal
22	10	15	3	2	8	tukar data 5 dengan 6
22	10	15	2	3	8	tukar data 4 dengan 3
22	10	2	15	3	8	tukar data 3 dengan 2
22	2	10	15	3	8	tukar data 2 dengan 1
2	22	10	15	3	8	LANGKAH 1 SELESAI

LANGKAH 2 :

1	2	3	4	5	6	POSISI DATA
2	22	10	15	3	8	Data Langkah 1 Akhir
2	22	10	3	15	8	tukar data 4 dengan 3
2	22	3	10	15	8	tukar data 3 dengan 2
2	3	22	10	15	8	LANGKAH 2 SELESAI

LANGKAH 3 :

1	2	3	4	5	6	POSISI DATA
2	3	22	10	15	8	Data Langkah 2 Akhir
2	3	22	10	8	15	tukar data 5 dengan 6
2	3	22	8	10	15	tukar data 4 dengan 3
2	3	8	22	10	15	LANGKAH 3 SELESAI

LANGKAH 4 :

1	2	3	4	5	6	POSISI DATA
2	3	8	22	10	15	Data Langkah 3 Akhir
2	3	8	22	10	15	tukar data 5 dengan 4
2	3	8	10	22	15	LANGKAH 4 SELESAI

LANGKAH 5 :

1	2	3	4	5	6	POSISI DATA
2	3	8	10	22	15	Tukar data 5 dengan 6
2	3	8	10	15	22	TERURUT

Prosedur pertukaran data Procedure tukar (var a,b:word); Var c:word; Begin c:=a; a:=b; b:=c; End; prosedur bubble sort dengan jenis sort accending Procedure asending_Buble(var data:array; jmldata:integer); Var I,j:integer; Begin for i:=2 to jmldata do for j:=jmldata downto I do if data[j]< data{j-1] then tukardata(data[j], data[j-1]) End; Prosedur Bubble sort secara descending Procedure decending_Buble(var data:array; jmldata:integer); Var I,j:integer; Begin for i:=2 to jmldata do for j:=jmldata downto I do if data[j] >data{j-1] then tukardata(data[j], data[j-1]) End;

Merge Sort

Algoritma Merge adalah algoritma yang dijalankan sebagai akibat dari terlalu banyaknya daftar yang diurutkan, dengan menghasilkan lebih banyak daftar yang diurutkan sebagai output. Algoritma merge ini disesuaikan untuk mesin drive tape. Penggunaannya dalam akses memori acak besar yang terkait telah menurun, karena banyak aplikasi algoritma merge yang mempunyai alternatif lebih cepat ketika kamu memiliki akses memori acak yang menjaga semua data mu. Hal ini disebabkan algoritma ini membutuhkan setidaknya ruang atau memori dua kali lebih besar karena dilakukan secara rekursif dan memakai dua tabel.

Algoritma merge sort membagi tabel menjadi dua tabel yang sama besar. Masing-masing tabel diurutkan secara rekursif, dan kemudian digabungkan kembali untuk membentuk tabel yang terurut. Implementasi dasar dari algoritma merge sort memakai tiga buah tabel, dua untuk menyimpan elemen dari tabel yang telah di bagi dua dan satu untuk menyimpan elemen yang telah terurut. Namun algoritma ini dapat juga dilakukan langsung pada dua tabel, sehingga menghemat ruang atau memori yang dibutuhkan.

Algoritma Merge umumnya memiliki satu set pointer p_0..n yang menunjuk suatu posisi di dalam satu set daftar L_0..n . Pada awalnya mereka menunjuk item yang pertama pada setiap daftar. Algoritmanya sebagai berikut:

Selama p_0..n masih menunjuk data yang di dalam sebagai pengganti pada akhirnya:

1. Melakukan sesuatu dengan data item yang menunjuk daftar mereka masing-masing.
2. Menemukan pointers points untuk item dengan kunci yang paling rendah; membantu salah satu pointer untuk item yang berikutnya dalam daftar.

Algoritma Merge Sort ialah algoritma pengurutan yang berdasarkan pada strategi divide and conquer.

Algoritma untuk merge sort ialah sebagai berikut :

1. Untuk kasus n=1, maka table a sudah terurut sendirinya (langkah solve)

2. Untuk kasus n>1, maka :

a. DIVIDE: bagi table a menjadi dua bagian, bagian kiri dan bagian kanan, masing-masing bagian berukuran n/2 elemen.

b. CONQUER: secara rekursif, terapkan algoritma D-and-C pada masing-masing bagian.

MERGE: gabung hasil pengurutan kedua bagian sehingga diperoleh table a yang terurut.

Contoh kasus:

Algoritma

Procedure MergeSort(input/output A : TabelInt, input i, j : integer)

{ Mengurutkan tabel A[i..j] dengan algoritma Merge Sort

Masukan: Tabel A dengan n elemen

Keluaran: Tabel A yang terurut

}

Deklarasi:

k : integer

Algoritma:

if i { Ukuran(A)> 1}

k←(i+j) div 2

MergeSort(A, i, k)

MergeSort(A, k+1, j)

Merge(A, i, k, j)

Endif

Quick Sort

Algoritma Quick Sort

Dalam algoritma quick sort, pemilihan pivot adalah hal yang menentukan apakah algoritma quick sort tersebut akan memberikan performa terbaik atau terburuk. Berikut beberapa cara pemilihan pivot :

1. Pivot adalah elemen pertama, elemen terakhir, atau elemen tengah tabel. Cara ini hanya bagus jika elemen tabel tersusun secara acak, tetapi tidak bagus jika elemen tabel semula sudah terurut. Misalnya, jika elemen tabel semula menurun, maka semua elemen tabel akan terkumpul di upatabel kanan.

2. Pivot dipilih secara acak dari salah satu elemen tabel. Cara ini baik, tetapi mahal, sebab memerlukan biaya (cost) untuk pembangkitan prosedur acak. Lagi pula, itu tidak mengurangi kompleksitas waktu algoritma.

3. Pivot adalah elemen median tabel. Cara ini paling bagus, karena hasil partisi menghasilkan dua bagian tabel yang berukuran seimbang (masing masing ≈ n/2 elemen). Cara ini memberikan kompleksitas waktu yang minimum. Masalahnya, mencari median dari elemen tabel yang belum terurut adalah persoalan tersendiri.

Algoritma Quick Sort terdiri dari dua prosedur, yaitu prosedur PARTISI dan prosedur QUICKSORT. Berikut pseudocode dari algoritma quick sort :

Procedure QuickSort (input/output a : array [1..n] of integer, input i , j : integer )

{mengurutkan tabel a[i..j] dengan algoritma quick sort. Masukkan: Tabel a[i..j] yang sudah

terdefinisi elemen-elemennya. Keluaran: Tabel a[i..j] yang terurut menaik.}

Deklarasi :

k : integer;

Algoritma :

if (i<j) then

Partisi(a,i,j,k) { Ukuran (a) > 1}

QuickSort(a,i,k)

QuickSort(a,k+1, j)

Endif

Procedure Partisi (input/output: a : array[1..n] of integer, input i , j : integer, output q : integer)

{Membagi tabel a[i..j] menjadi subtabel a[i..q] dan a[q+1..j]. Keluaran upatabel a[i..q] dan subtabel a[q+1..j]. Sedemikian sehingga elemen tabel a[i..q] lebih kecil dari elemen tabel a[q+1..j]}

Deklarasi :

Pivot, temp : integer

Algoritma :

Pivot <- A[(i+j) div 2] { pivot = elemen tengah }

p <- i

q <- j

repeat

while a[p] < pivot do

p <- p + 1

endwhile

{ Ap >= pivot }

while a[q] > pivot do

q <- q – 1

endwhile

{ Aq >= pivot }

if (p _ q) then

{ pertukarkan a[p] dengan a[q]}

temp <- a[p]

a[p] <- a[q]

a[q] <- temp

{ tentukan awal pemindaian berikutnya}

p <- p+ 1

q <- q – 1

endif

until p > q

Kompleksitas Algoritma Quick Sort

Kebutuhan waktu dari quicksort bergantung pada pembuatan partisi, seimbang atau tidak, yang bergantung juga pada elemen yang digunakan sebagai pivot. Dalam menghitung kompleksitas ini, perlu dilihat pula perhitungan recurrence, karena terdapat fungsi rekursif untuk penyelesaian sub-masalah.

Terdapat 3 jenis kompleksitas waktu dari quicksort:

1. Kasus terburuk (worst case), yaitu terjadi bila terbentuk partisi dengan komposisi sub-masalah antara n – 1 elemen dan 0 elemen. Dengan demikian pemanggilan fungsi secara rekursif dengan array berukuran 0 akan langsung kembali, T(0) = Θ(1), sehingga berlaku: T(n) = T(n – 1) + cn = O(n²).
2. Kasus terbaik (best case), yaitu terjadi bila terbentuk partisi dengan dengan komposisi seimbang, dengan ukuran masing-masing tidak lebih dari n/2. Sehingga didapat: T(n) = 2T(n/2) + cn = na + cn log n = O(n log n).
3. Kasus rata-rata (average case), yaitu terjadi dari perimbangan pivot antara terbaik dan terburuk, yang dalam prakteknya lebih mendekati kasus terbaik ketimbang terburuk. Sehingga didapat: T_avg(n) = O(n log n).

Kelebihan dan Kelemahan Algoritma Quick Sort

Beberapa hal yang membuat quick sort unggul:

• Secara umum memiliki kompleksitas O(n log n).
• Algoritmanya sederhana dan mudah diterapkan pada berbagai bahasa pemrograman dan arsitektur mesin secara efisien.
• Dalam prakteknya adalah yang tercepat dari berbagai algoritma pengurutan dengan perbandingan, seperti merge sort dan heap sort.
• Melakukan proses langsung pada input (in-place) dengan sedikit tambahan memori.
• Bekerja dengan baik pada berbagai jenis input data (seperti angka dan karakter).

Namun terdapat pula kelemahan quick sort:

• Sedikit kesalahan dalam penulisan program membuatnya bekerja tidak beraturan (hasilnya tidak benar atau tidak pernah selesai).
• Memiliki ketergantungan terhadap data yang dimasukkan, yang dalam kasus terburuk memiliki kompleksitas O(n²).
• Secara umum bersifat tidak stable, yaitu mengubah urutan input dalam hasil akhirnya (dalam hal inputnya bernilai sama).
• Pada penerapan secara rekursif (memanggil dirinya sendiri) bila terjadi kasus terburuk dapat menghabiskan stack dan memacetkan program.

Implementasi Algoritma Quick Sort

Berikut adalah implementasi dari quick sort dalam bahasa C. Implementasinya terbagi menjadi dua prosedur, yaitu prosedur partisi dan prosedur quicksort.

void quicksort(int x[], int first, int last) {

int pivIndex = 0;

if(first < last) {

pivIndex = partition(x,first, last);

quicksort(x,first,(pivIndex-1));

quicksort(x,(pivIndex+1),last);

}

}

int partition(int y[], int f, int l) {

int up,down,temp;

int piv = y[f];

up = f;

down = l;

goto partLS;

do {

temp = y[up];

y[up] = y[down];

y[down] = temp;

partLS:

while (y[up] <= piv && up < l) {

up++;

}

while (y[down] > piv  && down > f ) {

down–;

}

} while (down > up);

y[f] = y[down];

y[down] = piv;

return down;

}

Sorting dan Searching

 Teknik Sorting

Sorting bisa didefinisikan sebagai suatu proses pengurutan data yang
sebelumnya disusun secara acak sehingga menjadi tersusun secara teratur menurut
suatu aturan tertentu. Sorting yang kita terapkan menggunakan tipe data array agar
pemahaman serta pengimplementasiannya lebih mudah. Pada umumnya terdapat
dua jenis pengurutan :
- Ascending (Naik).
- Descending (Turun).
Contoh :
Data : Array [1..6] of Byte = (22, 10, 15, 3, 8, 2);
Data Acak : 22 10 15 3 8 2
Terurut Ascending : 2 3 8 10 15 22
Terurut Descending : 22 15 10 8 3 2

Metode Pengurutan Data
- Pengurutan berdasarkan perbandingan (comparison-based sorting)
• Bubble sort, exchange sort
- Pengurutan berdasarkan prioritas (priority queue sorting method)
• Selection sort, heap sort
- Pengurutan berdasarkan penyisipan dan penjagaan terurut (insert and keep
sorted method)
• Insertion sort, tree sort
- Pengurutan berdasarkan pembagian dan penguasaan (devide and conquer
method)
• Quick sort, merge sort
- Pengurutan berkurang menurun (diminishing increment sort method)
• Shell sort

Teknik Searching
Searching merupakan suatu proses pendarian data dari sejumlah data yang
ada. Pencarian data dapat dilakukan pada sejumlah data yang sudah terurut atau
juga pada data yang sama sekali belum terurut. Kita mencoba menggunakan dua
metode pencarian yaitu :
- Pencarian Berurutan (Sequential Searching).
Metode ini merupakan metode paling sederhana, secara garis besar metode
ini bisa dijelaskan sebagai berikut. Dari data yang diketahui, data yang dicari
dibandingkan satu per satu sampai data tersebut ditemukan atau tidak ditemukan.
Pada saat data yang dicari sudah ditemukan, maka proses pencarian langsung
dihentikan. Tetapi jika belum ditemukan, maka pencarian diteruskan sampai
seluruh data dibandingkan.

- Pencarian Biner (Binary Seacrh).
Metode ini digunakan jika sejumlah data telah diurutkan. Jika dibandingkan
dengan metode awal tadi metode ini jauh lebih cepat. Secara garis besar metode
ini bisa dijelaskan sebagai berikut. Urutkan dahulu sejumlah data. Lalu bagi dua
data-data tadi dengan jumlah data yang sama pada masing-masingnya. Kemudian
data dibandingkan dengan data terakhir dari subdata yang pertama. Jika data yang
dicari lebih keci, pencarian dilanjutkan pada sub data pertama dengan terlebih
dahulu membagi dua lagi data-data tersebut dengan jumlah yang sama. Tetapi jika
data yang dicari lebih besar dari data terakhir subdata pertama, berarti data yang
dicari kemungkinan terletak pada subdata yang kedua. Proses diatas dilakukan
berulang sampai data ditemukan atau tidak ditemukan.