Pengurutan (SORTING) di C++

As-salamu'alaykum wr wb.
Lama ga posting artikel nih, maaf saya sibuk CBT Produktif hehe ..

oke , postingan kali ini saya akan membahas tentang shorting di C++ / Cplusplus hehe .. 

Q : Shorting itu apa sih ka? 

A : Shorting atau pengurutan adalah proses penyusunan kembali suatu data yang sebelumnya sudah disusun secara teratur sesuai dengan pola dan metode tertentu. Pengurutan bisa secara ascending(urut naik) atau descending(urut turun). Perlu anda ketahui bahwa pengurutan data dalam struktur data sangatlah penting terutama untuk data yang bersifat integer, pecahan, ataupun karakter.

Q : di C++ ada berapa macam shorting ka?

A : Ada banyak, Yuk kita bahas materi shorting .. hehe 

1. Radix Sort

Radix sort adalah algoritma non-comparation sort atau pengurutan tanpa perbandingan . metode ini mengklarifikisi sebuah data sesuai dengan kategori urutan tertentu. Dan setiap kategori diurutkan lagi dan seterusnya sesuai dengan kebutuhan. Kemudian bagian2 dari kategori tersebut akan digabungkan kembali.

Catatan : data yang diurutkan pertama kali yaitu berupa input nilai2 yang dimasukkan pertama kali berdasarkan radix pertamanya, lalu diteruskan atau diurutkan lagi berdasarkan radix keduanya, dst…

Pada system decimal radix adalah digit dalam angka decimal. Missal : angka 354 mempunyai 3 digit yaitu 3, 5 dan 4

Contoh algoritma radix sort untuk mengurutkan bilangan bulat positif, dengan jumlah digit maksimal 3 :

313

354

123

321

543

756

834

675

·         Pertama kita harus membagi-bagi data sesuai dengan urutan terkanan

·         Lihat terlebih dahulu digit yang paling besar untuk menentukan kategori berapa baris data yang akan kita urutkan, dan dicontoh ini nilai digit paling besar yaitu angka 8, sehingga kategori sebanyak 8 baris dan diawali dengan angka 0. Supaya lebih jelas lihat table dibawah :

Kategori digit 1	0	1	2	3	4	5	6	7	8
isi	-	321	-	313,123, 543	354,834	675	756	-	-

                                                            Tabel 1.1

 Hasil dari kategori pertama tadi akan digabungkan kembali sesuai dengan penjelasan diatas ;

321

313

123

543

354

834

675

756

                                                            Tabel 1.2

Kemdian dilakukan pengkategorian kembali berdasarkan dengan  digit yang ke-2 dengan berpatokan / melihat baris urutan dari pengkategorian yang pertama tadi yaitu (Tabel 1.2).

Kategori digit 2	0	1	2	3	4	5	6	7	8
isi	-	313	321,123	834	543	354,756	-	675	-

                                                            Tabel 1.3

Selanjutnya hasil dari pengkategorian ke-2 digabungkan kembali sehingga diperoleh :

313

321

123

834

543

354

756

675

                                                            Table 1.4

Langkah terakhir yaitu pengkategorian ke-3 berdasar digit ke-3 dengan berpatokan melihat baris urutan pengkategorian ke-2 yaitu (Tabel 1.4)

Kategori digit 3	0	1	2	3	4	5	6	7	8
isi	-	123	-	313,321, 354	-	543	675	756	834

                                                            Tabel 1.5

Jadi, hasil akhirnya dapat dituliskan :

123

313

321,

354

543

675

756

834

                                                            Table 1.6

Dari proses2 yang sudah kita kerjakan menggunakan Redix Sort, sangat jelas Radix sort termasuk algoritma pengurutan tanpa pembanding yang bersifat melihat digit2 angka sebagai pengontrolnya. Sebenarnya Radix Sort  dapat diimplementasikan dalam pengurutan bilangan Decimal dan bilangan bit. Namun dalam penggunaannya Radix Sort bisa dimodifikasi untuk mengurutkan data2 negatif & pecahan.

Kelebiha : merupakan algoritma pengurutan yang cepat, mudah dan sangat efektif

