Senin, 03 Oktober 2016

Sorting

Pengertian
Sorting merupakan suatu proses pengurutan yang bermula dari data/elemen acak yang kemudian diurutkan baik secara asceding (menaik) atau descending (menurun) dengan menggunakan aturan tertentu.

Tujuan melakukan sorting yaitu supaya data yang sudah terurut mudah untuk dicari, mudah untuk diperiksa, dan mudah diperbaiki apabila terdapat kesalahan. Dengan mengurutkan data maka semakin mudah untuk menyisipkan data atau penggabungan data.

Metode-metode sorting yaitu :

1.       Bubble Sort (Metode Gelembung)

Merupakan suatu pengurutan dengan cara penukaran data tepat dengan data disebelahnya secara     berulang dan terus menerus sampai data tidak bias ditukarkan lagi, jika tidak ada perubahan berarti data sudah terurut. Merupakan metode pengurutan paling simple karena konsep dari bubble sort ini adalah mengulang proses perbandingan dari tiap tiap elemen data. 

  1.       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 algoritma menghasilkan data dengan urutan ascending (A-Z) kondisi tidak sesuai adalah data i > data -i+1, dan sebaliknya.
  2.       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.
  3.     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, dst.
  4.        Proses akan berhenti jika tidak ada pertukaran dalam satu iterasi.



      Contoh Kasus :

      Misalkan data yang akan diurutkan secara ascending :

     6    3    9      1      5

 







      Algoritma Bubble Sort Secara Ascending

        Procedure bubble_sort_asc(I/O  nama_var_array : nama_tipe_array,
       Input  N : integer)
       {I.S.  : array(1..N) sudah terdefinisi}
       {F.S. : menghasilkan array(1..N) yang sudah tersusun secara ascending}
        Kamus:
                       i, j : integer
                       temp : tipedata
        Algoritma:
                        for  i  ß  1  to  N-1   do
                        for   j   ß  n   downto   i+1  do
                             if(nama_var_array(j) < nama_var_array(j-1))
                                 then
                                        temp ß nama_var_array(j)
                                        nama_var_array(j) ß nama_var_array(j-1)
                                        nama_var_array(j-1)  ß  temp
                            endif
                     endfor
                     endfor
      EndProcedure



         Data Yang Akan Diurutkan Secara Descending :

    6      3      9      1      5









      Algoritma Bubble Short secara descending

       Procedure bubble_sort_dsc(I/O nama_var_array : nama_tipe_array, Input  N : integer)
       {I.S.  : array(1..N) sudah terdefinisi}
       {F.S. : menghasilkan array(1..N) yang sudah tersusun secara descending}
        Kamus:
                       i,j : integer
                       temp : tipedata
        Algoritma:
                       for  i  ß  1  to  N-1   do
                       for   j   ß  1   to   (N - i)  do
                            if(nama_var_array(j) < nama_var_array(j+1))
                               then
                                       temp ß nama_var_array(j)
                                       nama_var_array(j) ß nama_var_array(j+1)
                                       nama_var_array(j+1)  ß  temp
                           endif
                     endfor
                     endfor
       EndProcedure



            Kelebihan dan Kekurangan Bubble Sort 

        Kelebihan :

  •    Merupakan metode yang paling simpel.
  •    Mudah dipahami algoritmanya.

        Kekurangan:
  • ·   Untuk jumlah data yang banyak penggunaan metode bubble sort kurang efektif karena                bisa memakan waktu yang lama dalam melakukan proses perbandingan atau pertukaran              datanya.


     2.   Selection Sort (Metode Seleksi)

     Merupakan metode pengurutan yang memiliki konsep Maksimum dan Minimum dimana elemen- elemen data di bandingkan satu-persatu sampai pada elemen terakhir dan disusun berdasarkan ketentuan-ketentuan berlaku lalu menukar posisinya.
     Seperti pada algoritma Bubble Sort, proses memilih nilai maksimum /minimum dilakukan pada setiap pass. Jika array berukuran N, maka jumlah pass adalah N-1.



         Contoh Kasus :






        Algoritma Maximum Sort Ascending

          Procedure Maximum_sort_asc(I/O  nama_var_array : nama_tipe_array, Input N : integer)
         {I.S. : array(1..N) sudah terdefinisi}
         {F.S. : menghasilkan array(1..N) yang sudah tersusun secara ascending}
          Kamus:
                       i, j, max, x : integer
                       temp : tipedata
          Algoritma:
                        x  ß  n
                        for  i  ß  1  to  N-1   do
                           max ß 1
                        for   j   ß  2   to   x  do
                          if(nama_var_array(j) > nama_var_array(max))
                               then
                                    max ß j
                         endif
                         endfor
                                     temp ß nama_var_array(max)
                                     nama_var_array(max) ß nama_var_array(j)
                                     nama_var_array(j)  ß  temp
                                     x ß x - 1
                         endfor
           EndProcedure



          Algoritma Minimum Sort Ascending

         Procedure Minimum_sort_asc(I/O nama_var_array : nama_tipe_array,
           Input  N : integer)
          {I.S. : array(1..n) sudah terdefinisi}
           {F.S. : menghasilkan array(1..n) yang sudah tersusun secara ascending}
           Kamus:
                             i, j, min : integer
                             temp  :  tipedata
           Algoritma:
                    for  i  ß  1  to  (N – 1)   do
                            min ß i
                    for   j   ß  i+1   to   N  do
                            if(nama_var_array(j) < nama_var_array(min))
                               then
                                       min ß j
                               endif
                    endfor
                             temp ß nama_var_array(min)
                             nama_var_array(min) ß nama_var_array(i)
                             nama_var_array(i)  ß  temp
                   endfor
            EndProcedure

        
          Kelebihan dan Kekurangan Selection Sort :

           Kelebihan  :
  •           Mudah untuk diimplementasikan.
  •           Operasi pertukarannya hanya dilakukan sekali saja.
  •           Waktu pengurutan dapat lebih cepat.
           Kekurangan :
  •                       Sulit untuk membagi masalah.


