Pengurutan (Sorting) - Algoritma Pemrograman 2

Pengurutan (Sorting) pada C++

1). Definisi Sorting

Pengurutan data dalam struktur data sangat penting terutama untuk data yang beripe data numerik ataupun karakter. Pengurutan dapat dilakukan secara ascending (urut naik) dan descending (urut turun). Pengurutan (Sorting) adalah proses pengurutan data yang sebelumnya disusun secara acak sehingga tersusun secara teratur menurut aturan tertentu.

2). Deklarasi Array Sorting

Mendeklarasikan array secara global:

int data[100]; int n; //untuk jumlah data

Fungsi Tukar 2 Buah Data:

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

Sorting merupakan suatu proses untuk menyusun kembali himpunan obyek menggunakan aturan tertentu. Sorting disebut juga sebagai suatu algoritma untuk meletakkan kumpulan elemen data kedalam urutan tertentu berdasarkan satu atau beberapa kunci dalam tiap-tiap elemen.

Pada dasarnya ada dua macam urutan yang biasa digunakan dalam suatu proses sorting:

ü  Urut naik (ascending) Mengurutkan dari data yang mempunyai nilai paling kecil sampai paling besar.

ü  Urut turun (descending) Mengurutkan dari data yang mempunyai nilai paling besar sampai paling kecil.

3). Metode Sorting Data

Ada banyak alasan dan keuntungan dengan mengurutkan data. Data yang terurut mudah untuk dicari, mudah untuk diperiksa, dan mudah untuk dibetulkan jika terdapat kesalahan. Data yang terurut dengan baik juga mudah untuk dihapus jika sewaktu-waktu data tersebut tidak diperlukan lagi. Selain itu, dengan mengurutkan data maka kita semakin mudah untuk menyisipkan data atapun melakukan  penggabungan data.

Metode – metode sorting meliputi :

a). Metode Bubble Sort

Bubble Sort merupakan cara pengurutan yang sederhana. Konsep dari ide dasarnya adalah seperti “gelembung air” untuk elemen struktur data yang semestinya berada  pada posisi awal. Cara kerjanya adalah dengan berulang-ulang melakukan proses looping terhadap elemen-elemen struktur data yang belum diurutkan. Di dalam proses looping tersebut,nilai dari dua elemen struktur data dibandingkan. Jika ternyata urutannya tidak sesuai dengan “pesanan”,maka dilakukan pertukaran (swap). Algoritma sorting ini disebut juga dengan comparison sort dikarenakan hanya mengandalkan perbandingan nilai elemen untuk mengoperasikan elemennya.

Algoritma bubble sort dapat diringkas sebagai berikut, jika N adalah panjang elemen struktur data, dengan elemen-elemennya adalah T1, T2, T3, …, TN-1,TN, maka:

ü  Lakukan looping  untuk membandingkan dua elemen berdekatan. Looping ini dilakukan dari belakang.

ü  Jika elemen pada TN-1 > TN , maka lakukan  pertukaran (swap). Jika tidak, lanjutkan ke  proses looping berikutnya sampai bertemu dengan bagian struktur data yang telah diurutkan.

ü  Ulangi langkah di atas untuk struktur data yang tersisa.

Contoh program Bubble Sorting :

#include <iostream> #include <iomanip> #include <conio.h> using namespace std; main() {     int S[8]={1,4,90,34,2,6,4,10};     int temp;     cout<<"Data Sebelum Diurutkan : "<<endl;     for (int a=0; a<8;a++)     {         cout<<setw(4)<<S[a];     }     cout<<endl<<endl;     for (int b=0;b<7;b++)         for (int c=0;c<7;c++)         if (S[c]>=S[c+1])     {         temp=S[c];        S[c]=S[c+1];        S[c+1]=temp;     }     cout<<"Data Setelah Diurutkan : "<<endl;     for(int d=0; d<8;d++)         cout<<setw(3)<<S[d]<<endl<<endl;     getch(); }

Penjelasan :

Program diatas merupakan program untuk Bubble Sort. Pada program diatas data yang akan diurutkan telah ditentukan terlebih dahulu sebanyak 8 bilangan. Pertama, data dimunculkan terlebih dahulu dengan urutan yang acak, yaitu sesuai dengan urutan bilangan yang sudah ditentukan sebelum di sorting. Untuk menampilkan urutan bilangan tersebut dilakukan dengan sebuah perulangan yaitu  :

for (int a=0; a<8;a++)     {         cout<<setw(4)<<S[a];     }

Pada perulangan diatas dilakukan jika a=0, lalu a kurang dari 8, kemudian a increment. Baru kemudian data ditampilkan satu  persatu dengan lebar field yang sudah diatur yaitu 4.

Kemudian, bilangan yang sudah diurutkan akan ditampilkan. Sebelumnya terjadi proses untuk mengurutkan bilangan tersebut, yaitu :

for (int b=0;b<7;b++)         for (int c=0;c<7;c++)         if (S[c]>=S[c+1])     {         temp=S[c];        S[c]=S[c+1];        S[c+1]=temp;     }

Pada proses diatas terdapat dua buah perulangan pada perulangan pertama dimana b=0, b kurang dari 7 dan b increment. Kemudian pada perulangan kedua dimana c=0, c kurang dari 7 dan c increment. Kemudian terdapat sebuah pemilihan kondisi, jika S[c] lebih dari samadengan S[c+1], maka  nilai temp samadengan S[c], S[c] samadengan S[c+1] dan S[c+1] samadengan temp;

Setelah proses diatas barulah data ditampilkan dengan urutan yang sudah terurut.

Output :

Data yang sebelumnya acak, diurutkan dengan menggunakan metode bubble sort.

b). Metode Insert Sort

Cara kerja insertion sort sebagaimana namanya.Pertama-tama, dilakukan proses iterasi, dimana di setiap iterasi insertion sort memindahkan nilai elemen,kemudian menyisipkannya berulang-ulang sampai ketempat yang tepat. Begitu seterusnya dilakukan. Dari proses iterasi, seperti biasa, terbentuklah bagian yang telah di-sorting dan bagian yang belum.

Algoritma Insertion Sort. Algoritma Insertion Sort dapat dirangkum sebagai berikut:

ü  Simpan nilai Ti kedalam variabel sementara, dengan i = 1.

ü  Bandingkan nilainya dengan elemen sebelumnya.

ü  Jika elemen sebelumnya (Ti-1) lebih besar nilainya daripada Ti, maka tindih nilai Ti dengan nilai Ti-1 tersebut. Decrement i (kurangi nilainya dengan 1).

ü  Lakukan terus poin ke-tiga, sampai Ti-1 ≤ Ti.

ü  Jika Ti-1 ≤ Ti terpenuhi, tindih nilai di Ti dengan variabel sementara yang disimpan sebelumnya.

ü  Ulangi langkah dari poin 1 di atas dengan i di-increment (ditambah satu).

Contoh program Insert sort :

#include <conio.h> #include <iomanip> #include <iostream> using namespace std; int n,i,j,data[20],simpan; main() { cout<<"Masukkan banyak data = ";cin>>n; for(i=1;i<=n;i++) {  cout<<"Data ke-"<<i<<" = ";cin>>data[i]; } cout<<"Data Sebelum Diurutkan : "<<endl; for(i=1;i<=n;i++)  cout<<data[i]<<"  "; cout<<endl<<endl; for(i=2;i<=n;i++) {  j=i;  while (j>0&&data[j]<data[j-1])    {   simpan=data[j];   data[j]=data[j-1];   data[j-1]=simpan;   j--;    } } cout<<endl<<"Data Setelah Diurutkan :"<<endl; for(i=1;i<=n;i++)  cout<<setw(3)<<data[i]<<endl<<endl; getch(); }

Penjelasan :

Program diatas merupakan program untuk mengurutkan data dengan metode insert sort, yaitu mengurutkan data dengan menginputkan data yang kita inginkan.

Awalnya kita mengiputkan terlebih dahulu jumlah data atau bilangan yang akan dimasukkan, jumlah data yang ingin diinputkan disimpan pada variabel n, yang kemudian digunakan sebagai jumlah perulangan penginputan data.  Data atau bilangan yang kita inputkan akan disimpan di variabel data[i]. Terlihat pada:

cout<<"Masukkan banyak data = ";cin>>n; for(i=1;i<=n;i++) {  cout<<"Data ke-"<<i<<" = ";cin>>data[i]; }

Setelah menginputkan data, data yang belum diurutkan akan ditampilkan. Data ditampilkan sesuai dengan urutan diinputkannya. Terlihat pada :

cout<<"Data Sebelum Diurutkan : "<<endl; for(i=1;i<=n;i++)  cout<<data[i]<<"  "; cout<<endl<<endl;

Kemudian terdapaat proses mengurutkan data. Terdapat perulangan dimana i samadengan 2, i kurang dari samadengan n kemudian i increment. Nilai j sama dengan i, terdapat fungsi while untuk mengecek apakah j lebih besar daripada 0, dan data[j] lebih besar dari data[j-1]. Lalu terjadi proses swap dimana simpan sama dengan data[j], data[j]=data[j-1], dan data[j-1] sama dengan simpan. Kemudian j decrement.

Terlihat pada :

for(i=2;i<=n;i++) {  j=i;  while (j>0&&data[j]<data[j-1])    {   simpan=data[j];   data[j]=data[j-1];   data[j-1]=simpan;   j--;    } }

Setelah data diurutkan maka data ditampilkan dengan urutan yang sudah benar. Terlihat pada :

cout<<endl<<"Data Setelah Diurutkan :"<<endl; for(i=1;i<=n;i++)  cout<<setw(3)<<data[i]<<endl<<endl;

Data ditampilkan dengan menggunakan perulangan dimana i sama dengan 1, i kurang dari sama dengan n, dan i increment. Lalu ditampilkan satu persatu dengan lebar field 3.

Output :

Pertama memasukkan banyak data yang ingin dimasukkan, kemudian memasukkan datanya secara acak. Kemudian program mengurutkan data yang sudah dimasukkan tadi dengan menggunakan metode insert sort.

c). Metode Quick Sort

Dalam algoritma Quick Sort dikenal apa yag disebut dengan pivot, pivot merupakan suatu elemen yang dipilh dari elemen array yang akan di urutkan, pivot dapat diambil dari elemen paling pinggir dari Array ataupun dari elemen yang tengah.

Dalam pengoperasiannya elemen yang lebih besar dari elemen pivot akan dipindah ke sebelah kanan pivot dann yang lebih kecil akan dipindah kesebelah kiri pivot, proses ini disebut dengan proses partitioning dan akan mengasilkan dua partisi array, yaitu partisi yang lebih besar dari pivot dan partisi yang lebih kecil dari pivot. Proses diatas kemudian dilakukan lagi pada masing-masing paritisi,

Secara ringkas, algoritma Quick Sort adalah sebagai berikut:

ü  Pilih elemen pivot.

ü  Pindahkan elemen array yang lebih kecil dari elemen pivot ke sebelah kiri pivot, dan elemen yang lebih besar dari lemen pivot ke sebelah kanan pivot.

ü  Ulangi langkah 1 dan 2 untuk masing masing partisi yang terbentuk dari langkah.

Contoh program :

#include <iostream> #define n 20 using namespace std; int Ar[n]; void quickSort(int arr[], int left, int right); int main() {   int jumlahBil=5; cout<<"Masukkan jumlah bilangan dalam : "; cin>>jumlahBil; int Ar[jumlahBil]; for(int i=0; i<jumlahBil;i++) { cout<<"Bilangan ke-"<< i+1 << " : "; cin>>Ar[i]; } quickSort(Ar,0,jumlahBil-1 ); cout<<"Data yang telah diurutkan"<<endl; for(int i=0; i<jumlahBil;i++) { cout<<Ar[i]<<"\n"; } } void quickSort(int arr[], int left, int right) { int i = left, j = right; int tmp; int pivot = arr[(left + right) / 2]; while (i <= j) { while (arr[i] < pivot) i++; while (arr[j] > pivot) j--; if (i <= j) { tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; i++; j--; } }; if (left < j) quickSort(arr, left, j); if (i < right) quickSort(arr, i, right); }

Penjelasan :

Program diatas merupakan program pengurutan data dengan metode quick sort. Terdapat pendefinisian jumlah n maksimal adalah 20. Kemudian kita memasukkan jumlah data atau bilangan, kemudian jumlah data yang diinputkan akan dijadikan sebagai jumlah perulangan untuk input data atau bilangannya. Bilangan yang diinput akan disimpan pada variabel Ar[i]. Terlihat pada :

cout<<"Masukkan jumlah bilangan dalam : "; cin>>jumlahBil; int Ar[jumlahBil]; for(int i=0; i<jumlahBil;i++) { cout<<"Bilangan ke-"<< i+1 << " : "; cin>>Ar[i]; }

Kemudian data tersebut diurutkan dengan algoritma quick sort, yaitu dengan pemilihan pivot dan memisahkan data yang lebih kecil dari pivot dan yang lebih besar. Setelah diurutkan, maka data yang sudah diurutkan akan ditampilkan sesuai jumlah data yang diinputkan namun dengan susunan yang sudah terurut. Data ditampilkan satu persatu dengan perulangan. Dimana i sama dengan 0, i kurang dari jumlahBil maka i increment. Terlihat pada :

cout<<"Data yang telah diurutkan"<<endl; for(int i=0; i<jumlahBil;i++) { cout<<Ar[i]<<"\n"; }

Output :

Pertama menentukan jumlah data yang ingin dimasukkan. Kemudian memasukkan data secara acak. Program akan melakukan pengurutan terhadap data yang dimasukkan tadi dengan metode quick sort.

Sumber :
Saputri, S. (2016). Pengurutan. Modul Alpro 2-1, 118-128.