ALPRO : Materi Sorting

SORTING

Pengertian Sorting

Pengurutan (Sorting) merupakan proses pengurutan sekumpulan data dalam suatu    urutan tertentu.

Sorting dipakai untuk:
1.Membantu proses pencarian (searching)
2.Menyelesaikan masalah-masalah kompleks seperti penjadwalan (scheduling), pengolahan basis data, riset operasi, dsb.

Jenis-Jenis Pengurutan

                                          1.            BUBBLE SORT

·         Pengertian Bubble Sort

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. Jika tidak ada perubahan berarti data sudah terurut. Disebut pengurutan gelembung karena masing-masing kunci akan dengan lambat menggelembung ke posisinya yang tepat.

·         Kelebihan dan Kekurangan Bubble Sort

-          Kelebihan :

1. Metode Bubble  Sort merupakan yang paling simple

2. Metode Bubble Sort muda di pahami algoritmanya

-          Kelemahan :

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.

·      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

·         Contoh Program Bubble Sort

#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;

                        }

}

        }

}

Output :

                                          2.            SELECTION SORT

·         Pengertian Selection Sort

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.

·         Metode 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 :

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

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

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

                         4          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:

44 55 12 42 94 18 06 67 Data Awal

06 55 12 42 94 18 44 67 Tukarkan data ke 1 dengan data ke 7

06 12 55 42 94 18 44 67 Tukarkan data ke 2 dengan data ke 3

06 12 18 42 94 55 44 67 Tukarkan data ke 3 dengan data ke 6

06 12 18 42 94 55 44 67 Data ke 4 tidak ditukarkan

06 12 18 42 44 55 94 67 Data ke 5 ditukarkan dengan data ke 7

06 12 18 42 44 55 94 67 Data ke 6 tidak ditukarkan

06 12 18 42 44 55 67 94 Data ke 7 ditukarkan dengan data ke 8

06  12 18 42 44 55 67 94 Data setelah terurut

Tabel 2. Langkah demi langkah pengurutan dengan metode selection sort.

·         Kelebihan dan Kekurangan Selection Sort

-          Kelebihan

                                1            Algoritma ini sangat rapat dan mudah untuk diimplementasikan.

                                2            Operasi pertukarannya hanya dilakukan sekali saja.

                                3            Waktu pengurutan dapat lebih ditekan.

                                4            Mudah menggabungkannya kembali.

                                5            Kompleksitas selection sort relatif lebih kecil.

-          Kekurangan

                                1            Sulit untuk membagi masalah.

                                          3.            INSERTION SORT

·         Pengertian Insertion Sort

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

·         Macam- macam metode insertion sort

                                  1            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
i=7	3	9	11	12	17	23	35	15	31	20
i=8	3	9	11	12	15	17	23	35	31	20
i=9	3	9	11	12	15	17	23	31	35	20
Akhir	3	9	11	12	15	17	20	23	31	35

                                  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.

·         Kelebihan dan kekurangan insertion sort

-          Kelebihan

                                          1.            Sederhana dalam penerapannya.

                                          2.            Mangkus dalam data yang kecil.

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

                                          4.            Mangkus dalam data yang sebagian sudah terurut.

                                          5.            Lebih mangkus dibanding Bubble Sort dan Selection Sort.

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

                                          7.            Stabil.

-          Kekurangan

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

b.      Untuk larik yang jumlahnya besar ini tidak praktis.

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

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

·         Contoh Program

#include <stdio.h>

int main()

{

  int n, array[1000], c, d, t;

  printf("Masukkan Banyak Elemen ");

  scanf("%d", &n);

  printf("Masukkan %d Bilangan\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("Data Yang Sudah Terurut :\n");

  for (c = 0; c <= n - 1; c++) {

    printf("%d\n", array[c]);

  }

  return 0;

}

Output :

                                          4.            SHELL SORT

·         Pengertian Shell Sort

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.

·         Metode Shell Sort

·         Kelebihan dan Kekurangan Shell Sort

-          Kelebihan

                                1            Algoritma ini sangat rapat dan mudah untuk diimplementasikan.

                                2            Operasi pertukarannya hanya dilakukan sekali saja.

                                3            Waktu pengurutan dapat lebih ditekan.

                                4            Mudah menggabungkannya kembali.

                                5            Kompleksitas selection sort relatif lebih kecil.

-          Kekurangan

                                1            Membutuhkan method tambahan.

                                2            Sulit untuk membagi masalah.

·         Contoh Program

-          Contoh Program Kedua (  Mengurutkan Data Tipe Angka )

#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;

}

Output :

 

-          Contoh Program Kedua (  Mengurutkan Data Tipe Angka dengan Dua Array )

#include <stdio.h>

#include <conio.h>

int main()

{

        int n,m,i,j,range,jarak,simpan,data[50],dx[50];

        printf("Masukkan banyak data A:\t"),scanf("%d",&n);

        printf("Masukkan banyak data B:\t");scanf("%d",&m);

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

        {

                        printf ("Data A ke %d:\t",i+1);scanf("%d",&data[i]);

        }

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

        {

                        printf ("Data B ke %d:\t",i+1);scanf ("%d",&dx[i]);

        }

        printf ("\nSEBELUM\n");

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

        {

                        printf("\nDataA=%d",data[i]);

        }

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

        {

                        printf("\nDataB=%d",dx[i]);

        }

        jarak=n/2;

        while (jarak>0)

        {

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

                        {

                                        j=i-jarak;

                                        while(j>=0)

                                        {

                                                        if(data[j+jarak]<data[j])

                                                        {

                                                                        simpan=data[j];

                                                                        data[j]=data[j+jarak];

                                                                        data[j+jarak]=simpan;

                                                                        printf ("\n");                     

                                                                        for(int j=0;j<n;j++)

                                                                        {

                                                                                        printf("\n%d",data[j]);

                                                                        }

                                                        }

                                                        j=j-jarak;

                                        }

                        }

                        jarak=jarak/2;

        }

        range=m/2;

        while (range>0)

        {

                        for (i=range;i<m;i++)

                        {

                                        j=i-range;

                                        while(j>=0)

                                        {

                                                        if(dx[j+range]>dx[j])

                                                        {

                                                                        simpan=dx[j];

                                                                        dx[j]=dx[j+range];

                                                                        dx[j+range]=simpan;

                                                                        printf ("\n");                     

                                                                        for(int j=0;j<n;j++)

                                                                        {

                                                                                        printf("\n%d",dx[j]);

                                                                        }

                                                        }

                                                        j=j-range;

                                        }

                        }

                        range=range/2;

        }

        printf("\n");

        printf("\nSESUDAH data A\n");

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

        {

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

        }

        printf("\n");

        printf("\nSESUDAH data B\n");

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

        {

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

        }

        getch ();

        return 0;

}

Output :

-          Contoh Program Ketiga (  Mengurutkan Data Tipe Char )

#include <string.h>

#include <stdio.h>

#include <stdlib.h>

void shell_sort(char *chars, int c)  {

 register int i, j, space, k;

 char x, a[5];

 a[0]=9; a[1]=5; a[2]=3; a[3]=2; a[4]=1;

 for(k=0; k < 5; k++) {

  space = a[k];

  for(i=space; i < c; ++i) {

   x = chars[i];

   for(j=i-space; (x < chars[j]) && (j >= 0); j=j-space)

    chars[j+space] = chars[j];

   chars[j+space] = x;

  }

 }

}

int main() {

 char string[3];

 printf("Masukkan Karakter: ");

 gets(string);

 shell_sort(string, strlen(string));

 printf("Pengurutan karakter: %s.\n", string);

 return 0;

}

Output :