1. Jelaskan maksud dari Bubble Sort, Exchange Sort, Selection Sort, Heap Sort, Insertion Sort, Tree Sort, Quick Sort, Merge Sort, Shell Sort.
2. Tuliskan pula algoritma dari 9 metode tersebut?
Macam – Macam Metode Sorting Serta Prosedur/Algoritma/Syntaxnya (Struktur Data)
A. Bubble Sort
Bubble sort (metode gelembung) adalah metode pengurutan dengan dengan cara melakukan penukaran data dengan tepat disebelahnya secara terus menerus sampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan. Jika tidak ada perubahan berarti data sudah terurut. Disebut pengurutan gelembung karena masing-masing kunci akan dengan lambat menggelembung ke posisinya yang tepat.
Prosedur/Algoritma/Syntax Bubble Sort atau exchange sort :
void BubbleSort()
{
int i, j;
for(i=1; i<Max-1; i++)
for(j=Max-1; j>=i; j--)
if(Data[j-1] > Data[j])
Tukar(&Data[j-1], &Data[j]);
}
B. Exchange Sort
Melakukan pembandingan antara data, dan melakukan pertukaran apabila urutan yang
didapat belum sesuai. Bisa dikatakan Bubble sort sama dengan Exchange Sort karena kedua metode ini melakukan pertukaran berulang-ulang terhadap elemen data yang belum diurutkan.
Prosedur/Algoritma/Syntax Exchange Sort ASSCENDING
for (int i=0; i< 6-1; i++)Prosedur/Algoritma/Syntax Exchange Sort DESCENDING
{
for (int j = (i+1); j data[j])
{
t = data [j];
data [j] = data [i] ;
data [i] = t;
}
for (int i=0; i< 6-1; i++)
{
for (int j = (i+1); j< 6; j++)
{
if (data2[i] < data2[j])
{
t = data2[j];
data2[j] = data2[i] ;
data2[i] = t;
}
C. Selection Sort
Algoritma selection sort adalah mencari elemen yang tepat untuk diletakkan di posisi yang telah diketahui, dan meletakkannya di posisi tersebut setelah data tersebut ditemukan. Selection Sort membandingkan elemen yang sekarang dengan elemen yang berikutnya sampai dengan elemen yang terakhir. Jika ditemukan elemen lain yang lebih kecil dari elemen sekarang maka dicatat posisinya dan kemudian ditukar.
Prosedur/Algoritma/Sintaks program fungsi Selection Sort:
void selection_sort(){
for(int i=0;i<n-1;i++){
pos = i;
for(int j=i+1;j<n;j++){
if(data[j] < data[pos])
pos = j; //ascending
}
if(pos != i) tukar(pos,i);
}
}
D. Heap Sort
Heapsort merupakan salah satu bentuk dari selection sort yang memiliki kompleksitas algorima O(n log(n)) yang menggunakan struktur data heap. Algoritma ini bekerja dengan menentukan elemen terbesar (atau terkecil) dari sebuah daftar elemen, dan diletakkan pada akhir (atau awal) dari daftar tersebut. Heap sort menyelesaikan sebuah pengurutan menggunakan struktur data yang disebut heap. Heap merupakan sebuah pohon biner hampir lengkap dimana isi dari simpul ayah selalu lebih besar dari isi simpul anak-anaknya sehingga simpul akar selalu merupakan elemen terbesar.
Prosedur/Algoritma/Syntax Heapsort;
function heapSort(a, count) is
input: sebuah larik tidak terurut a dengan panjang length
(pertama letakkan a dalam max-heap) heapify(a, count)
end := count -1
while end > 0 do
remove ( )
reheapify ( )
end := end – 1
E. 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.
Prosedur/Algoritma/Syntax Insertion sort
void insertion_sort(){
int temp;
for(int 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;
}
}
F. Quick Sort
Pengurutan ini berdasar pada prinsip devide and conquer. Devide adalah suatu langkah memilah masalah menjadi sub – masalah dalam proses rekursi, sedangkan conquer adalah proses menyelesaikan sub masalah tersebut, kemudian dilakukan pendekatan terhadap masalah utama. Pada dasarnya prinsip kerjanya adalah membagi atau memartisi sekumpulan data menjadi dua bagian sedemikian rupa sehingga elemen ke-i berada tepat pada posisisnya, dimana semua elemen yang nilainya lebih kecil daripada elemen ke-i akan terletak disebelah kirinya, sedangkan yang mempunyai nilai lebih besar berada disebelah kanannya. Algoritma ini memiliki kompleksitas O(n log n).
Prosedur/Algoritma/Syntax Quick Sort
void quicksort (int *arr, int kr, int kn)
{
int i, j, k;
if (kr<kn)
{
j=kr;
k=kn+;
do
{
do j++; while (j <= kn && arr[j] < arr[kr]);
do k–; while (arr[k] > arr[kr]);
if (j<k) tukar (&arr[j], &arr[k]);
}
while (j <= k);
tukar (&arr[kr], &arr[k]);
quicksort (arr, kr, k-1);
quicksort (arr, k+1, kn);
} }
G. Merge sort
Merupakan salah satu teknik sorting yang mengurutkan suatu data dengan cara penggabungan. Merge sort juga menggunakan proses divide and conquer pada rekursi. Berikut adalah langkah kerja merge sort :
Devide : Memilah elemen – elemen dari data menjadi dua bagian.
Conquer : Menyelesaikan setiap bagian dengan memanggil prosedur merge sort secara rekursif.
Kombinasi : Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkan rangkaian data berurutan.
Proses rekursi akan berhenti jika telah mencapai elemen dasar, atau artinya jika bagian yang diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen tersebut menandakan bahwa bagian tersebut telah sesuai rangkaian.
Prosedur/Algoritma/Syntax Quick Sort Merge sort
void mergesort (int *x, int n)
{
int *r, i, j, k, l1, l2, u1, u2, size;
r = (int *) malloc (n * sizeof (int));
size = 1;
while (size < n)
{
l1 = 0; k = 0;
while (l1+size < n)
{
l2 = l1+size;
u1 = l2 – 1;
u2 = (l2 + size – 1 < n) ? l2 + size – 1 : n-1;
for (i=l1; j=l2; i<=u1 && j<=u2; k++)
r[k] = (x[i] <= x[j]) ? x[i++] : x[j++];
while (i<=u1) r[k++] = x[i++];
while (j<=u2) r[k++] = x[j++];
l1 = u2+1;
}
for(i=l1; k<n; i++) r[k++] = x[i];
for(i=0; i<n; i++) x[i] = r[i];
size *= 2;
}
free(r); }
H. Shell Sort
Algoritma ini memiliki kesamaan cara kerja dengan insertion sort, yaitu membandingkan elemen-elemen dengan jarak tertentu. Insertion sort membandingkan elemen–elemen data yang berdekatan (berjarak satu posisi), sedangkan shell sort membandingkan elemen berjarak tertentu, misalnya elemen yang berjarak 5 posisi atau 2 posisi dan pada akhirnya akan selesai pada pengurutan data yang berjarak 1 posisi. Namun nilai ini haruslah dicari sedemikian rupa agar tidak menulangi atau merusak hasil sorting sebelumnya.
Prosedur/Algoritma/Syntax Shell Sort
void shellsort (int *r, int lo, int hi)
{
int d, i, j, temp;
for (d = hi – lo + 1; d>1; )
{
if (d>5) d = 1;else d=(5*d – 1)/11;
for (i=hi – d; i>=lo; i–)
{
temp = r[i];
for (j=i+d; (j<=hi) && (temp>r[j]); j+=d)
r[j-d] = r[j];
r[j-d] = temp;
}
}
}