3.     Insertion sort (Metode Penyisipan)
     Merupakan suatu perbandingan data untuk mencari posisi yang “tepat” di setiap elemen array.
     Merupakan metode pengurutan yang membandingkan dua elemen data pertama lalu mengurutkannya kemudian mengecek elemen data berikutnya satu persatu dan membandingkannya dengan elemen data yang telah diurutkan.
      Proses ini  menyisipkan sebuah elemen array yang diproses ke tempatnya yang seharusnya. Proses dilakukan sebanyak N-1, dengan indeks dimulai dari 0. Proses pengurutan dengan menggunakan algoritma Insertion Sort dilakukan dengan cara membandingkan data ke-i (dimana i dimulai dari data ke-2 sampai dengan data terakhir) dengan data berikutnya. Jika ditemukan data yang lebih kecil maka data tersebut disisipkan ke depan sesuai dengan posisi yang seharusnya.

     Metode Insertion Sort bertujuan untuk menjadikan bagian sisi kiri array terurutkan sampai dengan seluruh array berhasil diurutkan. Metode ini mengurutkan bilangan-bilangan yang telah dibaca dan berikutnya secaraberulang akan menyisipkan bilangan-bilangan dalam array yang belum terbaca ke sisi kiri array yang telah terurut. 



         Contoh Insertion Sort :


          Bagian biru/abu-abu (dua bilangan pertama) sekarang dalam keadaan terurut secara relatif.



         Berikutnya, kita perlu menyisipkan bilangan ketiga (4) ke dalam bagian biru/abu-abu sehingga    
         setelah penyisipan tersebut, bagian biru/abu-abu tetap dalam keadaan terurut secara relatif; 
 
         Caranya :
         pertama : Ambil bilangan ketiga (4).
   
          Kedua : Geser bilangan kedua (10) shg ada ruang untuk disisipi.


         Ketiga : Sisipkan bilangan 4 ke posisi yang tepat.


         Sekarang, tiga bilangan pertama sudah terurut secara relatif dan kita sisipkan bilangan keempat kepada tiga bilangan pertama tsb.  Setelah penyisipan, empat bilangan pertama haruslah dalam keadaan terurut secara relatif.




         Ulangi proses tsb sampai bilangan terakhir disisipkan.








        Proses Sorting Selesai.

        Contoh lain :



         Contoh Kasus :
     Dari gambaran proses pengurutan/ sorting  data di atas dapat diketahui  bagaimana data-data tersebut berpindah  posisi  dari satu index ke index lain dalam satu array.  Untuk detail proses pengurutan diatas, dapat disimak melalui detail simulasi berikut.

          Data awal : 5, 2, 4, 6, 1, 3

    Jumlah Index = 6   dimulai dari 0 s/d 5
    Anggaplah index adalah ‘I’,
    Untuk setiap proses pengurutan data, perbandingan data dimulai dari index kedua (dalam hal ini           i=1)

    Proses I:
    i=1, x=1,  j=0
    x<j  à2<5 — true  =2, 5, 4, 6, 1, 3

    Proses II
    i=2, j=1, x=2
    x<j à  4<5 — true = 2, 4, 5, 6, 1, 3     j=j-1,      Jika benar    x=x-1
    x<j à4<2 — false = 2, 4, 5, 6, 1, 3

    Proses III
    I=3, j=2, x=3
    x<j à6<5 — false =  2, 4, 5, 6, 1, 3     j=j-1    1    jika sebuah proses bernilai false, maka proses tersebut tidak akan dilanjutkan, karena secara otomatis data yang ada disebelah kiri semuanya sudah terurut dengan benar.
        
        Proses IV
    i=4, j=3, x=4
    x<j à1<6 — true = 2, 4, 5, 1, 6, 3   j=j-1,     jika benar  maka  x=x-1
    x<j à 1<5 — true = 2, 4, 1, 5,6, 3  j=j-1 ,     jika benar  maka   x=x-1
    x<j  à1<4  — true = 2, 1, 4, 5,6, 3  j=j-1,     jika benar  maka   x=x-1
    x<j  à 1<2 — true =   1, 2, 4, 5,6, 3

    Proses V
    i=5, j=4, x=5  
    x<j à3<6  — true = 1, 2, 4, 5,3, 6  j=j-1  , jika benar maka x=x-1
    x<j à3<5 — true = 1, 2, 4, 3, 5, 6   j=j-1,  jika benar maka x=x-1
    x<j à3<4 — true = 1, 2, 3, 4, 5, 6  j=j-1,   jika benar maka x=x-1
    x<jà3<2 — false = 1, 2, 3, 4, 5, 6  j=j-1



         Kelebihan dan Kekurangan Insertion Sort :

           Kelebihan :
  •        Sangat Sederhana.
  •        Sangat efisien untk data yang sangat kecil misalkan data kurang dari 10 or 20.
  •        Prosesnya yang cepat.
  •        Jika list sudah terurut atau sebagian sudah terurut maka Insertion Sort akan lebih cepat dibandingkan dengan Quick sort.
  •        Stabil.
      Kekurangan :
  •       Untuk larik yang jumlahnya besar ini tidak praktis.
  •             Banyak Operasi yang Dilakukan.
  •             Jika list terurut terbalik maka proses Loopingnya akan lama.


     4.  Shell Sort (Metode shell)
          Metode ini disebut juga dengan metode pertambahan menurun (diminishing increment). Metode          ini dikembangkan oleh Donald L. Shell pada tahun 1959, sehingga sering disebut dengan Metode        Shell Sort. Metode ini mengurutkan data dengan cara membandingkan suatu data dengan data              lain yang memiliki jarak tertentu, kemudian dilakukan penukaran bila diperlukan. Proses                    pengurutan dengan metode Shell dapat dijelaskan sebagai berikut  :
          Pertama-tama adalah menentukan jarak mula-mula dari data yang akan dibandingkan, yaitu N / 2.        Data pertama dibandingkan dengan data dengan jarak N / 2. Apabila data pertama lebih besar dari        data ke N / 2 tersebut maka kedua data tersebut ditukar. Kemudian data kedua dibandingkan dengan      jarak yang sama yaitu N / 2. Demikian seterusnya sampai seluruh data dibandingkan sehingga              semua data ke-j selalu lebih kecil daripada data ke-(j + N / 2).

     Pada proses berikutnya, digunakan jarak (N / 2) / 2 atau N / 4. Data pertama dibandingkan dengan        data dengan jarak N / 4. Apabila data pertama lebih besar dari data ke N / 4 tersebut maka kedua          data tersebut ditukar. Kemudian data kedua dibandingkan dengan jarak yang sama yaitu N / 4.              Demikianlah seterusnya hingga seluruh data dibandingkan sehingga semua data ke-j lebih kecil            daripada data ke-(j + N / 4).

     Pada proses berikutnya, digunakan jarak (N / 4) / 2 atau N / 8. Demikian seterusnya sampai jarak        yang digunakan adalah 1.


        Contoh Kasus :
         Dalam  Pascal :

        Procedure Shell(Var Temp : Data; JmlData : Integer); 
        Var 
                    I,J, Jarak : Integer; 
         Begin 
                    Jarak := JmlData Div 2; 
                    While Jarak > 0 Do 
                    Begin 
                             For I:=1 To JmlData-Jarak Do 
                                   Begin 
                                          J := I + Jarak; 
                                          If Temp[I] > Temp[J] Then  
                                          SWAP(Temp[I], Temp[Lok]); 
                                   End; 
                             Jarak := Jarak Div 2; 
                    End; 
          End;
  

         Kelebihan dan Kekurangan Shell Sort :

          Kelebihan :
  •          Operasi pertukarannya hanya sekali.
  • ·              Mudah menggabungkaannya kembali.


         Kekurangan :
  •               Membutuhkan metode tambahan.
  •               Sulit untuk membagi sebuah masalah pada data.




    5.   Quick Sort

      Metode ini dikembangkan oleh CAR Hoare. Secara garis besar metode ini dijelaskan sebagai berikut. Misalnya kita ingin mengurutkan data A yang membunyai N elemen. Kita pilih sembarang elemen dari data tersebut, biasanya elemen pertama, misalnya X. Kemudain semua elemen tersebut disusun dengan menempatkan X pada posisi J sedemikian rupa shingga elemen ke 1 sampai ke J-1 mempuyai nilai lebih besar dari X. Sampai berikutnya diulang untuk  setiap sub data.

      Divide and conquer adalah metode pemecahan masalah yang bekerja dengan membagi (divide) masalah menjadi beberapa sub-masalah yang sama atau berhubungan, hingga masalah tersebut menjadi sederhana untuk dipecahkan (conquer) secara langsung. Pemecahan dari tiap-tiap sub-masalah kemudian digabungkan untuk memberikan solusi terhadap masalah semula[6].

      Metode divide and conquer menawarkan penyederhanaan masalah dengan pendekatan tiga langkah sederhana: pembagian masalah menjadi sekecil mungkin, penyelesaian masalah-masalah yang telah dikecilkan, kemudian digabungkan kembali untuk mendapat solusi optimal secara keseluruhan. Khusus untuk quicksort, proses penggabungan (combine) tidak perlu dilakukan, karena sudah terjadi secara alami.

       Dalam penerapannya metode ini dilakukan secara rekursif, yaitu memanggil dirinya sendiri. Cara  pemanggilan ini memanfaatkan mekanisme stack dalam menyimpan data yang sedang diproses.  Namun bisa juga dengan versi non-rekursif yaitu dengan membuat struktur data tertentu yang meniru  cara kerjastack.

       Strategi divide-and-conqueror digunakan di dalam quicksort. Di bawah iniakan dijelaskan langkah-langkahnya :

  •  ·       Pilih nilai pivot Kita ambil nilai di tengah-tengah elemen sebagai sebagai nilaidari pivot  tetapi  bisa nilai mana saja.
  •     ·  Partisi  Atur ulang semua elemen sedemikian rupa, lalu semua elemen yang lebihrendah daripada pivot dipindahkan ke sebelah kiri dari array/list dan semuaelemen yang lebih besar dari  pivot dipindahkan ke sebelah kanan dari array/list. Nilai yang sama dengan pivot  dapat diletakkan di mana saja dari array. Ingat,mungkin array/list akan dibagi dalam bagian yang tidak sama.
  • ·        Urutkan semua bagian (kiri/kanan)  Aplikasikan algoritma quicksort secararekursif pada bagian sebelah kiri dan kanan.





          Contoh dari proses Soring dengan menggunakan metode Quick Sort :



       Contoh Kasus :
        Dalam  Pascal :

       Procedure Quick(Var Temp : Data; Awal, Akhir : Integer); 
       Var
              I,J : Integer; 
       Procedure ATUR; 
                      Begin 
                            I:=Awal +1; 
                            J:= Akhir; 
                            While Temp[I] < Temp[Awal] Do Inc(I);
                            While Temp[J] > Temp[Awal] Do Dec(J); 
                            While I < J Do 
                            Begin 
                                     SWAP(Temp[I], Temp[J]); 
                                     While Temp[I] < Temp[Awal] Do Inc(I); 
                                     While Temp[J] > Temp[Awal] Do Dec(J); 
                            End; 
                      SWAP(Temp[Awal], Temp[J]); 
                      End; 
                      Begin 
                             If Awal < Akhir Then 
                                     Begin 
                                              ATUR; 
                                                       Quick(Temp, Awal, J-1); 
                                                       Quick(Temp,J+1,Akhir); 
                                     End; 
        End;


        Kelebihan dan Kekurangan Quick Sort :

         Kelebihan :
  •        Secara umum memiliki kompleksitas O(n log n).
  •              Algoritmanya sederhana dan mudah diterapkan pada berbagai bahasa pemrograman.
  •              Dalam prakteknya adalah yang tercepat dari berbagai algoritma pengurutan dengan perbandingan.
  •        Melakukan proses langsung pada input (in-place) dengan sedikit tambahan memori.
  •                Bekerja dengan baik pada berbagai jenis input data (seperti angka dan karakter).


   Kekurangan :
  •                 Sedikit kesalahan dalam penulisan program membuatnya bekerja tidak beraturan (hasilnya tidak benar atau tidak pernah selesai).
  •                  Ttidak Stabil.



