Algoritma Pengurutan

A. Masalah Pengurutan

     Pengurutan (sorting) adalah proses mengatur sekumpulan objek menurut urutan atau susunan tertentu [WIR76].

B. Algoritma Pengurutan

     Algoritma pengurutan yang sering ditemukan di dalam literatur komputer antara lain :

1. Bubble Sort

     a. Pengertian
   

      Bubble Sort (metode gelembung) adalah metode pengurutan dengan cara melakukan penukaran data dengan tepat disebelahnya secara terus menerus sampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan.

     b. Kelebihan dan Kekurangan

          1. Kelebihan

·         Metode Bubble  Sort merupakan yang paling simple

·         Metode Bubble Sort muda di pahami algoritmanya

  2. Kekurangan

·         Meskipun simpel metode Bubble Sort  merupakan metode pengurutan yang paling tidak efisien.  Kelemahan Bubble Sort adalah pada saat mengurutkan data yang sangat besar akan mengalami kelambatan luar biasa, atau dengan kata lain kinerja memburuk cukup signifikan ketika data yang diolah jika  data cukup banyak. Kelemahan lain adalah jumlah pengulangan akan tetap sama jumlahnya walaupun data sesungguhnya sudah cukup terurut. Hal ini disebabkan setiap data dibandingkan dengan setiap data yang lain untuk menentukan posisinya.

c. Algoritma dari Bubble Sort

•       Membandingkan data ke-i dengan data ke-(i+1) (tepat bersebelahan). Jika tidak sesuai maka tukar (data ke-i = data ke-(i+1) dan data ke-(i+1) = data ke-i). Apa maksudnya tidak sesuai? Jika kita menginginkan algoritme menghasilkan data dengan urutan ascending (A-Z) kondisi tidak sesuai adalah data ke-i > data ke-i+1, dan sebaliknya untuk urutan descending (A-Z).

•       Membandingkan data ke-(i+1) dengan data ke-(i+2). Kita melakukan pembandingan ini sampai data terakhir. Contoh: 1 dgn 2; 2 dgn   3; 3 dgn 4; 4 dgn 5 … ; n-1 dgn n.

•       Selesai satu iterasi, adalah jika kita sudah selesai membandingkan antara (n-1) dgn n. Setelah selesai satu iterasi kita lanjutkan lagi iterasi berikutnya sesuai dengan aturan ke-1. mulai dari data ke-1 dgn data ke-2, dan seterusnya.

•       Proses akan berhenti jika tidak ada pertukaran dalam satu iterasi

d. Contoh Program

#include <stdio.h>

#define N 20

int bubble(int n);

int i,j,A[N];

main()          

