Sorting (Selection Sort dan Insertion Sort)

Pengantar Pengurutan Data

Proses pengurutan data banyak ditemukan di dalam komputer. Hal itu karena data yang diurut mudah dicari. Untuk membentuk data yang tidak terurut menjadi terurut, terdapat berbagai algoritma yang bisa digunakan, namun yang akan kita bahas hanyalah selection sort dan insertion sort.

Di dalam pengurutan data terdapat istilah ascending dan descending. Pengurutan dengan dasar nilai yang kecil menuju ke nilai yang besar disebut ascending (urut naik), sedangkan yang disusun atas dasar dari nilai besar ke kecil disebut descending (urut turun).

Selection Sort (Pengurutan Seleksi)

Pengurutan seleksi (selection sort) mempunyai mekanisme seperti berikut: mula mula suatu penunjuk (diberi nama posAwal), yang menunjuk ke lokasi awal pengurutan data, diatur agar berisi indeks pertama dalam larik. Selanjutnya dicari bilangan terkecil yang terletak antara posisi sesudah yang ditunjuk oleh penunjuk tersebut hingga elemen yang terakhir di dalam larik. Lokasi bilangan ini ditunjuk oleh posMin. Lalu tukarkan nilai bilangan terkecil tersebut dengan nilai yang dintunjukan oleh posAwal. Proses seperti ini diulang dari posAwal bernilai 0 hingga n-2, dengan n menyatakan jumlah elemen dalam larik.

Untuk lebih jelasnya kita dapat melihatnya di gambar:

 
Contoh :

Cobalah untuk menimplementasikan subrutin pengurutan seleksi baik dalam bentuk algoritma maupun program.

Algoritma:

SUBRUTIN selection_sort(L,n) 

       UNTUK posAwal = 0 S/D n-2

              posMin <- posAwal

              UNTUK j<- posAwal + 1 S/D n - 1

                    JIKA L[posMin] > L[j] MAKA

                         posMin <- j

                    AKHIR-JIKA

              AKHIR-UNTUK

           //tukarkan

          tmp <- L[posAwal]

          L[posAwal] <- L[posMin]

          L[posMin] <- tmp

      AKHIR-UNTUK

AKHIR-SUBRUTIN

Program:

Ascending

#include <iostream.h>
#include <conio.h>

void tampilkan_larik(int data[], int n)
{
   int i;

   for (i = 0; i < n; i++)
      cout << data[i] << " ";

   cout << "\n";
}

void selection_sort(int data[], int n)
{
   int posMin, posAwal, j, tmp;

   for (posAwal = 0; posAwal < n-1; posAwal++)
   {
      posMin = posAwal;
      for (j = posAwal + 1; j < n; j++)
          if (data[posMin] > data[j])
             posMin = j;

      /* Tukarkan */
      tmp = data[posAwal];
      data[posAwal] = data[posMin];
      data[posMin] = tmp;

      cout << "Hasil posAwal= " << posAwal <<": ";
      tampilkan_larik(data, n);
   }
}

int main()
{ 
   const JUM_DATA = 8;

   int i;
   int data[] = {25, 57, 48, 37, 12, 92, 80, 33};

   selection_sort(data, JUM_DATA);

   /* Hasil pengurutan */

   cout << "Hasil pengurutan:\n";
   tampilkan_larik(data, JUM_DATA);

   getch ();
   return 0;
}

Hasil eksekusi program:

   

 
Descending

#include <iostream.h>
#include <conio.h>

void tampilkan_larik(int data[], int n)
{
   int i;

   for (i = 0; i < n; i++)
      cout << data[i] << " ";

   cout << "\n";
}

void selection_sort(int data[], int n)
{
   int posMin, posAwal, j, tmp;

   for (posAwal = 0; posAwal < n-1; posAwal++)
   {
      posMin = posAwal;
      for (j = posAwal + 1; j < n; j++)
          if (data[posMin] < data[j])
             posMin = j;

      /* Tukarkan */
      tmp = data[posAwal];
      data[posAwal] = data[posMin];
      data[posMin] = tmp;

      cout << "Hasil posAwal= " << posAwal <<": ";
      tampilkan_larik(data, n);
   }
}

