Macam-macam
sorting
Sorting adalah proses menyusun elemen – elemen dengan
tata urut tertentu dan proses tersebut terimplementasi dalam bermacam aplikasi.
Kita ambil contoh pada aplikasi perbankan. Aplikasi tersebut mampu menampilkan
daftar account yang aktif.Hampir seluruh pengguna pada sistem
akan memilih tampilan daftar berurutan secaraascending demi
kenyamanan dalam penelusuran data. Beberapa macam algoritmasorting telah
dibuat karena proses tersebut sangat mendasar dan sering digunakan. Oleh karena
itu, pemahaman atas algoritma – algoritma yang ada sangatlah berguna.
1. Selection Sort (Ascending):
Ide utama
dari algoritma selection sort adalah memilih elemen dengan
nilai paling rendah dan menukar elemen yang terpilih dengan elemen ke-i.
Nilai dari idimulai dari 1 ke n, dimana n adalah
jumlah total elemen dikurangi 1.
Proses
pengurutan dengan menggunakan metode selection sort secara terurut naik adalah:
·
Mencari data
terkecil dari data pertama sampai data terakhir, kemunian di tukar posisinya
dengan data pertama
·
Mencari data
terkecil dari data kedua sampai data terakhir, kemudian di tukar dengan
posisinya dengan data kedua.
·
Mencari data
terkecil dari data ketiga sampai data terakhir, kemudian di tukar posisinya
dengan data ketiga
·
Dan
seterusnya sampai semua data turut naik. apabila terdapat n buah data yang akan
di urutkan, maka membutukan (n - 1) langkah pengurutan, dimana data terakhir
yaitu data ke-n tidak perlu di urutkan karena hanya tinggal satu satunya.
Contoh
2. Bubble Sort
Konsep Buble
Sort
Merupakan
algoritma pengurutan paling tua dengan metode pengurutan paling sederhana.
Metode pengurutan gelembung (Bubble Sort) diinspirasikan oleh gelembung sabun
yang berada dipermukaan air. Karena berat jenis gelembung sabun lebih ringan
daripada berat jenis air, maka gelembung sabun selalu terapung ke atas
permukaan. Prinsip di atas dipakai pada pengurutan gelembung.
Bubble sort
(metode gelembung) adalah metode/algoritma pengurutan dengan dengan cara
melakukan penukaran data dengan tepat disebelahnya secara terus menerus sampai
bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan. Jika
tidak ada perubahan berarti data sudah terurut. Disebut pengurutan gelembung
karena masing-masing kunci akan dengan lambat menggelembung ke posisinya yang tepat
contoh kasus bubble sort.
3. Insertion sort
Algoritma insertion sort pada
dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum
diurutkan dan yang sudah diurutkan. Elemen pertama diambil dari bagian array
yang belum diurutkan dan kemudian diletakkan sesuai posisinya pada bagian lain
dari array yang telah diurutkan. Langkah ini dilakukan secara berulang hingga
tidak ada lagi elemen yang tersisa pada bagian array yang belum diurutkan.
Ilustrasi: :
Data dicek satu per satu mulai dari yang kedua sampai
dengan yang terakhir. Apabila ditemukan data yang lebih kecil daripada data
sebelumnya, maka data tersebut disisipkan pada posisi yang sesuai. Akan lebih
mudah apabila membayangkan pengurutan kartu. Pertama-tama anda meletakkan
kartu-kartu tersebut di atas meja, kemudian melihatnya dari kiri ke kanan.
Apabila kartu di sebelah kanan lebih kecil daripada kartu di sebelahkiri, maka
ambil kartu tersebut dan sisipkan di tempat yang sesuai.
Contoh:
4. Metode Penggabungan (Merge Sort)
Metode penggabungan biasanya digunakan pada pengurutan
berkas. Prinsip dari metode penggabungan sebagai berikut : mula-mula diberikan
dua kumpulan data yang sudah dalam keadaan urut. Kedua kumpulan data tersebut
harus dijadikan satu table sehingga dalam keadaan urut.
5. Quick Sort
Algoritma sortir yang efisien yang ditulis oleh C.A.R.
Hoare pada 1962. Dasar strateginya adalah “memecah dan menguasai”. Quicksort
dimulai dengan menscan daftar yang disortir untuk nilai median. Nilai ini, yang
disebut tumpuan (pivot), kemudian dipindahkan ke satu sisi pada daftar dan
butir-butir yang nilainya lebih besar dari tumpuan di pindahkan ke sisi lain.
Contoh:
6. Metode Shell (Shell Sort)
Metode ini disebut juga dengan metode pertambahan
menurun (diminishing increment). Metode ini dikembangkan oleh Donald L. Shell
pada tahun 1959, sehingga sering disebut dengan Metode Shell Sort. Metode ini
mengurutkan data dengan cara membandingkan suatu data dengan data lain yang
memiliki jarak tertentu, kemudian dilakukan penukaran bila diperlukan
Contoh:
7. Radix sort
Ide dasar dari metode Radix sort ini
adalah mengkategorikan data-data menjadi sub kumpulan subkumpulan data sesuai
dengan nilai radix-nya, mengkonkatenasinya, kemudian
mengkategorikannya kembali berdasar nilai radix
contoh:
8.
Bucket Sort
Bucket sort adalah algoritma sorting yang bekerja
dengan partisi array ke dalam jumlah terbatas sort. Setiap kotak ini kemudian
diurutkan secara individual, baik menggunakan algoritma sorting yang berbeda,
atau dengan rekursif menerapkan algoritma bucket sort. Sebuah variasi dari
metode ini disebut semacam hitungan tunggal buffered lebih cepat dari jenis
cepat dan membutuhkan waktu sekitar waktu yang sama untuk berjalan pada set
data.
Algoritma:
·
Cari nilai
maksimum dan minimum di array
·
Inisialisasi
array bucket Daftar <> unsur (ukuran maxValue – minValue + 1)
·
Pindahkan elemen dalam array untuk
bucket
·
Write bucket
keluar (dalam rangka) ke array yang asli
9. Heap Sort
Merupakan satu bentuk dari selection sort yang
memiliki kompleksitas algoritma O (n log(n) ) yang menggunakan struktur data
heap. Heap sort bekerja dengan menentukan elemen terbesar (atau terkecil) dari
sebuah susunan elemen, dan diletakkan pada akhir (atau awal) dari daftar
tersebut. Algoritma:
1. Buat suatu heap.
2. Ambil isi dari root masukkan kedalam
sebuah array.
3. Hapus element root dengan
mempertahankan properti heap.
4. Ulangi sampai tree menjadi kosong
10. ExchangeSort
Pembahasan yang kedua mengenai
Metode Exchange Sort. Metode ini merupakan metode pengurutan data yang hampir
mirip dengan Bubble Sort ( Mirorr-Nya buble sort), bahkan mungkin juga metode
Bubble Sort sama dengan Exchange Sort. Namun setiap metode pasti memiliki
perbedaan, perbedaan antara Exchange Sort dan Bubble Sort terletak dalam hal
bagaimana membandingkan antar elemen-elemennya.
Exchange sort membandingkan suatu
elemen dengan elemen-elemen lainnya dalam array tersebut, dan melakukan
pertukaran elemen jika perlu. Jadi ada elemen yang selalu menjadi elemen pusat
(pivot). Sedangkan Bubble sort akan membandingkan elemen pertama/terakhir
dengan elemen sebelumnya/sesudahnya, kemudian elemen tersebut itu Untuk
setiap proses, akan dilakukan dengan mencari elemen dari posisi yang belum
diurutkan dan kemudian memilih elemen yang memiliki nilai terkecil atau terbesar
yang akan ditukarkan ke posisi yang tepat di dalam array.
Misalnya untuk putaran pertama,
akan dicari data dengan nilai terkecil dan data ini akan ditempatkan pada
indeks terkecil, pada putaran kedua akan dicari data kedua terkecil, dan akan
ditempatkan di indeks kedua, negitu seterusnya hingga tidak ada data yang
dicari lagi.
Selama proses, pembandingan dan
pengubahan hanya dilakukan pada indeks pembanding saja, pertukaran data secara
fisik terjadi pada akhir proses.
Perbedaannya: dalam exchange sort
ada elemen yang berfungsi sebagai pusat (pivot), pertukaran hanya akan
dilakukan jika diperlukan saja dari pivot tersebut. Sedangkan bubble sort
akan membandingkan elemen pertama/terakhir dengan elemen sebelumnya/sesudahnya,
kemudian elemen sebelum/sesudahnya itu akan menjadi pusat (pivot) untuk
dibandingkan dengan elemen sebelumnya/sesudahnya lagi, begitu seterusnya.
void exchange (int a[], int n) {
int i,j;
for (i=0;i<=n-1;i++) {
for (j=(i+1);j<n;j++)
if(a[i]>a[j])
tukar (a,i,j);
}
}
|
11. Tree Sort
Tree sort adalah metode sorting dengan cara membangun
pohon biner dengan menampilkan 3 hasik output: PreOrder,InOrder,PostOrder.
Konsep dan
Algoritma:
Konsep dasar
dari tree sort adalah sebagaimana sebuah pohon, ada akar, batang, ranting,
daun, dsb. Dalam tree sort ada istilah akar atau root dan daun atau leaf.
Perhatikan gambar di bawah ini.
Ketentuan
dari gambar diatas adalah :
1. menjadi akar ,
2. menjadi subtree kiri,
3. menjadi subtree kanan,
4 & 5. menjadi daun dari subtree kiri ,
6. menjadi daun dari subtree kanan.
2. menjadi subtree kiri,
3. menjadi subtree kanan,
4 & 5. menjadi daun dari subtree kiri ,
6. menjadi daun dari subtree kanan.
Setiap objek dalam pohon biner berisi dua pointer,
biasanya disebut kiri dan kanan. Selain pointer ini tentu saja node dapat
berisi tipe data lainnya. Misalnya, pohon biner integer bisa terdiri dari objek
dari jenis berikut:
struct
Node {
int item; / / Data dalam node ini.
Node *kiri; / / Pointer ke subtree kiri.
Node * kanan; / / Pointer ke subtree kanan.
}
Sign up here with your email
EmoticonEmoticon