Pengurutan data dengan metode selection-sort

Dari sekian banyak algoritma pengurutan data, program ini menggunakan algoritma selection-sort karena algoritma ini tidak sulit untuk diimplementasikan dalam program.

Bagian yang penting dalam proses pengurutan ini adalah fungsi pembanding diantara dua buah data. Fungsi ini harus bisa membandingkan data walaupun atribut yang ingin diurutkan/cara pengurutan yang dipilih bisa berbeda-beda. Jadi, hanya dengan satu buah fungsi pembanding, dan satu implementasi selection-sort tadi, dapat dilakukan metode pengurutan yang berbeda-beda.

Fungsi pembanding adalah sebuah fungsi yang dapat memutuskan apakah dua buah data yang dibandingkan harus dibalik atau tidak. Jika fungsi ini mengeluarkan nilai TRUE, maka data harus dibalik.

Dalam program ini, atribut yang dapat diurutkan adalah:

• Nomor

• Nama

• Nama (yang dibalik)

• NPM

• NPM (yang dibalik)

Proses pengurutan berdasarkan nama/npm yang dibalik tidak berbeda dengan proses pengurutan berdasarkan nama/npm yang tidak dibalik. Hanya saja, sebelum dilakukan perbandingan, nama/npm tersebut harus dibalik terlebih dahulu.

Cara pengurutan yang dapat dipilih adalah:

• Urut naik (A sampai Z)

• Urut turun (Z sampai A)

Dalam implemetasi fungsi pembanding data, digunakan fungsi strcmp() untuk melakukan perbandingan nama/npm dan untuk membandingkan nomor urut, hanya digunakan pembanding angka biasa, yaitu lebih besar atau lebih kecil.

Dengan menggunakan fungsi strcmp() untuk membandingkan nama/npm dan tanda lebih besar/lebih kecil untuk membandingkan nomor urut, dapat diperoleh informasi apakah data pertama lebih kecil daripada data kedua atau sebaliknya. Dalam fungsi pembanding ini, diasumsikan data pertama akan selalu lebih besar sama dengan data kedua. Sehingga sampai saat ini, fungsi pembanding akan sukses dalam proses pengurutan dengan cara pengurutan urut naik. Agar fungsi ini dapat digunakan untuk pengurutan naik, nilai perbandingan tadi harus dibalik.

if (atribut pembanding == NAMA) {
 hasil = strcmp(data1->nama, data2->nama) >= 0;
}
else if (atribut pembanding == NPM) {
 hasil = strcmp(data1->npm, data2->npm) >= 0;
}
else {
 hasil = data1->nomor >= data2->nomor;
}

hasil = hasil ^ (cara-pengurutan != URUT_NAIK);

Selain fungsi pembanding, ada satu fungsi lain yang digunakan dalam proses pengurutan yang dipakai dalam program ini, yaitu fungsi penukar data. Dalam program ini, data disimpan dalam sebuah linked-list, dan proses penukaran dua buah data dapat menjadi sulit jika salah dalam memutuskan bagaimana cara menukar data. Daripada menukar node yang tentunya harus memindah-mindahkan lagi pointer dalam node tersebut, akan jauh lebih mudah jika yang ditukar adalah data-data yang ada di dalam node tersebut.

int iTemp;
char *cTemp;

//tukarkan nomor urut
iTemp = data1->index;
data1->index = n2->index;
n2->index = iTemp;

//tukarkan nama
cTemp = data1->name;
data1->name = data2->name;
data2->name = cTemp;

//tukarkan npm
cTemp = n1->npm;
n1->npm = data2->npm;
data2->npm = cTemp;

Setelah fungsi pembanding dan fungsi penukar data dibuat, tentunya algoritma selection-sort juga harus diimplementasikan. Karena program ini menggunakan linked-list untuk menyimpan data, maka algoritma tersebut harus dapat mengurutkan data yang disimpan dengan menggunakan linked-list.

Dalam selection-sort ada dua buah loop yang digunakan, dan karena keduanya merupakan loop maju, maka pengadaptasian algoritma untuk linked-list tidak sulit untuk dibuat.

Pada loop bagian luar, akan dilakukan iterasi dari data pertama sampai data ke n-1. Dalam proses ini akan digunakan sebuah pointer untuk menunjuk ke sebuah node. Pointer ini akan dimulai dari data pertama sampai data ke n-1. Data ke n-1 ditunjukkan dengan sebuah node yang node berikutnya tidak ada.

pointer_luar = head->next;
while (head->next != NULL) {
 
 loop_bagian_dalam_ada_di_sini

 pointer_luar = pointer_luar->next;
}

Loop bagian dalam akan dimulai dari posisi data yang ditunjukkan oleh loop bagian luar sampai data terakhir. Dalam loop ini akan dilakukan proses perbandingan antara data yang ditunjuk oleh loop dalam dengan data yang akan ditukarkan (selection-sort).

data_yang_akan_ditukar = pointer_luar;
pointer_dalam = pointer_luar;
while (pointer_dalam != NULL) {

 ganti = bandingkan(data_yang_akan_ditukar, pointer_dalam)
 if (ganti) {
  data_yang_akan_ditukar = pointer_dalam;
 }  

 pointer_dalam = pointer_dalam->next;
}

tukar_data(pointer_luar, data_yang_akan_ditukar);

Sehingga setelah loop bagian luar dan bagian dalam digabung, maka algoritma selection-sort sudah dapat dipakai.

struct tData *loop_luar, *loop_dalam, *data_yang_akan_ditukar;

pointer_luar = head->next;
while (head->next != NULL) {

 data_yang_akan_ditukar = pointer_luar;
 pointer_dalam = pointer_luar;
 while (pointer_dalam != NULL) {

  ganti = bandingkan(data_yang_akan_ditukar, pointer_dalam)
  if (ganti) {
   data_yang_akan_ditukar = pointer_dalam;
  }

  pointer_dalam = pointer_dalam->next;
 }

 tukar_data(pointer_luar, data_yang_akan_ditukar);

 pointer_luar = pointer_luar->next;