Kekurangan : pengguaannya terbatas pada kasus2 tertentu dan memerlukan memori tambahan yang besar dalam prosesnya mengkategorikan sebuah data.

Contoh program Radix Sort dengan Dev-C++

//Radix sort;

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

2. Quick Short

Quick Sort adalah algoritma sorting yang berdasarkan pembanding dengan metode divide and conqueror, sangat berbeda dengan Radix Sort yang tanpa pembanding. Disebut Quick Sort karena algoritma Quick Sort mengurutkan dengan sangat cepat atau Quick Sort juga bias disebut dengan exchange sort, karena konsepnya yang membuat partisi2 dan Sort yang dilakukan tiap partisi.

Kelebihan :

·   Algoritma sederhana dan mudah diterapkan pada berbagai bahasa pemrograman dan arsitektur mesin secara efisien.

·  Algoritma pengurutan yang lebih cepat dengan perbandingan seperti Marge Sort dan Heap Sort.

· Melakukan proses secara langsung pada input(in-place) dengan sedikit tambahan memory.

·   Bias digunakan dgn baik untuk input angka daan karakter

Kekurangan :

·         Sedikit kesalahan saja didalam program bisa menyebablkan  program tidak beraturan atau outputan tidak benar bahkan eksekusi tidak akan pernah selesai.

·         Memiliki ketergantungan terhadap data yang dimasukkan.

·         Sifatnya yg kurang stable karena input yang akan dirubah pada hasil akhirnya(output) bernilai

sama.

·         Memiliki katergantungan terhadap data yang dimasukkan.

·         Pada penerapan rekursif(memanggil dirinya sendiri) bahkan dalam kasus terburuk bisa dapat menghabiskan stack dan memacetkan rogram.

3.INSERTION SORT

Insertion Sort adalah sebuah metode pengurutan dgn cara menyisipkan 

elemen larik/array pada posisi yang tepat.

Keuntungan :

·         Sangat sederhana

·         Sangat efisien untk data yang sangat kecil misalkan data kurang dari 10 or 20

·         Prosesnya yang cepat

Kekurangan :

·         Banyak operasi yang dilakukan

·         Kinerja buruk atau kurang efisien  dika data dalam jumlah yang besar (tapi lebih baik daripada buble sort)

4. MARGE SORT

Marge Sort merupakan algoritma yang dirancang untuk memenuhi kebutuhan pengurutan atas rangkaian data  apabila suatu data tersebut tidak memungkinkan disimpan dalam memory computer yang kikarenakan jumlahnya yang terlalu besar.

Algoritma ini hampir sama dengan algoritma diatas yaitu memecah data yang kemudian digabungkan kembali. Bedanya pertama kita pecah data menjadi 2 bagian yang mana bagian pertama merupakan setengah (jika datanya genap) dan stengah minus satu (jika datanya ganjil) dari seluruh data. Kemudian dilakukan pemacahan kembali untuk masing2 blok sampai haanya terdiri 1 data dari tiap blok. Andthen menggabungkannya kembali dengan membandingkan pada blok yang sama apakah data yang pertama(data nilai pertama pada index ke-1) lebih besar dari pada data ke tengah+1(data setelah index ke-1), jika iya, maka data ke tengah+1 dipindah ke data yang pertama tadi, kemudian data yang pertama sampai ke tengah digesrt ke data yg ke-2 sampai ke tengah+1. Bingung ya gan , langsung saja raktek dengan program aja

5. 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.

Jadi kebanyakan metode ini memerlukan 2 buah table, satu tabel untuk menyimpan heap dan tabel yang lain untuk menyimpan hasil. 

6. SHELL SORT

Shell Sort merupakan perbaikan metode pengurutan sisip dan merupakan salahsatu algoritma sorting pada sebuah deklarasi array

Kelebihan :

·         Operasi pertukarannya hanya sekali

·         Mudah menggabungkaannya kembali

·         Kompleksitas selection relative lebih kecil

Kekurangan :

·         Membutuhkan methot tambahan

·         Sulit untuk membagi sbuah masalah pada data

7. BUBLE SORT

Bubble Sort adalah metode Sorting paling mudah. Diberi nama bubble karena proses pengurutannya secara berangsur-angsur bergerak / berpendah ke posisinya yang tepat, seperti gelembung yang keluar dari minuman bersoda.

