Algoritma : Sorting

Rumahit.ID - Salah satu bagian penting dari struktur data adalah sorting atau pengurutan data. Ada banyak sekali Algoritma pengurutan data di dunia komputer, yatu : bubble sort, selection sort, insertion sort, exchange sort, quick sort, merge sort, dan lain lain.
Sorting adalah proses pengurutan data yang sebelumnya disusun secara acak atau tidak teratur sehingga menjadi tersusun secara terurut menurut suatu aturan tertentu.


Pada umumnya terdapat 2 jenis pengurutan :

• Ascending (naik, pengurutan dari karakter/angka kecil ke karakter/angka besar).
• Descending (turun, pengurutan dari karakter/angka besar ke karakter/angka kecil).

Contoh :

Data acak                 : 5 6 8 1 3 25 10
Terurut Ascending     : 1 3 5 6 8 10 25
Terurut Descending : 25 10 8 6 5 3 1

Metode Pengurutan (Sorting)

Untuk melakukan proses pengurutan tersebut dapat digunakan berbagai macam cara / metoda. Beberapa metoda diantaranya :

1. Bubble / Exchange Sort
2. Selection Sort
3. Insertion Sort

1. Metode Buble Sort

Metode bubble sort adalah metode yang mendasarkan penukaran dua buah elemen untuk mencapai keadaan urut. Metode ini mempunyai perilaku seperti gelembung dimana bila akan diurutkan naik nilai yang besar akan naik (indeks besar) sementara nilai yang kecil akan turun (indeks kecil). Setiap data akan dibandingkan dengan data yang ada disebelahnya sampai dengan data terakhir. Metode ini adalah yang termudah, tetapi paling tidak efisien.

Contoh data-data sebagai berikut akan diurut dari yang terkecil sampai yang terbesar dari ke 8 data tersebut dan akan menggunakan pembandingan data yang paling akhir:

5 34 32 25 75 42 22 2

Adapun langkah-langkah pengurutan adalah sebagai berikut :

Langkah 1:

Hasilnya adalah :

2 5 34 32 25 75 42 22

Langkah 2 :

Hasilnya adalah :

2 5 22 34 32 25 75 42

Langkah 3 :

Hasilnya adalah :

2 5 22 34 32 25 42 75

Langkah 4 :

Langkah 5 :

Hasilnya adalah :

2 5 22 25 32 34 42 75

Untuk pengurutan data dari besar ke kecil adalah kebalikan dari proses di atas.

Algoritma dari langkah-langkah di atas adalah :

1. Tentukan data-data yang akan diurutkan dan disimpan dalam array.
2. Lakukan pengulangan dari data-data tersebut.
3. Lakukan pembandingan antara data yang satu dengan data yang lain, dimana kalau data yang satu lebih kecil dari data yang lain, maka posisinya ditukar. Kalau tidak, posisinya tetap.
4. Tampilkan data hasil pembandingan.
5. Ulangi langkah 3, sampai semua data dibandingkan.
6. selesai.

Implementasi dari langkah-langkah dalam Bubble Sort dapat dilihat pada program berikut ini, program Ascending dengan menggunakan Bubble Sort.

#include <iostream.h>
#include <iomanip.h> 

void main()
{
   int NumList[8]= { 5, 34, 32, 25, 75, 42, 22, 2};
   int i,ii,iii; 
   int Swap;
   cout<<"Data sebelum diurutkan : \n"; 
   for(int ctr=0; ctr<8; ctr++)
   {
      cout<< setw(3)<<NumList[ctr];
   }
   cout<<"\n\n"; 
   for(i=0; i<7; i++) 
   for(ii=0; ii<7; ii++)
      if (NumList[ii] > NumList[ii+1])
      {
          Swap = NumList[ii]; 
          NumList[ii] = NumList[ii+1]; 
          NumList[ii+1] = Swap;
      }
    cout<<"Data setelah diurutkan : \n" ; 
    for (iii=0; iii<8; iii++); 
    cout<<setw(3)<<NumList[iii]; 
    cout<<endl<<endl;
}

2. Metode Selection Sort

Metode seleksi (Selection Sort) adalah suatu metode pengurutan yang membandingkan elemen yang sekarang dengan elemen berikutnya sampai elemen yang terakhir. Jika ditemukan elemen lain yang lebih kecil dari elemen sekarang, maka dicatat posisinya dan kemudian ditukar. Misalkan ada data-data sebagai berikut yang akan diurutkan dari yang terkecil sampai yang terbesar dari data tersebut.

5 34 32 25 75 42 22 2

Langkah-langkahnya adalah sebagai berikut :

Langkah 1 :

Posisi     : 1 2 3 4 5 6 7 8
Data : 5 34 32 25 75 42 22 2

Pembanding Posisi
5 < 34 1
5 < 32 1
5 < 25 1
5 < 75 1
5 < 42 1
5 < 22 1
5 < 2 8

Tukar data pada posisi 1 dengan data posisi 8

Hasil Sementara : 2 34 32 25 75 42 22 5

Langkah 2 :

Posisi     : 1 2 3 4 5 6 7 8
Data : 2 34 32 25 75 42 22 5

Pembanding Posisi
34 > 32           3
32 > 25           4
25 < 75           4
25 < 42           4
25 > 22           7
22 > 5           8

Tukar data pada posisi 2 dengan data pada posisi 8

Hasil Sementara : 2 5 32 25 75 42 22 34

Langkah 3 :

Posisi     : 1 2 3 4 5 6 7 8
Data : 2 5 32 25 75 42 22 34

