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 wacana 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 sanggup 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 yakni 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 menurut radix pertamanya, kemudian diteruskan atau diurutkan lagi menurut radix keduanya, dst…

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

Contoh algoritma radix sort untuk mengurutkan bilangan bundar 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 memilih 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 terperinci 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 klarifikasi diatas ;

321

313

123

543

354

834

675

756

Tabel 1.2

Kemdian dilakukan pengkategorian kembali menurut 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 balasannya sanggup dituliskan :

123

313

321,

354

543

675

756

834

Table 1.6

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

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

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

Contoh jadwal 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 yakni algoritma sorting yang menurut pembanding dengan metode divide and conqueror, sangat berbeda dengan Radix Sort yang tanpa pembanding. Disebut Quick Sort sebab algoritma Quick Sort mengurutkan dengan sangat cepat atau Quick Sort juga bias disebut dengan exchange sort, sebab konsepnya yang menciptakan partisi2 dan Sort yang dilakukan tiap partisi.

Kelebihan :

·   Algoritma sederhana dan gampang diterapkan pada banyak sekali bahasa pemrograman dan arsitektur mesin secara efisien.

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

· Melakukan proses secara pribadi pada input(in-place) dengan sedikit komplemen memory.

·   Bias dipakai dgn baik untuk input angka daan karakter

Kekurangan :

·         Sedikit kesalahan saja didalam jadwal sanggup menyebablkan  jadwal tidak beraturan atau outputan tidak benar bahkan sanksi tidak akan pernah selesai.

·         Memiliki ketergantungan terhadap data yang dimasukkan.

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

sama.

·         Memiliki katergantungan terhadap data yang dimasukkan.

·         Pada penerapan rekursif(memanggil dirinya sendiri) bahkan dalam masalah terburuk sanggup mampu menghabiskan stack dan memacetkan rogram.

3.INSERTION SORT

Insertion Sort yakni 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 jelek 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 belahan yang mana belahan pertama merupakan setengah (jika datanya genap) dan stengah minus satu (jika datanya ganjil) dari seluruh data. Kemudian dilakukan pemacahan kembali untuk masing2 blok hingga 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 sesudah index ke-1), jikalau iya, maka data ke tengah+1 dipindah ke data yang pertama tadi, kemudian data yang pertama hingga ke tengah digesrt ke data yg ke-2 hingga ke tengah+1. Bingung ya gan , pribadi saja raktek dengan jadwal aja

5. HEAP SORT

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

Algoritma ini bekerja dengan memilih elemen terbesar atau elemen terkecil dari sbuah daftar element, yang kemudian diletakkan di tamat atau di awal dari daftar tersebut.

Algoriyma ini diawali dengan menciptakan array heap dgn membangun tumpukan dari kumpulan data kemudian memindahkan data dari terbesar ke belahan 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 hingga 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 duduk masalah pada data

7. BUBLE SORT

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

Simpelnya ialah bahwa bubble sort mengurutkan data dengan membandingkan elemen kini dengan elemen berikutnya, meskipun dibilang paling simple dan algoritmanya paling gampang untuk dipahami disisi lain bubble sort mempunyai kelemahan yg jauh lebih jelek daripada metode insertion sort misalkan saja jikalau jumlah data yang diolah cukup banyak maka data akan mengalami kelembatan yang sangat parah, sebab disetiap data akan dibandingkan untuk memilih 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); }