Sorting Pada C++ - Sorting atau lebih dikenal dengan sebutan pengurutan data pada sebuah struktur data sangat penting. Pengurutan data atau Sorting ini sanggup dilakukan pada data yang bersifat numerik maupun karakter. Sorting sanggup dilakukan secara Ascending (urut naik) ataupun Descending (urut turun). Ada beberapa metode - metode dalam pengurutan data atau sorting diataranya sebagai berikut :
Metode Dalam Sorting :
1. Pengurutan menurut perbandingan
a. Bubble Sort
b. Exchange Sort
2. Pengurutan tanpa perbandingan
a. Radix Sort
3. Pengurutan menurut prioritas
a. Selection Sort
b. Heap Sort
4. Pengurutan menurut penyisipan dan penjagaan terurut
a. Insertion Sort
b. Tree Sort
5. Pengurutan menurut pembagian dan penguasaan
a. Quick Sort
b. Merge Sort
6. Pengurutan berkurang menurun
a. Shell Sort
Beberapa metode sorting yang sudah dipelajari di Algoritma dan Pemrogaraman yang dasar ialah Bubble Sort, Selection Sort dan Insertion Sort. Namun pada ketika ini, Algoritma Sorting yang kini kita pelajari yaitu ialah Radix Sort, Shell Sort, Quick Sort, dan Merge Sort.
Contoh Pemrograman Shell Sort, Radix Sort, Quick Sort dan Merge Sort
A. Shell Sort
Shell Sort ini ialah metode Algoritma Sorting yang dikembangkan oleh Donald L. Shell pada tahun 1959. Metode Shell Sort ini merupakan metode yang dilakukan penambahan secara menurun atau diminishing increment sort. Cara mengurutkan data pada metode Shell Sort ini ialah dengan membandingkan suatu data yang ada dengan data lain yang mempunyai jarak tertentu sehingga membentuk sebuah sub-list, kemudian dilakukan pertukaran data kalau diperlukan. Jarak yang digunakan menurut pada increment value atau disebut dengan Sequence Number. Sequence Number tersebut akan menjadi sebuah sub-list dari kumpulan elemen yang asli.
Misalnya pada referensi kasus Sequence Number (k) = 5, maka sublist nya ialah sebagai berikut :
s[0] s[5] s[10] dst
Proses untuk memilih yang terjadi pada Shell Sort ialah sebagai berikut :
1. Buat sub list menurut jarak atau sequence number yang telah dipilih.
2. Urutkan masing - masing sub list tersebut
3. Gabungkan seluruh sublist yang ada
4. Disarankan pada jarak awal dari data yang akan dibandingkan yaitu ialah N/2
5. Proses berikutnya, gunakan jarak (N/2)/2 atau N/4
6. Proses selanjutnya gunakan jarak (N/4)/2 atau N/8
7. Demikian seterusnya hingga sequence number yang digunakan tersebut ialah 1.
Misalnya referensi untuk pengurutan Shell Sort :
Data pada array yang telah dibentuk sebagai berikut :
Berdasarkan dari data diatas, maka telah didapat jumlah array atau jumlah data pada diatas ialah N = 8
*catatan : N ialah jumlah data
Jika sudah diperoleh dengan N = 8. Maka selanjutnya kita memilih Sequence Number tersebut dengan cara memilih Sequence Number pada Shell Sort sebagai berikut :
K2 = Sequence Number 2 : 8/4 = 2
K3 = Sequence Number 3 : 8/8 = 1
Maka telah diperoleh yaitu K1 = 4, K2 = 2, K3 = 1.
Proses selanjutnya yaitu, melaksanakan perbandingan atau membandingkan dengan data yang lain yang telah ditentukan jarak sequence number yang telah kita sanggup tadi sebagai berikut :
Contoh Program Shell Sort pada Pemrograman C++ :
Source Code Shell Sort :
#include<iostream>
#include<conio.h>
#include<stdlib.h>
using namespace std;
int main() {
int array;
cout << "Penerapan algoritma Shell Sort\n";
cout << "Masukkan panjang array: ";cin>>array;
int arr_sorting[array], a, k,j, i, t;
cout << "\nMasukkan " << array << " Data yang akan diurutkan : " << endl;
for (i = 0; i < array; i++)
{
cout<<"Data ke- "<<i+1<<": ";
cin >> arr_sorting[i];
}
cout << "\nData anda :";
for (i = 0; i < array; i++) {
cout << "\t" << arr_sorting[i];
}
for (i = array / 2; i > 0; i = i / 2) {
for (j = i; j < array; j++) {
for (k = j - i; k >= 0; k = k - i) {
if (arr_sorting[k + i] >= arr_sorting[k])
break;
else {
t = arr_sorting[k];
arr_sorting[k] = arr_sorting[k + i];
arr_sorting[k + i] = t;
}
}
cout << "\nPengulangan Shell Sort " << i << " : " << j;
for (a = 0; a < array; a++) {
cout << "\t" << arr_sorting[a];
}
}
}
cout << "\n\nData yang telah diurutkan dengan algoritma Shell Sort :\n";
for (i = 0; i < array; i++) {
cout << "\t" << arr_sorting[i];
}
getch();
}
Tampilan Program :
B. Radix Sort
Radix Sort merupakan metode sorting yang mengurutkan data menurut posisi digit angka atau sebuah abjad pada sebuah string. Pengurutan dengan memakai Radix Sort ini sanggup dilakukan dengan posisi digit terakhir atau terkanan LSD (Least Significant Digit) atau digit paling awal atau terkiri atau MSD (Most Significant Digit).
Misalnya n ialah sebuah inputan dan d ialah jumlah maksimal digit data yang dimiliki. Algoritma pengurutan Radix Sort ini sanggup diselesaikan memakai pengurutan yang dimulai dari digit paling terkecil maupun terbesar.
1. Ambil nilai maksimal dari inputan array yaitu d
2. Mulai dari digit paling kecil, kemudian urutkan data tersebut
3. Ambil data sebagai inputan untuk digit selanjutnya
4. Lakukan pengulangan hingga digit d
5. Tampilkan hasilnya
6. Selesai
Contoh pengurutan dengan memakai Radix Sort pada sebuah tipe data String :
Contoh pengurutan dengan memakai Radix Sort pada sebuah tipe data Numerik atau Integer :
Contoh Program Radix Sort pada Pemrograman C++ :
Source Code Radix Sort :
#include<stdlib.h>
#include<stdio.h>
#include<conio.h>
#include<iostream>
#define MAX 10
#define DESIMAL 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;
for (i = 1; i < n; i++)
{
if (a[i] > m)
m = a[i];
}
while (m / exp > 0)
{
int paket[DESIMAL] = {0};
for (i = 0; i < n; i++)
paket[(a[i] / exp) % DESIMAL]++;
for (i = 1; i < DESIMAL; i++)
paket[i] += paket[i - 1];
for (i = n - 1; i >= 0; i--)
b[--paket[(a[i] / exp) % DESIMAL]] = a[i];
for (i = 0; i < n; i++)
a[i] = b[i];
exp *= DESIMAL;
printf("\nUrutan : ");
print(a, n);
}
}
int main()
{
int arr[MAX];
int i, n;
printf("Masukkan jumlah data yang akan diurutkan : ", MAX);
scanf("%d", &n);
if(n>10)
{
printf("Data yang sanggup dimasukan maksimal 10\n");
system("PAUSE");
return 0;
}
n = n < MAX ? n : MAX;
printf("\nMasukkan %d Data\n", n);
for (i = 0; i < n; i++)
{
printf("Data ke-%d: ",i+1);
scanf("%d", &arr[i]);
}
printf("\nARRAY : ");
print(&arr[0], n);
radixsort(&arr[0], n);
printf("\nData Terurut : ");
print(&arr[0], n);
printf("\n");
system("PAUSE");
return 0;
}
Tampilan Program :
C. Merge Sort
Merge dan Quick merupakan dua metode pengurutan dengan memakai teknik secara pembagian dan penguasaan (devide and conquer method). Algoritma pada Merge Sort ini akan membagi data secara rekursif hingga memenuhi suatu kondisi tertentu atau terminated condition is true. Terminated condition is true ini pada sebuah algoritma Merge Sort yaitu apabila data tidak sanggup dibagi lagi (data tunggal telah diperoleh). Apabila data yang dibagi tidak sanggup dipecah lagi, maka proses selanjutnya ialah penggabungan (merging) antara sub - sub bab dengan melihat dan memperhatikan pengurutan data yang diinginkan apakah secara Ascending (ASC) atau secara Descending (DSC). Lakukan proses penggabungan ini hingga seluruh data telah digabungkan sesuai urutan. Kompleksitas algoritma Merge Sort ini ada n Log n.
Ilustrasi gambar penerapan pada Algoritma Merge Sort :
Dari ilustrasi gambar penerapan Algoritma Merge Sort diatas sanggup dijabarkan memakai Pseudocode Merge Sort sebagai berikut :
D. Quick Sort
Metode Quick Sort ini sama ibarat Merge Sort, hanya saja quick sort mempunyai kompleksitas 0 (n log n), sehingga dari algoritma quick sort ini sangat cocok untuk mengurutkan pada volume data yang besar.
Langkah - Langkah sederhana Metode Algoritma Quick Sort :
1. Pertama, pilih nilai Pivot. Nilai pivot ini sanggup diambil pada nilai tengah yang ada pada array data.
2. Partisi, sesudah memperoleh nilai pivot yaitu melaksanakan partisi atau pembagian pada array menurut pivot. Apabila data yang akan diurutkan secara Ascending (ASC) maka, seluruh data yang lebih kecil dari pivot letakkan di sebelah kiri dan seluruh data yang lebih besar diletakkan disebelah kanan pivot. Begitu juga dengan sebaliknya apabila ingin mengurutkan data secara Descending (DSC).
3. Sorting kedua bagian. Langkah terakhir ialah melaksanakan pengurutan secara quick sort rekursif pada bab kiri dan kanan.
Data yang akan diurutkan :
{1, 12, 5, 26, 7, 14, 3, 7, 2}
Itulah beberapa contoh aktivitas dan source code radix sort, shell sort, merge sort, dan quick sort. Jika masih resah dengan materi diatas, silahkan bertanya melalui kolom komentar dibawah ini. Praktis - gampang artikel ini sangat bermanfaat untuk anda yang sedang ingin belajar bahasa pemrograman C++ hingga mahir. Inilah ilmu yang saya dapatkan dari daerah kuliah saya, disini juga kita masih belajar. Tidak ada salahnya untuk mengembangkan ilmu kepada kalian yang sama - sama ingin mencar ilmu pemrograman C++ hingga mahir dan jago.
Sumber https://soymedia.blogspot.com/