Metode Dalam Sorting :
1. Pengurutan berdasarkan perbandingan
a. Bubble Sort
b. Exchange Sort
2. Pengurutan tanpa perbandingan
a. Radix Sort
3. Pengurutan berdasarkan prioritas
a. Selection Sort
b. Heap Sort
4. Pengurutan berdasarkan penyisipan dan penjagaan terurut
a. Insertion Sort
b. Tree Sort
5. Pengurutan berdasarkan pembagian dan penguasaan
a. Quick Sort
b. Merge Sort
6. Pengurutan berkurang menurun
a. Shell Sort
Contoh Pemrograman Shell Sort, Radix Sort, Quick Sort dan Merge Sort
A. Shell Sort
Misalnya pada contoh kasus Sequence Number (k) = 5, maka sublist nya adalah sebagai berikut :
s[0] s[5] s[10] dst
Proses untuk menentukan yang terjadi pada Shell Sort adalah sebagai berikut :
1. Buat sub list berdasarkan jarak atau sequence number yang telah dipilih.
2. Urutkan masing – masing sub list tersebut
3. Gabungkan seluruh sublist yang ada
4. Disarankan pada jarak awal dari data yang akan dibandingkan yaitu adalah N/2
5. Proses berikutnya, gunakan jarak (N/2)/2 atau N/4
6. Proses selanjutnya gunakan jarak (N/4)/2 atau N/8
7. Demikian seterusnya hingga sequence number yang digunakan tersebut adalah 1.
Misalnya contoh untuk pengurutan Shell Sort :
Data pada array yang telah dibuat sebagai berikut :
*catatan : N adalah jumlah data
K1 = Sequence Number 1 : 8/2 = 4
K2 = Sequence Number 2 : 8/4 = 2
K3 = Sequence Number 3 : 8/8 = 1
Maka telah diperoleh yaitu K1 = 4, K2 = 2, K3 = 1.
Contoh Program Shell Sort pada Pemrograman C++ :
Source Code Shell Sort :
#include<iostream>
#include<conio.h>
#include<stdlib.h>
using namespace std;
int main() {
int array;
cout << “Penerapan algoritma Shell Sortn”;
cout << “Masukkan panjang array: “;cin>>array;
int arr_sorting[array], a, k,j, i, t;
cout << “nMasukkan ” << array << ” Data yang akan diurutkan : ” << endl;
for (i = 0; i < array; i++)
{
cout<<“Data ke- “<<i+1<<“: “;
cin >> arr_sorting[i];
}
cout << “nData anda :”;
for (i = 0; i < array; i++) {
cout << “t” << arr_sorting[i];
}
for (i = array / 2; i > 0; i = i / 2) {
for (j = i; j < array; j++) {
for (k = j – i; k >= 0; k = k – i) {
if (arr_sorting[k + i] >= arr_sorting[k])
break;
else {
t = arr_sorting[k];
arr_sorting[k] = arr_sorting[k + i];
arr_sorting[k + i] = t;
}
}
cout << “nPengulangan Shell Sort ” << i << ” : ” << j;
for (a = 0; a < array; a++) {
cout << “t” << arr_sorting[a];
}
}
}
cout << “nnData yang telah diurutkan dengan algoritma Shell Sort :n”;
for (i = 0; i < array; i++) {
cout << “t” << arr_sorting[i];
}
getch();
}
B. Radix Sort
Langkah – langkah sederhana mengurutkan data dengan menggunakan Radix Sort pada pemrograman :
1. Ambil nilai maksimal dari inputan array yaitu d
2. Mulai dari digit paling kecil, kemudian urutkan data tersebut
3. Ambil data sebagai inputan untuk digit selanjutnya
4. Lakukan pengulangan hingga digit d
5. Tampilkan hasilnya
6. Selesai
Contoh pengurutan dengan menggunakan Radix Sort pada sebuah tipe data String :
Contoh pengurutan dengan menggunakan Radix Sort pada sebuah tipe data Numerik atau Integer :
Contoh Program Radix Sort pada Pemrograman C++ :
Source Code Radix Sort :
#include<stdlib.h>
#include<stdio.h>
#include<conio.h>
#include<iostream>
#define MAX 10
#define DESIMAL 10
void print(int *a, int n)
{
int i;
for (i = 0; i < n; i++)
printf(“%dt”, a[i]);
}
void radixsort(int *a, int n)
{
int i, b[MAX], m = a[0], exp = 1;
for (i = 1; i < n; i++)
{
if (a[i] > m)
m = a[i];
}
while (m / exp > 0)
{
int paket[DESIMAL] = {0};
for (i = 0; i < n; i++)
paket[(a[i] / exp) % DESIMAL]++;
for (i = 1; i < DESIMAL; i++)
paket[i] += paket[i – 1];
for (i = n – 1; i >= 0; i–)
b[–paket[(a[i] / exp) % DESIMAL]] = a[i];
for (i = 0; i < n; i++)
a[i] = b[i];
exp *= DESIMAL;
printf(“nUrutan : “);
print(a, n);
}
}
int main()
{
int arr[MAX];
int i, n;
printf(“Masukkan jumlah data yang akan diurutkan : “, MAX);
scanf(“%d”, &n);
if(n>10)
{
printf(“Data yang dapat dimasukan maksimal 10n”);
system(“PAUSE”);
return 0;
}
n = n < MAX ? n : MAX;
printf(“nMasukkan %d Datan”, n);
for (i = 0; i < n; i++)
{
printf(“Data ke-%d: “,i+1);
scanf(“%d”, &arr[i]);
}
printf(“nARRAY : “);
print(&arr[0], n);
radixsort(&arr[0], n);
printf(“nData Terurut : “);
print(&arr[0], n);
printf(“n”);
system(“PAUSE”);
return 0;
}
C. Merge Sort
Ilustrasi gambar penerapan pada Algoritma Merge Sort :
Dari ilustrasi gambar penerapan Algoritma Merge Sort diatas dapat dijabarkan menggunakan Pseudocode Merge Sort sebagai berikut :
D. Quick Sort
Langkah – Langkah sederhana Metode Algoritma Quick Sort :
Ilustrasi gambar Pengurutan data pada Algoritma Quick Sort :
Data yang akan diurutkan :
{1, 12, 5, 26, 7, 14, 3, 7, 2}