Pembanding Posisi
32 > 25           4
25 < 75           4
25 < 42           4
25 > 22           7
22 < 34           7

Tukar data pada posisi 3 dengan data pada posisi 7

Hasil Sementara : 2 5 22 25 75 42 32 34

Langkah 4 :

Posisi     : 1 2 3 4 5 6 7 8
Data : 2 5 22 25 75 42 32 34

Pembanding Posisi
75 > 42           6
42 > 32           7
32 < 34           7

Tukar data pada posisi 5 dengan data pada posisi 7

Hasil Sementara : 2 5 22 25 32 42 75 34

Langkah 5 :

Posisi     : 1 2 3 4 5 6 7 8
Data : 2 5 22 25 32 42 75 34

Pembanding Posisi

42 < 75           6
42 > 34           8

Tukar data pada posisi 6 dengan data pada posisi 8

Hasil Sementara : 2 5 22 25 32 34 75 42

Langkah 6 :

Posisi     : 1 2 3 4 5 6 7 8
Data : 2 5 22 25 32 34 75 42

Pembanding Posisi

75 > 42           8

Tukar data pada posisi 7 dengan data pada posisi 8


Hasil Akhir : 2 5 22 25 32 34 42 75

Proses pengurutan data di atas memerlukan 6 kali perulangan. Algoritma dari langkah-langkah di atas adalah :

1. Tentukan data-data yang akan diurutkan dan disimpan dalam array.
2. Lakukan pengulangan dari data-data tersebut.
3. Lakukan pembandingan antara data yang satu dengan data yang lain, dimana kalau data yang satu lebih kecil dari data yang lain, maka posisinya ditukar. Kalau tidak, posisinya tetap.
4. Tampilkan data hasil pembandingan.
5. Ulangi langkah 3, sampai semua data dibandingkan.
6. Selesai.

Implementasi program selection adalah sebagai berikut :

#include <stdio.h> 
#include <conio.h>

int A[8]={2,5,22,25,32,34,42,75},i,j,tampung,pos; 

main() {
      clrscr();
      printf("Sebelum Sorting : \n"); 
      for (i=0; i<8; i++) {
         printf("%i " , A[i]);
      }
      for (i=0; i<8-i; i++) {
          if (A[j]<A[pos])
          {
             pos=j;
          }
      }
      if (pos!=i)
      {
           tampung=A[pos]; 
           A[pos]=A[i]; 
           A[i]=tampung;
      }
      printf("\n\nSetelah Sorting : \n"); 
      for (i=0; i<8; i++)
      {
      printf("%i ", A[i]);
      }
      return 0;
}

3. Metode Insertion Sort

Metode Insertion(penyisipan) adalah dengan membandingkan data/elemen ke-n (n  mulai dari data ke-2 hingga elemen terakhir) dengan elemen-elemen sebelumnya. Jika ditemukan data yang lebih kecil maka data tersebut disisipkan ke depan (tukar posisi) sesuai dengan posisi seharusnya.

Contoh : 8 3 7 4

Langkah 1 : 3 dibandingkan dengan 8, karena 3 < 8 maka kedua elemen ditukar posisinya
yang menghasilkan urutan 3 8 7 4

Langkah 2 : 7 dibandingkan dengan 8, karena 7 < 8 maka 7 ditukar posisinya dengan 8
yang menghasilkan urutan 3 7 8 4

Langkah 3 : 4 dibandingkan dengan 8, karena 4 < 8 maka tukar posisinya, hasil sementara
adalah 3 7 4 8

Kemudian 4 dibandingkan dengan 7, karena 4 < 7 maka tukar posisinya,
hasilnya adalah 3 4 7 8

Kemudian 4 dibandingkan dengan 3, karena 4 > 3 , maka posisinya tetap,
hasil akhirnya adalah 3 4 7 8

Algoritma dari langkah-langkah di atas adalah :

1. Tentukan data-data yang akan diurutkan dan disimpan dalam array.
2. Lakukan  pembandingan  antara  data   ke   2  hingga   elemen  terakhir dengan data sebelumnya, jika data yang dibandingkan bernilai lebih kecil, maka posisinya ditukar.
3. Tampilkan data hasil pembandingan.
4. Ulangi langkah 2, sampai semua data dibandingkan.
5. Selesai.

Implementasi program insertion adalah sebagai berikut :

#include <stdio.h> 
#include <conio.h>

int A[5]={8,3,7,4},i,j,tampung; 
main()
{
     clrscr();
     printf("Sebelum Sorting : \n"); 
     for (i=0; i<=4; i++)
     {
        printf("%i " , A[i]);
     }
     for (i=1; i<4; i++)
     {
        tampung=A[i]; 
        j=i-1;
        while (A[j]>tampung && j>0)
        {
           A[j+1] = A[j]; j--;
        }
           A[j+1]=tampung;
        }
     printf("\n\nSetelah Sorting : \n"); 
     for (i=0; i<5; i++)
     {
         printf("%i ", A[i]);
     }
     return 0;
}

Daftar Pustaka :

Andri Kristanto, Algoritma & Pemrograman dengan C++ Edisi 2, Graha Ilmu, Yogyakarta, 2009.

Teddy Marcus Zakaria dan Agus Prijono, Konsep dan Implementasi Struktur Data, Informatika, Bandung, 2006

Thompson Susabda Ngoen, Pengantar Algoritma dengan Bahasa C, Salemba Teknika, Jakarta, 2004

Modul Algoritma dan Struktur Data Universitas Mercubuana.