ALGORITMA DAN STRUKTUR DATA : BAB 12

SORTING (1)

12. 1 Sorting

Sorting / pengurutan adalah suatu proses untuk mengurutkan elemen-elemen berdasarkan key /
kunci tertentu. Tujuan dari sorting adalah agar mudah dan cepat dalam melakukan pencarian /
searching.
Dalam kehidupan sehari-hari banyak sekali contoh yang dapat diberikan tentang sorting ini,
misalnya Absen Mahasiswa diurutkan / disort berdasarkan NIM , Daftar Dosen diurutkan berdasarkan
Kode Dosen. Urutan dalam sorting :
• Bisa dilakukan secara menaik dari kecil ke besar ( Ascending ), yang berarti elemen dengan
key yang kecil akan berada diatas dari elemen dari key yang lebih besar atau

• Bisa dilakukan secara menurun dari besar ke kecil ( Descending ), yang berarti elemen
dengan key besar akan berada di atas elemen dengan key yang lebih kecil.
Teknik melakukan sorting ini cukup banyak , yang dapat dikelompokkan dalam 3 (tiga) kelompok,
yaitu :

1. Simple Sort Techniques
• Exhange sort / Bubble Sort
• Selection Sort
• Insertion Sort

2. Advanced Sort Techniques
• Heap Sort
• Quick Sort
• Merge Sort

12. 1.1 Exchange / Bubble Sort

Exchange Sort melakukan pengurutan dengan membandingkan elemen dengan elemen berikutnya.
Jika elemen sekarang ternyata lebih besar ( untuk Ascending Sort ) dibandingkan dengan elemen
berikutnya,maka dilakukan pertukaran tempat (SWAP). Dibawah ini disajikan contoh dalam
melakukan Exhange Sort.
Contoh : Apabila terdapat daftar angka 390, 205, 182, 45, 235, lakukan sorting dengan teknik
Exchange Sort.

GambarGambar

Prosedure untuk melakukan Exchange Sort adalah sebagai berikut :

#define Nmaks 1000;
typedef int LarikInt[Nmaks+1];
void ExchangeSort (LarikInt *L, int N)
{
int I;
int K;
int Temp;
for (I=1; I <=N-1; I++)
for (K = N; K>= I+1; K–)
if (*L[K] < *L[K-1])
{
Temp = *L[K];
*L[K] = *L[K-1];
*L[K-1] = Temp;
}
}

12.1.2 Selection Sort

Konsep dasar dalam melakukan pengurutan dengan teknik selection sort adalah dengan memilih nilai
terkecil dari nilai-nilai yang akan diurutkan. Dibawah ini disajikan contoh secara bertahap mengenai
proses Selection Sort.
Contoh bila diketahui list angka 390, 205, 182, 45, 235 dilakukan sorting dengan teknik Selection Sort.

Gambar

 

Langkah-langkahnya adalah sebagai berikut :

1. Dari list angka ambil yang paling kecil, yaitu angka 45, tukar tempat antara 45 dengan
elemen yang berada pada tempat pertama, yaitu angka 390, berarti sudah ada 1 angka (
yaitu 45 ) yang diurut, yang ditandai dengan garis bawahnya.

2. Dari list angka yang belum sort ( dari 205,182,,390,235 ) ambil angka yang paling kecil.
Yaitu angka 182. tukar tempat antara 182 dengan angka pada posisi kedua, yaitu 205.
berarti sudah ada 2 angka ( yaitu 45 dan 182 ) yang sudah urut.

3. dstnya
Prosedur untuk melakukan Selection Sort adalah sebagai berikut :

#define Nmaks 1000;
typedef int LarikInt[Nmaks+1];
void selectionsort(LarikInt *L, int N);
{
int I;
int J;
int Imin;
int Temp;
for (I=1; I<=N-1; I++)
{
Imin = I;
for (J=I+1; J<=N; J++)
if (*L[J] < *L[Imin])
Imin = J;
Temp = *L[Imin];
*L[Imin] = *L[I];
*L[I] = Temp;
}
}

12.1.3 Insertion Sort

Insertion Sort dilakukan dengan menambahkan satu demi satu elemen ke dalam list elemen-elemen
yang telah terurut, sehingga data tepat sorted. Berikut diberikan ilustrasi secara bertahap dalam
melakukan Insertion Sort.

Contoh : untuk list angka yang sama seperti diatas, yaitu : 390, 205, 182, 45, 235 lakukan
Sorting dengan teknik Insertion Sort

Gambar

Langkah pengerjaan Insertion Sort adalah sebagai berikut :

1. Ambil 2 angka yang paling bawah , yaitu 45 dan 235, lakukan pengurutan terhadap kedua
angka tersebut.

2. Tambahkan 1 angka lagi ke dalam list data yang sudah terurut, yang menjadi 182, 45, 235
lakukan pengurutan terhadap list data ini.

3. dstnya.
Prosedur untuk melakukan Insertion Sort adalah sebagai berikut :
#define Nmaks 1000;
typedef int LarikInt[Nmaks+1];
void InsertionSort(LarikInt *L, int N)
{
typedef enum{true=1, false=0} boolean;
int I;
int J;
int x;

boolean ketemu;
for (I=2; I<=N; I++)
x = *L[I];
J = I-1;

ketemu = false;
while (J >= 1) && (! ketemu)
{
if (x < *L[J])
{
*L[J+1] = *L[J];
J—;
}
else
ketemu = true;
}
*L[J+1] = x;
}
}

Iklan

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s