int main()
{ 
   const JUM_DATA = 8;

   int i;
   int data[] = {25, 57, 48, 37, 12, 92, 80, 33};

   selection_sort(data, JUM_DATA);

   /* Hasil pengurutan */

   cout << "Hasil pengurutan:\n";
   tampilkan_larik(data, JUM_DATA);

   getch ();
   return 0;
}

Hasil eksekusi program:

 













Insertion Sort (Pengurutan dengan Penyisipan)

Pengurutan dengan penyisipan (insertion sort) adalah suatu metode yang melakukan pengurutan dengan cara menyisipkan data yang belum urut ke dalam bagian data yang telah diurutkan. Konsep seperti ini biasa dilakukan pada permainan kartu. Ketika sebuah kartu baru didapatkan (hasil pembagian dari pengocokan kartu) kartu akan disisipkan oleh pemain pada posisi yang tepat sehingga penambahan kartu tersebut membuat semua kartu tetap terurutkan.

Untuk lebih jelasnya kita lihat gambar:

 

contoh :

Bila L adalah larik dengan n elemen, mula mula L[0] (elemen pertama) dianggap sebagai kumpulan data yang telah diurutkan, yang terdiri dari 1 buah data. Kemudian dilakukan penyisipan data dari L[1] sampai dengan L[n-1] ke dalam kumpulan data dari L[0] sampai dengan L[k-1] dengan 1<k<n. Dalam hal ini penyisipan dilakukan pada tempat yang tepat sehingga data pada L[0] sampai dengan L[k] menjadi urut.

Algoritma:

SUBRUTIN selection_sort(L,n)
        UNTUK k <- 1 S/D n-1
               x<-L[k]

               //sisipkan x ke dalam L[0..k-1]
               i <- k-1
               ketemu <- SALAH
               ULANG SELAMA i >= 0 DAN TIDAK ketemu
                      JIKA x < L[i] MAKA
                           L[i+1] <- L[i]
                           i <- i -1
                      SEBALIKNYA
                           ketemu = BENAR
                      AKHIR-JIKA

                      L[i+1] <- x
               AKHIR-ULANG
        AKHIR-UNTUK
AKHIR-SUBRUTIN

Program:

Ascending

#include <iostream.h>
#include <conio.h>

void tampilkan_larik(int data[], int n)
{
   int i;

   for (i = 0; i < n; i++)
      cout << data[i] << " ";

   cout << "\n";
}

void insertion_sort(int data[], int n)
{
   int i, k;
   int x;
   int ketemu;

   for (k = 1; k < n; k++)
   {
      x = data[k];

      // Sisipkan x ke dalam data[0..k-1]
      i = k - 1;
      ketemu = 0;

      while ((i >= 0) && (!ketemu))
      {
         if (x < data[i])
         {
            data[i+1] = data[i];
            i = i - 1;
         }
         else
            ketemu = 1;

         data[i+1] = x;
      }
   }  
}

int main()
{ 
   const JUM_DATA = 8;

   int i;
   int data[] = {25, 57, 48, 37, 12, 92, 80, 33};

   insertion_sort(data, JUM_DATA);

   // Hasil pengurutan

   cout << "Hasil pengurutan:\n";
   tampilkan_larik(data, JUM_DATA);

   getch ();
   return 0;
}

Hasil eksekusi program:

Descending

#include <iostream.h>
#include <conio.h>

void tampilkan_larik(int data[], int n)
{
   int i;

   for (i = 0; i < n; i++)
      cout << data[i] << " ";

   cout << "\n";
}

void insertion_sort(int data[], int n)
{
   int i, k;
   int x;
   int ketemu;

   for (k = 1; k < n; k++)
   {
      x = data[k];

      // Sisipkan x ke dalam data[0..k-1]
      i = k - 1;
      ketemu = 0;

      while ((i >= 0) && (!ketemu))
      {
         if (x > data[i])
         {
            data[i+1] = data[i];
            i = i - 1;
         }
         else
            ketemu = 1;

         data[i+1] = x;
      }
   }  
}

int main()
{ 
   const JUM_DATA = 8;

   int i;
   int data[] = {25, 57, 48, 37, 12, 92, 80, 33};

   insertion_sort(data, JUM_DATA);

   // Hasil pengurutan

   cout << "Hasil pengurutan:\n";
   tampilkan_larik(data, JUM_DATA);

   getch ();
   return 0;
}

Hasil eksekusi program: