asads
U2FsdGVkX1+oAnwbnskvya69szTjdFpGybhS2NzdrKHSjoJTr08Mjc5tbPuHiBiBO8XlWYvlkceixZrnmV7xdQ==

Baca Juga

Belajar Pemrograman Materi Sorting pada C++ (Shell Sort, Radix Sort, Merge Sort, Quick Sort)

Sorting Pada C++ - Sorting atau lebih dikenal dengan sebutan pengurutan data pada sebuah struktur data sangat penting. Pengurutan data atau Sorting ini dapat dilakukan pada data yang bersifat numerik maupun karakter. Sorting dapat 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 berdasarkan perbandingan
a. Bubble Sort
b. Exchange Sort

2. Pengurutan tanpa perbandingan
a. Radix Sort

3. Pengurutan berdasarkan prioritas
a. Selection Sort
b. Heap Sort

4. Pengurutan berdasarkan penyisipan dan penjagaan terurut
a. Insertion Sort
b. Tree Sort

5. Pengurutan berdasarkan 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 adalah Bubble Sort, Selection Sort dan Insertion Sort. Namun pada saat ini, Algoritma Sorting yang sekarang kita pelajari yaitu adalah 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 adalah 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 adalah dengan membandingkan suatu data yang ada dengan data lain yang memiliki jarak tertentu sehingga membentuk sebuah sub-list, kemudian dilakukan pertukaran data jika diperlukan. Jarak yang dipakai berdasarkan pada increment value atau disebut dengan Sequence Number. Sequence Number tersebut akan menjadi sebuah sub-list dari kumpulan elemen yang asli.

Misalnya pada contoh kasus Sequence Number (k) = 5, maka sublist nya adalah sebagai berikut :

s[0] s[5] s[10] dst

Proses untuk menentukan yang terjadi pada Shell Sort adalah sebagai berikut :

1. Buat sub list berdasarkan 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 adalah 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 adalah 1.

Misalnya contoh untuk pengurutan Shell Sort :

Data pada array yang telah dibuat sebagai berikut :
Belajar Pemrograman Materi Sorting pada C++ (Shell Sort, Radix Sort, Merge Sort, Quick Sort)


Berdasarkan dari data diatas, maka telah didapat jumlah array atau jumlah data pada diatas adalah N = 8

*catatan : N adalah jumlah data

Jika sudah diperoleh dengan N = 8. Maka selanjutnya kita menentukan Sequence Number tersebut dengan cara menentukan Sequence Number pada Shell Sort sebagai berikut :

K1 = Sequence Number 1 : 8/2 = 4
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, melakukan perbandingan atau membandingkan dengan data yang lain yang telah ditentukan jarak sequence number yang telah kita dapat tadi sebagai berikut :
Belajar Pemrograman Materi Sorting pada C++ (Shell Sort, Radix Sort, Merge Sort, Quick Sort)
Belajar Pemrograman Materi Sorting pada C++ (Shell Sort, Radix Sort, Merge Sort, Quick Sort)

Belajar Pemrograman Materi Sorting pada C++ (Shell Sort, Radix Sort, Merge Sort, Quick Sort)



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 :
Belajar Pemrograman Materi Sorting pada C++ (Shell Sort, Radix Sort, Merge Sort, Quick Sort)



B. Radix Sort 
Radix Sort merupakan metode sorting yang mengurutkan data berdasarkan posisi digit angka atau sebuah karakter pada sebuah string. Pengurutan dengan menggunakan Radix Sort ini dapat dilakukan dengan posisi digit terakhir atau terkanan LSD (Least Significant Digit) atau digit paling awal atau terkiri atau MSD (Most Significant Digit). 

Misalnya n adalah sebuah inputan dan d adalah jumlah maksimal digit data yang dimiliki. Algoritma pengurutan Radix Sort ini dapat diselesaikan menggunakan pengurutan yang dimulai dari digit paling terkecil maupun terbesar. 

Langkah - langkah sederhana mengurutkan data dengan menggunakan Radix Sort pada pemrograman :

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 menggunakan Radix Sort pada sebuah tipe data String :
Belajar Pemrograman Materi Sorting pada C++ (Shell Sort, Radix Sort, Merge Sort, Quick Sort)

Contoh pengurutan dengan menggunakan Radix Sort pada sebuah tipe data Numerik atau Integer :
Belajar Pemrograman Materi Sorting pada C++ (Shell Sort, Radix Sort, Merge Sort, Quick Sort)

Belajar Pemrograman Materi Sorting pada C++ (Shell Sort, Radix Sort, Merge Sort, Quick Sort)

Belajar Pemrograman Materi Sorting pada C++ (Shell Sort, Radix Sort, Merge Sort, Quick Sort)

Belajar Pemrograman Materi Sorting pada C++ (Shell Sort, Radix Sort, Merge Sort, Quick Sort)

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 dapat 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 :
Belajar Pemrograman Materi Sorting pada C++ (Shell Sort, Radix Sort, Merge Sort, Quick Sort)


C. Merge Sort
Merge dan Quick merupakan dua metode pengurutan dengan menggunakan 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 dapat dibagi lagi (data tunggal telah diperoleh). Apabila data yang dibagi tidak dapat dipecah lagi, maka proses selanjutnya adalah penggabungan (merging) antara sub - sub bagian 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 :
Belajar Pemrograman Materi Sorting pada C++ (Shell Sort, Radix Sort, Merge Sort, Quick Sort)


Dari ilustrasi gambar penerapan Algoritma Merge Sort diatas dapat dijabarkan menggunakan Pseudocode Merge Sort sebagai berikut :
Belajar Pemrograman Materi Sorting pada C++ (Shell Sort, Radix Sort, Merge Sort, Quick Sort)

Belajar Pemrograman Materi Sorting pada C++ (Shell Sort, Radix Sort, Merge Sort, Quick Sort)


D. Quick Sort 
Metode Quick Sort ini sama seperti Merge Sort, hanya saja quick sort memiliki 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 dapat diambil pada nilai tengah yang ada pada array data. 
2. Partisi, setelah memperoleh nilai pivot yaitu melakukan partisi atau pembagian pada array berdasarkan 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 adalah melakukan pengurutan secara quick sort rekursif pada bagian kiri dan kanan. 

Ilustrasi gambar Pengurutan data pada Algoritma Quick Sort :

Data yang akan diurutkan :

{1, 12, 5, 26, 7, 14, 3, 7, 2}

Belajar Pemrograman Materi Sorting pada C++ (Shell Sort, Radix Sort, Merge Sort, Quick Sort)

Belajar Pemrograman Materi Sorting pada C++ (Shell Sort, Radix Sort, Merge Sort, Quick Sort)

Itulah beberapa contoh program dan source code radix sort, shell sort, merge sort, dan quick sort. Jika masih bingung dengan materi diatas, silahkan bertanya melalui kolom komentar dibawah ini. Mudah - mudah artikel ini sangat bermanfaat untuk anda yang sedang ingin belajar bahasa pemrograman C++ sampai mahir. Inilah ilmu yang saya dapatkan dari tempat kuliah saya, disini juga kita masih belajar. Tidak ada salahnya untuk berbagi ilmu kepada kalian yang sama - sama ingin belajar pemrograman C++ sampai mahir dan jago. 
Loading...