6.   Merge Sort (Metode Penggabungan)


      Merupakan metode pengurutan data dengan cara data dibagi menjadi subkumpulan - subkumpulan yang kemudian subkumpulan tersebut diurutkan secara terpisah, dan kemudian digabungkan kembali dengan metode merging.
     Merge sort merupakan algoritma pengurutan dalam ilmu komputer yang dirancang untuk memenuhi kebutuhan pengurutan atas suatu rangkaian data yang tidak memungkinkan untuk ditampung dalam memori komputer karena jumlahnya yang terlalu besar. Algoritma ini ditemukan oleh John von Neumann pada tahun 1945.

Algoritma pengurutan data merge sort dilakukan dengan menggunakan cara divide and conquer yaitu dengan memecah kemudian menyelesaikan setiap bagian kemudian menggabungkannya kembali. Pertama data dipecah menjadi 2 bagian dimana bagian pertama merupakan setengah (jika data genap) atau setengah minus satu (jika data ganjil) dari seluruh data, kemudian dilakukan pemecahan kembali untuk masing-masing blok sampai hanya terdiri dari satu data tiap blok.

Setelah itu digabungkan kembali dengan membandingkan pada blok yang sama apakah data pertama lebih besar daripada data ke-tengah+1, jika ya maka data ke-tengah+1 dipindah sebagai data pertama, kemudian data ke-pertama sampai ke-tengah digeser menjadi data ke-dua sampai ke-tengah+1, demikian seterusnya sampai menjadi satu blok utuh seperti awalnya. Sehingga metode merge sort merupakan metode yang membutuhkan fungsi rekursi untuk penyelesaiannya.

      Contoh Kasus : 

     void mergeSort (int *T, int *temp, int Nmax)