{

int jml;

             printf("\t METODE BUBBLE SORT \n\n");

             printf("Masukkan jumlah bilangan: ");

             scanf("%d",&jml);

             printf("\n");

             // input data

                             for (i=0;i<jml;i++)

                             {

                             printf("Bilangan ke %d : ",i+1);

                             scanf("%d",&A[i]);

                             }

                             printf("\n");

             // mengurutkan data

                             bubble(jml);

             // menampilkan data

                             printf("Data yang sudah terurut : \n");

                                             for (i=0;i<jml;i++)

                             {

                              

             printf("%d\n",A[i]);

                             }

             }

             // fungsi bubble

             int bubble(int n)

             {

             int temp;

             for (i=1;i<=n-1;i++)

             {

             for (j=i;j<n;j++)

             {

                             if (A[i-1]>A[j])

                             {

                             temp = A[i-1];

                             A[i-1] = A[j];

                             A[j] = temp;

                             }}}
Maka outputnya :

2. Selection Sort

     a. Pengertian

•      Selection sort merupakan perbaikan dari metode bubble sort dengan mengurangi jumlah perbandingan. 

•      Selection sort merupakan metode pengurutan dengan mencari nilai data terkecil dan nilai data terbesar dimulai dari data diposisi 0 hingga diposisi N-1.

     b. Algoritma Selection Sort

    

• Jika terdapat N data dan data terkoleksi dari urutan 0 sampai dengan N-1 maka algoritma pengurutan dengan metode selection sort adalah sebagai berikut :

Ø  Cari data terkecil dalam interval j = 0 sampai dengan j = N-1

Ø  Jika pada posisi pos ditemukan data yang terkecil, tukarkan data diposisi pos dengan data di posisi i jika k.

Ø  Ulangi langkah 1 dan 2 dengan j = j + i sampai dengan j = N-1, dan seterusnya sampai j = N - 1.

·      Bila diketahui data awal berupa: 44 55 12 42 94 18 6 67, maka langkah per langkah pengurutan dengan metode selection sort adalah sebagai berikut:

Tabel 2. Langkah demi langkah pengurutan dengan metode Selection Sort.

c. Kelebihan dan Kekurangan

1. Kelebihan

• Algoritma ini sangat rapat dan mudah untuk diimplementasikan.
• Operasi pertukarannya hanya dilakukan sekali saja.
• Waktu pengurutan dapat lebih ditekan.
• Mudah menggabungkannya kembali.
• Kompleksitas selection sort relatif lebih kecil.

     2. Kekurangan

• Sulit untuk membagi masalah. 

3. Insertion Sort

     a. Pengertian

Insertion sort adalah metode pengurutan dengan cara menyisipkan elemen larik pada posisi yang tepat.

b. Algoritma Insertion Sort

1.       Metode langsung (STRAIGHT INSERTION SORT)

Ilustrasi dari langkah-langkah pengurutan dengan algoritma penyisipan langsung (straight insertion sort) dapat dilihat pada tabel berikut :

Iterasi                Data[0] Data[1] Data[2] Data[3] Data[4] Data[5] Data[6] Data[7]Data[8]Data[9]

Awal   12          35           9              11           3              17           23           15           31           20

i=1       12          35           9              11           3              17           23           15           31           20

i=2       12          35           9              11           3              17           23           15           31           20

i=3       9              12           35           11           3              17           23           15           31           20

i=4       9              11           12           35           3              17           23           15           31           20

i=5       3              9              11           12           35           17           23           15           31           20

i=6       3              9              11           12           17           35           23           15           31           20

       

      2. Metode  penyisipan biner (BINARY INSERTION SORT)

• Metode pengurutan dengan algoritma penyisipan biner (binary insertion sort) memperbaiki metode pengurutan dengan algoritma penyisipan langsung dengan melakukan proses perbandingan yang lebih sedikit sehingga proses pengurutan lebih cepat.

• Metode penyisipan biner melakukan proses perbandingan dengan membagi dua bagian data dari posisi 0 sampai dengan i-1 yang disebut dengan bagian kiri dan kanan. Apabila data pada posisi ke i berada pada jangkauan kiri maka proses perbandingan dilakukan hanya pada bagian kiri dan menggeser posisi sampai i.

    3. Kelebihan dan Kekurangan

     1. Kelebihan
            

•       Sederhana dalam penerapannya.

•       Mangkus dalam data yang kecil.

•       Jika list sudah terurut atau sebagian terurut maka Insertion Sort akan lebih cepat dibandingkan dengan Quicksort.

•       Mangkus dalam data yang sebagian sudah terurut.

•       Lebih mangkus dibanding Bubble Sort dan Selection Sort.

•       Loop dalam pada Inserion Sort sangat cepat, sehingga membuatnya salah satu algoritma pengurutan tercepat pada jumlah elemen yang sedikit.

•       Stabil.

2. Kekurangan

•       Banyaknya operasi yang diperlukan dalam mencari posisi yang tepat untuk elemen larik.

•       Untuk larik yang jumlahnya besar ini tidak praktis.

•       Jika list terurut terbalik sehingga setiap eksekusi dari perintah harus memindai dan mengganti seluruh bagian sebelum menyisipkan elemen berikutnya.

•       Membutuhkan waktu O(n2) pada data yang tidak terurut, sehingga tidak cocok dalam pengurutan elemen dalam jumlah besar.

4. Contoh Program

#include <stdio.h>
 
int main()
{
  int n, array[1000], c, d, t;
 
  printf("Enter number of elements\n");
  scanf("%d", &n);
 
  printf("Enter %d integers\n", n);
 
  for (c = 0; c < n; c++) {
    scanf("%d", &array[c]);
  }
 
  for (c = 1 ; c <= n - 1; c++) {
    d = c;
 
    while ( d > 0 && array[d] < array[d-1]) {
      t          = array[d];
      array[d]   = array[d-1];
      array[d-1] = t;
 
      d--;
    }
  }
 
  printf("Sorted list in ascending order:\n");
 
  for (c = 0; c <= n - 1; c++) {
    printf("%d\n", array[c]);
  }
 
  return 0;
}

Maka Outputnya :

1. 4. Shell Sort

     a. Sejarah dan Pengertian

        Penemu Algoritma Pengurutan shell adalah Donald Shell tahun 1959. Algoritma pengurutan shell merupakan perbaikan terhadap metode pengurutan sisip. Shell sort adalah salah satu sorting algoritma pada sebuah deklarasi array ([]).

        Pada pengurutan data kita terlebih dahulu harus membuat sub list – sub list yang di dasarkan pada jarak antar data yang di tentukan. Jarak yang telah ditetukan biasanya di lambangakan dengan k, biasanya jarak yang paling di gunakan pada sortingsn ini saat melakukan pengurutan data yaitu k5, k3. dan k1. Artinya, dari data yang akan ditentukan atau ditukar dengan data yang lain berjarak 5, 3 atau 1 data saja.

     b. Algoritma Shell Sort

     c. Kelebihan dan Kekurangan

     1. Kelebihan

• Algoritma ini sangat rapat dan mudah untuk diimplementasikan.
• Operasi pertukarannya hanya dilakukan sekali saja.
• Waktu pengurutan dapat lebih ditekan.
• Mudah menggabungkannya kembali.
• Kompleksitas selection sort relatif lebih kecil.

      2. Kekurangan
 

• Membutuhkan method tambahan.
• Sulit untuk membagi masalah.

     d. Contoh Program

    

#include<stdio.h>

#include<conio.h>

int main()

{

 int arr[30];

 int i,j,k,tmp,num;

 printf("Masukan Banyaknya Elemen :");

 scanf("%d", &num);

 for(k=0; k<num; k++)

 {

   printf("\nMasukkan %d Nilai : ",k+1);

   scanf("%d",&arr[k]);

 }

for(i=num/2; i>0; i=i/2)

 {

   for(j=i; j<num; j++)

   {

     for(k=j-i; k>=0; k=k-i)

     {

        if(arr[k+i]>=arr[k])

                             {

            break;

                             }

        else

        {

            tmp=arr[k];

            arr[k]=arr[k+i];

            arr[k+i]=tmp;

        }

     }

   }

 }

 printf("\n**** Hasil Shell Sort ****\n");

 for(k=0; k<num; k++)

     printf("%d\t",arr[k]);

 getch();

 return 0;

}

Maka outputnya :