Sorting
Sort adalah suatu proses
pengurutan data yang sebelumnya disusun secara acak atau tidak teratur menjadi
urut atau teratur menurut suatu aturan tertentu. Biasanya pengurutan dibagi
menjadi 2 yaitu :
·
Ascending : Pengurutan dari kecil ke besar.
·
Descending : Pengurutan dati besar ke kecil.
Ada banyak cara atau metode untuk melakukan pengurutan ascending
maupun descending :
·
Dalam proses pengurutan kita akan
memerlukan proses penukaran data.
·
Proses penukaran data tidak bisa
kita lakukan secara langsung dengan menukar isi variabel.
·
Penukaran data dilakukan dengan
metode swap.
Swap
Misalkan
terdapa dua data yang akan ditukar yaitu :
Data [1] = 5;
Data [2] = 10;
Cara yang salah :
Data [1] = data
[2];
Data [2] = data
[1];
Cara yang benar :
Swap = data [1];
Data [1] = data [2];
Data [2] = swap;
Untuk melakukan pengurutan terdapat beberapa cara atau metode
diantaranya :
·
Selection Sort
·
Insertion Sort
1.
Selection Sort
Selection Sort merupakan salah satu algoritma pengurutan yang
sederhana. Ide dasarnya adalah melakukan beberapa kali pass untuk melakukan
penyeleksian elemen struktur data. Untuk sorting ascending (menaik), elemen
yang paling kecil di antara elemen-elemen yang belum urut, disimpan indeksnya,
kemudian dilakukan pertukaran nilai elemen dengan indeks yang disimpan tersebut
dengan elemen yang paling depan yang belum urut. Sebaliknya, untuk sorting
descending (menurun), elemen yang paling besar yang disimpan indeksnya kemudian
ditukar.
Selection Sort diakui karena kesederhanaan algoritmanya dan
performanya lebih bagus daripada algoritma lain yang lebih rumit dalam situasi
tertentu. Algoritma ini bekerja sebagai berikut:
- Mencari nilai minimum (jika ascending) atau maksimum (jika descending) dalam sebuah list
- Menukarkan nilai ini dengan elemen pertama list
- Mengulangi langkah di atas untuk sisa list dengan dimulai pada posisi kedua
- Secara efisien kita membagi list menjadi dua bagian yaitu bagian yang sudah diurutkan, yang didapat dengan membangun dari kiri ke kanan dan dilakukan pada saat awal, dan bagian list yang elemennya akan diurutkan.
Secara efisien kita membagi list menjadi dua bagian yaitu bagian yang sudah
diurutkan, yang didapat dengan membangun dari kiri ke kanan dan dilakukan pada
saat awal, dan bagian list yang elemennya
akan diurutkan.
Simulasi
Algoritma Selection Sort
Jika digambarkan secara singkat, maka algoritma Insertion sort ini
dapat digambar sebagai berikut
Algoritma
pengurutan selection sort ini termasuk algoritma sulit dibagi/ mudah digabung
(hard split/easy join). Dari proses pengurutannya, Selection sort ini
memiliki dua buah varian yaitu :
o
Maximum Sort
Memilih data
yang maksimum dari suatu kumpulan data larik, lalu menempatkan data tersebut ke
elemen paling akhir atau paling awal sesuai pengurutan yang diinginkan. Data
maksimum/minimum yang diperoleh, “diisolasi” dan tidak diikutsertakan pada
proses pencarian data maksimum berikutnya.
o
Minimum Sort
Memilih data
yang minimum dari suatu kumpulan data larik , lalu menempatkan data tersebut ke
elemen paling akhir atau paling awal sesuai pengurutan yang diinginkan. Data
minimum yang diperoleh, “diisolasi” dan tidak diikutsertakan pada proses
pencarian data minimum berikutnya. Dalam pemecahan masalah algoritma selection
sort , kita dapat memilih dua metode alternatif algoritma antara lain pemecahan
dengan metode Brute Force dan pemecahan dengan metode devide and conquer.
Metode Pemecahan Brute Force
Kekuatan algoritma
brute force terletak pada kemampuannya untuk menemukan semua pemecahan masalah
yang mungkin, akan tetapi langkah yang dibutuhkan sangat banyak sehingga tidak
baik jika digunakan untuk memecahkan masalah yang memiliki masukan yang cukup
besar.
Contoh Program
Selection Sort
#include <iostream>
#include <conio.h>
#include <stdio.h>
#include <iomanip>
#ifdef __cplusplus__
#include <cstdlib>
#else
#include <stdlib.h>
#endif
int main()
{
int
x[5];
int i;
int
temp;
int
minindex;
int j;
if
(system("CLS")) system("clear");
cout
<< " >> Program Selection Sort << \n" << endl;
cout
<< "masukkan nilai x :\n";
for (i =
0; i<5; i++)
{
cout << "x[" << i << "] =
"; cin >> x[i];
}
cout
<< "\n Data sebelum di sort :";
for (i =
0; i<5; i++)
{
cout << setw(4) << x[i];
}
for (i =
0; i<5 - 1; i++) //perulangan iterasi
{
minindex = i;
for (j = i + 1; j<5; j++) //perulangan membandingkan
data
{
if (x[minindex]>x[j])
{
minindex = j;
}
}
temp = x[i];
x[i] = x[minindex];
x[minindex] = temp;
}
cout
<< "\n Data setelah di sort :";
for (i =
0; i<5; i++)
{
cout << setw(4) << x[i];
}
getchar();
cout
<< endl;
system("pause");
}
2. Insertion
Sort
Insertion sort adalah sebuah metode pengurutan
data dengan menempatkan setiap elemen data pada pisisinya dengan cara melakukan
perbandingan dengan data – data yang ada. Inde algoritma dari metode insertion
sort ini dapat dianalogikan sama seperti mengurutkan kartu, dimana jika suatu
kartu dipindah tempatkan menurut posisinya, maka kartu yang lain akan bergeser
mundur atau maju sesuai kondisi pemindahanan kartu tersebut. Dalam pengurutan
data, metode ini dipakai bertujuan untuk menjadikan bagian sisi kiri array
terurutkan sampai dengan seluruh array diurutkan.
Penganalogian Insertion Sort dengan pengurutan kartu
Berikut menjelaskan bagaimana algoritma Insertion Sort bekerja dalam pengurutan kartu, Anggaplah kita ingi mengurutkan satu set kartu dari kartu yang bernilai paling kecil hingga yang paling besar.
- Dimulai dengan posisi tangan kosong, dan semua kartu berada diatas meja. dan anggaplah kita akan menyusun kartu ke tangan kiri kita.
- Mengamil kartu pertama dari meja dan meletakannya ke tangan kiri.
- Mengambil kartu kedua dan membandingkannya dengan kartu yang sudah ada di tangan kiri.
- Jika kartu yang diambil dari meja memenuhi syarat perbandingan, maka kartu tersebut akan diletakan didepan kartu yang dibandingkan, serta kartu yang lain yang telah dibandingkan akan bergeser mundur (ke belakang).
Proses ini akan berlangsung sampai semua kartu akan terurutkan dengan benar sesuai criteria pengurutannya, demikian juga halnya dalam pengurutan data. Jika data sudah ada, maka pengurutan dimulai dengan mengambil satu data dan membandingkannya dengan data-data yang ada didepannya. Jika data yang diambil memenuhi syarat perbandingan, maka data yang diambil tersebut akan diletakan di depan data yang dibandingkan, kemudian data-data yang dibandingkan akan bergeser mundur.
Catatan : Dalam hal pengurutan data dengan metode insertion sort ini, data yang diambil pertama adalah data kedua, kemudian data yang diambil akan dibandingkan dengan data – data yang ada disebelah kiri / data sebelumnya (data-data sebelum data yang diambil). Jika proses tersebut selesai, maka akan dilanjutkan dengan data-data selanjutnya (data ke-3, data ke-4… dan seterusnya). Proses akan berlangsung sampai data – data terurutkan dengan benar.
Simulasi Algoritma
Insertion Sort.
Dari gambaran
proses pengurutan/sorting data di atas dapat diketahui bagaimana data-data
tersebut berpindah posisi dari satu index ke index lain dalam satu array.
Contoh
Program Insertion Sort
#include <iostream>
#include
<conio.h>
int main()
{
int i, j, n, data[10], simpan;
cout << "Masukkan banyak
data = "; cin >> n;
for (i = 1; i <= n; i++)
{
cout << "Data ke -
" << i << " = "; cin >> data[i];
}
for (i = 1; i<n; i++)
{
for (j = i + 1; j <= n; j++)
{
if (data[i]>data[j])
{
simpan =
data[i];
data[i] =
data[j];
data[j] =
simpan;
}
}
}
cout << "Hasil sorting
adalah = ";
for (i = 1; i <= n; i++)
cout << data[i] <<
" ";
getch();
}
Tidak ada komentar:
Posting Komentar