/*I.S. T tabel dgn elemen bertipe*/
/* integer, T tidak kosong*/
/*F.S T terturut menaik*/
/* Proses : melakukan pengurutan*/
/*         dengan melakukan metode sort*/
{
m_sort (T, temp, 0, Nmax -1);
}
void m_short (int *T, int *temp, int *left, int *right)
{
int mid;
if (*right > *left)
{
mid = (*right + *left) / 2;
m_sort (T, temp, left, mid);
m_sort (T, temp, mid+1, right);
merge (T, temp, left, mid+1, right);
}
}
void merge(int *T, int * temp, int left, int mid, int right)
{
int i, left_end, num_elements, tmp_pos;
     left_end + mid-1;
tmp_pos = left;
num_elements = right – left + 1;
while ((left <= left_end) && (mid <= right))
{
if (*T[left] <= *T[mid])
{
*temp[tmp_pos] = *T[left];
tmp_pos = tmp_pos +1;
left = left +1;
}
else
{
*temp [tmp_pos] = *T [mid];
tmp_pos = tmp_pos + 1;
mid = mid +1;
}
}
while (left <= left_end);
{
*temp[tmp_pos] = *T[left];
left = left +1;
tmp_pos = tmp_pos +1;
}
while (mid <= right)
{
*temp [tmp_pos] = *T [mid];
mid = mid +1;
tmp_pos = tmp_pos + 1;
}
for (i=0; i <= num_elements; i++)
{
*T[right] = *temp[right];
right = right -1;
}
}