Simpelnya ialah bahwa bubble sort mengurutkan data dengan membandingkan elemen sekarang dengan elemen berikutnya, meskipun dibilang paling simple dan algoritmanya paling mudah untuk dipahami disisi lain  bubble sort mempunyai kelemahan yg jauh lebih buruk daripada metode insertion sort misalkan saja jika jumlah data yang diolah cukup banyak maka data akan mengalami kelembatan yang sangat parah, karena disetiap data akan dibandingkan untuk menentukan posisinya.

SINTAX KESELURUHAN 

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

int data[100],data2[100];
int n;

void tukar(int a,int b)
{
int t;
t = data[b];
data[b] = data[a];
data[a] = t;
}

void bubble_sort()
{
for(int i=1;i<n;i++)
{
for(int j=n-1;j>=i;j–)
{
if(data[j]<data[j-1]) tukar(j,j-1);
}
}
cout<<“bubble sort selesai!”<<endl;
}

void exchange_sort()
{
for (int i=0; i<n-1; i++)
{
for(int j = (i+1); j<n; j++)
{
if (data [i] > data[j]) tukar(i,j);
}
}
cout<<“exchange sort selesai!”<<endl;
}

void selection_sort()
{
int pos,i,j;
for(i=0;i<n-1;i++)
{
pos = i;
for(j = i+1;j<n;j++)
{
if(data[j] < data[pos]) pos = j;
}
if(pos != i) tukar(pos,i);
}
cout<<“selection sort selesai!”<<endl;
}

void insertion_sort()
{
int temp,i,j;
for(i=1;i<n;i++)
{
temp = data[i];
j = i -1;
while(data[j]>temp && j>=0)
{
data[j+1] = data[j];
j–;
}
data[j+1] = temp;
}
cout<<“insertion sort selesai!”<<endl;
}

void QuickSort(int L, int R) //the best sort i’ve ever had 🙂
{
int i, j;
int mid;

i = L;
j = R;
mid = data[(L+R) / 2];

do
{
while (data[i] < mid) i++;
while (data[j] > mid) j–;

if (i <= j)
{
tukar(i,j);
i++;
j–;
};
} while (i < j);

if (L < j) QuickSort(L, j);
if (i < R) QuickSort(i, R);
}

void Input()
{
cout<<“Masukkan jumlah data = “; cin>>n;
for(int i=0;i<n;i++)
{
cout<<“Masukkan data ke-“<<(i+1)<<” = “; cin>>data[i];
data2[i] = data[i];
}
}

void Tampil()
{
cout<<“Data : “<<endl;
for(int i=0;i<n;i++)
{
cout<<data[i]<<” “;
}
cout<<endl;
}

void AcakLagi()
{
for(int i=0;i<n;i++)
{
data[i] = data2[i];
}
cout<<“Data sudah teracak!”<<endl;
}

void main()
{
int pil;
clrscr();
do
{
clrscr();
cout<<“Program Sorting Komplit!!!”<<endl;
cout<<“*********************************************”<<endl;
cout<<” 1. Input Data”<<endl;
cout<<” 2. Bubble Sort”<<endl;
cout<<” 3. Exchange Sort”<<endl;
cout<<” 4. Selection Sort”<<endl;
cout<<” 5. Insertion Sort”<<endl;
cout<<” 6. Quick Sort”<<endl;
cout<<” 7. Tampilkan Data”<<endl;
cout<<” 8. Acak Data”<<endl;
cout<<” 9. Exit”<<endl;
cout<<”    Pilihan Anda = “;  cin>>pil;
switch(pil)
{
case 1:Input(); break;
case 2:bubble_sort(); break;
case 3:exchange_sort(); break;
case 4:selection_sort(); break;
case 5:insertion_sort(); break;
case 6:QuickSort(0,n-1);
cout<<“quick sort selesai!”<<endl;
break;
case 7:Tampil(); break;
case 8:AcakLagi(); break;
}
getch();
}while(pil!=9);
}

Mungkin Cuman Sekian dari saya , was-salamu'alaykum wr wb.. 

hehe #RPLWajibNgulik 

Tweet