Teknik Sorting dan Searching

Teknik Sorting dan Teknik Searching

Sorting memiliki kepentingan tambahan bagi perancang algoritma paralel; ia sering
digunakan untuk melakukan permutasi data umum pada komputer dengan memori
terdistribusi. Operasi pemidahan data ini dpt digunakan untuk menyelesaikan masalah pada:
• teori graf
• geometri komputasional
• image processing
dalam waktu optimal atau hampir optimal.
Algoritma yang akan dipelajari berikut merupakan internal sort – yaitu, tabel yang di-sort
cukup kecil untuk masuk seluruhnya di memori primer. Semua algoritma berikut ini juga
men-sort dengan membandingkan sepasang elemen.
ENUMERATION SORT
Asumsi:
• Tabel dengan n elemen: a0, a1, …, an-1
• Untuk 2 elemen ai dan aj, salah satu kondisi ini pasti benar: ai aj.
• Tujuan sorting: menemukan permutasi (p0, p1, …, pn-1) sedemikian sehingga ap0 = ap1 = …
= apn-1.
Enumeration sort:
• menghitung posisi akhir setiap elemen pada list yang di-sort dan membandingkannya
dengan elemen lain dan menghitung jumlah elemen yang memiliki nilai lebih kecil.
• Jika j elemen memiliki nilai lebih kecil dari ai, maka pj=i; yaitu, elemen ai adalah (j + 1)
elemen pada list yang di-sort setelah ap0, …, apj-1.
• Jika diberikan n2 prosesor, model CRCW PRAM dapat menghitung setiap pasang elemen
dan menghitung posisi list setiap elemen dalam waktu konstan. Begitu mesin telah
menghitung posisi setiap elemen, diperlukan satu langkah lagi untuk memindahkan
elemen ybs ke lokasi yang telah urut.
ENUMERATION SORT (SPECIAL CRCW PRAM):
Parameter n {number of elements}
Global a[0...(n-1)] {elements to be sorted}
position[0...(n-1)] {sorted positions}
sorted[0...(n-1)] {Contains sorted elements}
begin
spawn(Pi,j, for all 0 = i, j < n)
for a ll Pi,j, where 0 = i, j < n do
position[i] 0
if a[i] < a[j] or (a[i] = a[j] and i < j) then
position[i] 1
endif
endfor
for a ll Pi,0, where 0 = i < n do
sorted[position[i]] a[i]
endfor
end
Satu set n elemen dapat di-sort dalam waktu T(log n) dengan n2 prosesor, jika dipakai model
PRAM CRCW dengan write simultan ke lokasi memori yang sama menyebabkan jumlah
nilai di-assign. Jika waktu yang diperlukan untuk spawn prosesor tidak dihitung, algoritma
berjalan dengan waktu konstan.
BATAS BAWAH UNTUK PARALLEL SORTING
Teorema 1:
Anggap ada n elemen yang akan di-sort pada array prosesor yang disusun menjadi mesh satu
dimensi. Juga asumsikan bahwa sebelum dan sesudah sort, elemen akan didistribusikan
merata, satu elemen per prosesor. Dengan demikian, batas bawah kompleksitas waktu pada
algoritma sorting yang mana pun adalah T(n).
Bukti:
Lebar biseksi dari jaringan mesh satu dimensi adalah 1. Misalkan posisi yang ter-sort dari
semua elemen yang pada awalnya ada pada satu sisi biseksi adalah pada sisi biseksi yang
lain, dan sebaliknya. Maka seluruh n elemen harus melewati satu link untuk mencapai sisi
yang lain. Karena link hanya dapat membawa satu elemen sekali, jumlah langkah yang
diperlukan untuk menukar elemen melalui biseksi paling tidak adalah sebesar n. Dengan
demikian, batas bawah kompleksitas jaringan mesh satu dimensi dengan syarat-syarat
tersebut adalah T(n).
Teorema 2:
Anggap ada n elemen yang akan di-sort pada array prosesor yang tersusun sebagai mesh dua
dimensi. Juga anggap bahwa sebelum dan sesudah sort, elemen-elemen tsb terdistribusi
merata, satu elemen per prosesor. Maka, batas bawah kompleksitas waktu untuk algoritma
sorting yang mana pun adalah T(vn).
Bukti:
Lebar biseksi jaringan mesh dua dimensi dengan n node adalah lebih kecil atau sama dengan
vn . Misalkan posisi ter-sort dari semua elemen yang pada awalnya ada pada satu sisi
biseksi adalah di sisi lain biseksi tsb, dan sebaliknya. Maka seluruh n elemen harus melalui
salah satu dari tidak lebih vn link untuk mencapai sisi lainnya. Karena satu link hanya
dapat membawa satu elemen sekali, jumlah langkah yang diperlukan untuk menukar elemen
melintasi biseksi paling tidak adalah n/ vn . Dengan demikian, batas bawah kompleksitas
array prosesor bagaimanapun yang disusun sebagai mesh dua dimensi dan berjalan dengan
ketentuan yang telah diberikan di atas adalah T(n/ vn ) = T(vn)
Teorema 3:
Anggap ada n = 2k elemen yang akan di-sort pada array prosesor yang tersusun sebagai
jaringan shuffle-exchange. Juga anggap bahwa sebelum dan sesudah sort, elemen
terdistribusi merata, satu elemen per prosesor. Batas bawah untuk algoritma sort mana pun
adalah T(log n).
Bukti:
Misalkan posisi ter-sort elemen yang pada awalnya berada pada node 0 adalah node n-1.
Pemindahan elemen tsb dari node 0 ke node n-1 menuntut paling tidak log n operasi
pertukaran dan paling tidak log n-1 operasi shuffle. Dengan alasan ini, batas bawah pada
algoritma sorting berbassis shuffle-exchange dengan batas-batas di atas adalah T(log n).
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
secara ascending demi kenyamanan dalam penelusuran data.
Beberapa macam algoritma sorting telah dibuat karena proses tersebut sangat
mendasar dan sering digunakan. Oleh karena itu, pemahaman atas algoritma –
algoritma yang ada sangatlah berguna.
Setelah menyelesaikan pembahasan pada bagian ini, anda diharapkan mampu :
1. Memahami dan menjelaskan algoritma dari insertion sort, selection sort,
merge sort dan quick sort.
2. Membuat implementasi pribadi menggunakan algoritma yang ada
6.2 Insertion Sort
Salah satu algoritma sorting yang paling sederhana adalah insertion sort. Ide dari
algoritma ini dapat dianalogikan seperti mengurutkan kartu. Penjelasan berikut ini
menerangkan bagaimana algoritma insertion sort bekerja dalam pengurutan kartu.
Anggaplah anda ingin mengurutkan satu set kartu dari kartu yang bernilai paling
kecil hingga yang paling besar. Seluruh kartu diletakkan pada meja, sebutlah meja
ini sebagai meja pertama, disusun dari kiri ke kanan dan atas ke bawah. Kemudian
kita mempunyai meja yang lain, meja kedua, dimana kartu yang diurutkan akan
diletakkan. Ambil kartu pertama yang terletak pada pojok kiri atas meja pertama
dan letakkan pada meja kedua. Ambil kartu kedua dari meja pertama, bandingkan
dengan kartu yang berada pada meja kedua, kemudian letakkan pada urutan yang
sesuai setelah perbandingan. Proses tersebut akan berlangsung hingga seluruh kartu
pada meja pertama telah diletakkan berurutan pada meja kedua.
Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi
dua bagian, yang belum diurutkan (meja pertama) dan yang sudah diurutkan (meja
kedua). 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.
Selection Sort
Jika anda diminta untuk membuat algoritma sorting tersendiri, anda mungkin akan
menemukan sebuah algoritma yang mirip dengan selection sort. Layaknya insertion
sort, algoritma ini sangat rapat dan mudah untuk diimplementasikan.
Mari kita kembali menelusuri bagaimana algoritma ini berfungsi terhadap satu paket
kartu. Asumsikan bahwa kartu tersebut akan diurutkan secara ascending. Pada
awalnya, kartu tersebut akan disusun secara linier pada sebuah meja dari kiri ke
kanan, dan dari atas ke bawah. Pilih nilai kartu yang paling rendah, kemudian
tukarkan posisi kartu ini dengan kartu yang terletak pada pojok kiri atas meja. Lalu
cari kartu dengan nilai paling rendah diantara sisa kartu yang tersedia. Tukarkan
kartu yang baru saja terpilih dengan kartu pada posisi kedua. Ulangi langkah –
langkah tersebut hingga posisi kedua sebelum posisi terakhir dibandingkan dan
dapat digeser dengan kartu yang bernilai lebih rendah
Ide utama dari algoritma selection sort adalah memilih elemen dengan nilai paling
rendah dan menukar elemen yang terpilih dengan elemen ke-i. Nilai dari i dimulai
dari 1 ke n, dimana n adalah jumlah total elemen dikurangi 1.
Algoritma
void selectionSort(Object array[], int startIdx, int endIdx) {
int min;
for (int i = startIdx; i < endIdx; i++) {
min = i;
for (int j = i + 1; j 0) {
min = j;
}
}
swap(array[min], array[i]);

sumber :
www.wikipedia.com

By: Bartolomeus Rynaldo A.H, NPM: 10408997