Kelebihan dan Kekurangan Merge Sort :

Kelebihan :
  •        Sangat sederhana.
  •        Sangat efisien untk data yang sangat kecil.
  •        Prosesnya yang cepat.


Kekurangan :
  •       Banyak operasi yang dilakukan.
  •       Kinerja buruk atau kurang efisien  jika data dalam jumlah yang besar.




           7.   Radix Sort


      Radix Sort adalah metode sorting tanpa pembandingan dengan kata lain, sorting Non Comparasion sort dimana dalam prosesnya tidak melakukan perbandingan antar data. Secara       umum yang proses yang dilakukan dalam metode ini adalah mengklasifikasikan data sesuai         dengan kategori terurut yang tertentu dan dalam tiap kategorinya dilakukan pengklasifikasian  lagi dan seterusnya sesuai dengan kebutuhan. Dan kemudian subkategori-subkategori tersebut  digabungkan kembali, yang secara dilakukan hanya dengan metode sederhana concatenation.
      Apa itu Radix Sort? Radix Sort merupakan algoritma pengurutan yang ajaib yang mana mengatur pengurutan nilainya tanpa melakukan beberapa perbandingan pada data yang dimasukkan. Kata radix bermakna harafiah posisi dalam angka [1]. Di mana sederhananya, dalam representasi desimal, radix adalah digitnya. Dalam implementasinya, Radix Sort merupakan algoritma pengurutan yang cepat, mudah, dan sangat efektif. Namun banyak orang yang berpikir bahwa algoritma ini memiliki banyak batasan di mana untuk kasus-kasus tertentu tidak dapat dilakukan dengan algoritma ini, seperti pengurutan bilangan pecahan dan bilangan negatif,
     Berdasarkan urutan pemrosesan radixnya, Radix Sort terbagi 2 macam, yaitu: LSD (Least Significant Digit), di mana pemrosesan dimulai dari radix yang paling tidak signifikan. dan MSD (Most Significant Digit), di mana pemrosesan dimulai dari radix yang paling signifikan.
     Proses dasar Radix Sort adalah mengkategorikan data-data menjadi subkumpulan-subkumpulan data sesuai dengan nilai radix-nya, mengkonkatenasinya, kemudian mengkategorikannya kembali berdasar nilai radix lainnya.
Contoh Kasus : 
Dalam C++ :

Realisasi radix sort di C dapat dilihat pada Script di bawah ini :
//program C++ Redix Short
#include <stdio.h>
#define MAX 20
#define SHOWPASS
#define BASE 10
void print(int *a, int n)
{
  int i;
  for (i = 0; i < n; i++)
    printf("%d\t", a[i]);
}

void radixsort(int *a, int n)
{
  int i, b[MAX], m = a[0], exp = 1;

  //Get the greatest value in the array a and assign it to m
  for (i = 1; i < n; i++)
  {
    if (a[i] > m)
      m = a[i];
  }

  //Loop until exp is bigger than the largest number
  while (m / exp > 0)
  {
    int bucket[BASE] = { 0 };

    //Count the number of keys that will go into each bucket
    for (i = 0; i < n; i++)
      bucket[(a[i] / exp) % BASE]++;

    //Add the count of the previous buckets to acquire the indexes after the end of each bucket location in the array
    for (i = 1; i < BASE; i++)
      bucket[i] += bucket[i - 1]; //similar to count sort algorithm i.e. c[i]=c[i]+c[i-1];

    //Starting at the end of the list, get the index corresponding to the a[i]'s key, decrement it, and use it to place a[i] into array b.
    for (i = n - 1; i >= 0; i--)
      b[--bucket[(a[i] / exp) % BASE]] = a[i];

    //Copy array b to array a
    for (i = 0; i < n; i++)
      a[i] = b[i];

    //Multiply exp by the BASE to get the next group of keys
    exp *= BASE;

    #ifdef SHOWPASS
      printf("\nPASS   : ");
      print(a, n);
    #endif
  }
}

int main()
{
  int arr[MAX];
  int i, n;
  printf("Enter total elements (n <= %d) : ", MAX);
  scanf("%d", &n);
  n = n < MAX ? n : MAX;

  printf("Enter %d Elements : ", n);
  for (i = 0; i < n; i++)
    scanf("%d", &arr[i]);

  printf("\nARRAY  : ");
  print(&arr[0], n);

  radixsort(&arr[0], n);

  printf("\nSORTED : ");
  print(&arr[0], n);
  printf("\n");

  return 0;
}


Kelebihan dan Kekurangan Redix Short :

 Kelebihan :
  •              Sangat efektif untuk data yang besar.
  •               Konsep Algoritma mudah dipahami


 Kekurangan :
  •         Realisasi program rumit dan kurang fleksibel untuk digunakan pada tipe data lain.



8.   Heap Sort

      Heap sort adalah algoritma yang paling lambat daripada algoritma yang memiliki kompleksitas  0(n long n) lebih unggul daripada algoritma marge sort dan quick sort karena tidak memerlukan  rekursif yang besar. Untuk itu heap sort sangatlah cocok sebuah kumpulan data yang besar.

     Algoritma ini bekerja dengan menentukan elemen terbesar atau elemen terkecil dari sbuah daftar   element, yang kemudian diletakkan di akhir atau di awal dari daftar tersebut.
     Algoriyma ini diawali dengan membuat array heap dgn membangun tumpukan dari kumpulan data kemudian memindahkan data dari terbesar ke bagian belakang dari sebuah table hasil, kemudian array heap tersebut dibangun kembali untuk mengambil elemen terbesar yang kemudian diletakkan di sebelah item yang telah dipindahkan tadi. Hal ini diulang-ulang sampai array heap habis.



Contoh Kasus :

 Dalam C++ :

/heap sort
#include <iostream>
#include <conio.h>
using namespace std;
void max_heapify(int *a, int i, int n)
{
    int j, temp;
    temp = a[i];
    j = 2*i;
    while (j <= n)
    {
        if (j < n && a[j+1] > a[j])
            j = j+1;
        if (temp > a[j])
            break;
        else if (temp <= a[j])
        {
            a[j/2] = a[j];
            j = 2*j;
        }
    }
    a[j/2] = temp;
    return;
}
void heapsort(int *a, int n)
{
    int i, temp;
    for (i = n; i >= 2; i--)
    {
        temp = a[i];
        a[i] = a[1];
        a[1] = temp;
        max_heapify(a, 1, i - 1);
    }
}
void build_maxheap(int *a, int n)
{
    int i;
    for(i = n/2; i >= 1; i--)
    {
        max_heapify(a, i, n);
    }
}
int main()
{
    int n, i, x;
    cout<<"enter no of elements of array\n";
    cin>>n;
    int a[20];
    for (i = 1; i <= n; i++)
    {
        cout<<"enter element"<<(i)<<endl;
        cin>>a[i];
    }
    build_maxheap(a,n);
    heapsort(a, n);
    cout<<"sorted output\n";
    for (i = 1; i <= n; i++)
    {
        cout<<a[i]<<endl;
    }
    getch();
}


Kelebihan dan Kekurangan Heap Sort :

Kelebihan :
  •        Baik digunakan pada larik yang banyak atau sedikit.
  •        Proses Cepat.

Kekurangan :
  •       Menggunakan banyak operasi.




        Referensi :
:


  



  



Diposting oleh di

1 komentar:

Langganan: Posting Komentar (Atom)