Algoritma Sorting

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, ai = aj, atau ai > aj.
• Tujuan sorting: menemukan permutasi ( π
0, π
1, ..., π
n-1) sedemikian sehingga aπ0 ≤ aπ1 ≤ ...
≤ aπn-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 π
j=i; yaitu, elemen ai adalah (j + 1)
elemen pada list yang di-sort setelah aπ0, ..., aπj-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 all 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
APP - Algoritma Sorting 2/4
for all Pi,0, where 0 ≤ i < n do
sorted[position[i]] ← a[i]
endfor
end
Satu set n elemen dapat di-sort dalam waktu Θ(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 Θ(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 Θ(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 Θ(√n).
Bukti:
Lebar biseksi jaringan mesh dua dimensi dengan n node adalah lebih kecil atau sama dengan
⎡√n⎤. 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 ⎡√n⎤ 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/⎡√n⎤. Dengan demikian, batas bawah kompleksitas
array prosesor bagaimanapun yang disusun sebagai mesh dua dimensi dan berjalan dengan
ketentuan yang telah diberikan di atas adalah Θ(n/⎡√n⎤) = Θ(√n)
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 Θ(log n).
APP - Algoritma Sorting 3/4
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 Θ(log n).
ODD-EVEN TRANSPOSITION SORT
Odd-even transposition sort dirancang untuk model array prosesor dengan elemen-elemen
processing yang disusun menjadi mesh satu dimensi.
Anggap A = (a0, a1, ..., an-1) adalah himpunan n elemen yang akan di-sort. Setiap n elemen
processing berisi dua variabel lokal: a, elemen unik dari array A, dan t, variabel yang berisi
nilai yang diambil dari elemen processing tetangganya.
Algoritma melakukan n/2 iterasi, dan setiap iterasi memiliki dua fase:
1. odd-even exchange: nilai a pada setiap prosesor bernomer ganjil (kecuali prosesor n-1)
dibandingkan dengan nilai a yang tersimpan di prosesor berikutnya. Nlai-nilai ditukar,
jika perlu, sehingga prosesor dengan nomer lebih kecil berisi nilai yang lebih kecil.
2. even-odd exchange: nilai a pada setiap prosesor bernomer genap dibandingkan dengan
nilai a yang tersimpan di prosesor berikutnya. Nlai-nilai ditukar, jika perlu, sehingga
prosesor dengan nomer lebih kecil berisi nilai yang lebih kecil.
Setelah n/2 iterasi, nilai-nilai harus ter-sort.
ODD-EVEN TRANSPOSITION SORT (ONE-DIMENSIONAL MESH PROCESSOR
ARRAY):
Parameter n
Global i
Local a {element to be sorted}
t {element taken from adjacent processor}
begin
for i ← 1 to n/2 do
for all Pj, where 0 ≤ j ≤ n-1 do
if j < n-1 and odd(j) then {Odd-even exchange}
t ⇐ successor(a) {Get value from successor}
successor(a)⇐max(a,t) {Give away larger val}
a ← min(a,t) {Keep smaller value}
endif
if even(j) then {Even-odd exchange}
t ⇐ successor(a) {Get value from successor}
successor(a)⇐max(a,t) {Give away larger val}
a ← min(a,t) {Keep smaller value}
endif
endfor
endfor
end
APP - Algoritma Sorting 4/4
Odd-even transposition sort dari delapan nilai pada model array prosesor mesh satu dimensi:
Indeks: 0 1 2 3 4 5 6 7
Nilai awal: G H F D E C B A
Setelah odd-even exchange: G F <H D <E B <C A
Setelah even-odd exchange: F <G D <H B <E A <C
Setelah odd-even exchange: F D <G B <H A <E C
Setelah even-odd exchange: D <F B <G A <H C <E
Setelah odd-even exchange: D B <F A <G C <H E
Setelah even-odd exchange: B <D A <F C <G E <H
Setelah odd-even exchange: B A <D C <F E <G H
Setelah even-odd exchange: A <B C <D E <F G <H
Teorema:
Kompleksitas sorting n elemen pada array prosesor mesh satu dimensi dengan n prosesor
menggunakan odd-even transposition sort adalah Θ(n).
Bukti:
Bukti berdasar fakta bahwa setelah i iterasi loop for luar, tidak ada elemen yang bisa lebih
jauh dari n -2i posisi dari posisi akhir dan ter-sortnya. Dengan demikian, n/2 iterasi cukup
untuk men-sort elemen-elemen tsb, dan kompleksitas waktu algoritma paralel adalah Θ(n),
jika diberikan n elemen processing.

Binary Search

       

Jika kita mempunyai sebuah file dari record-record yang telah dijalankan,

kita dapat melanjutkan menghapuskan memory pemeriksaan yang diperlukan

untuk mendapatkan kembali sebuah record yang telah dipakai oleh suatu teknik

binary search.

Suatu binary search dibandingkan dengan kunci dari pencarian record dengan

record tengah dari sebuah file. Kemudian masing-masing pencarian record

yang telah ditempatkan atau setengah dari file yang telah dihilangkan dengan

pertimbangan yang lebih lanjut. Dalam kasus yang sebelumnya, proses pemban-

dingan dari record tengah dilanjutkan dalam record-record selanjutnya.

Jika kita harus menghilangkan bagian atas dari sebuah file termasuk

record yang telah dibandingkan berlawanan. Selanjutnya jika kita harus

menghilangkan bagian bawah dari sebuah file termasuk record yang telah

dibandingkan berlawanan. Dalam pengulangan proses dari pembandingan

berlawanan dari record tengah, kita akhirnya akan menempatkan record yang

kita inginkan atau menentukan bahwa itu tidak ada dalam file ketika tidak

ada record-record selanjutnya.

Algorithm 2.1

Binary Search.

Terendah = 1.

Tertinggi = n.

While terendah < tertinggi do.

Tengah = (terendah + tertinggi) / 2.

if nilai kunci = nilai (tengah). Then data ditemukan.

Else if nilai kunci > nilai (tengah). Then terendah = tengah + 1.

Else tertinggi = tengah - 1.

end

end

end

Mari kita amati sebuah contoh dari suatu binary search yang telah disajikan terhadap suatu file dari record-record yang telah disusun secara urut. Dalam contoh ini, kita mencari record-record dengan kunci 39, dimana berindikasikan record yang terbaru yang telah dibandingkan berlawanan dari tanda kurung besar membatasi record yang masih dibawah pertimbangan.

Contoh 1

Di bawah ini adalah kunci–kunci carilah kunci 39 dengan mengunakan algorithm Binary Search.

[13, 16, 18, 27, 28, 29, 38, 39, 53].

1 2 3 4 5 6 7 8 9

File ini dinamakan File Sequential (secara berurutan).

Cara penyelesaian.

Bila di cari kunci 39 maka ;

Bila terendah = 1, dan tertinggi = 9,

maka 1 + 9 = 10 , lalu 10 / 2 = 5.

1. Nomor urut 5, adalah kunci 28 , tapi 28 < 39,

[13, 16, 18, 27, 28, 29, 38, 39, 53].

maka terendah = 5 , dan tertinggi = 9,

maka : 5 + 9 = 14

14 / 2 = 7.

2. Nomor urut 7 adalah 38 , tapi 38 < 39,

[13, 16, 18, 27, 28, 29, 38, 39, 53].

maka terendah = 8, dan tertinggi = 9, (karena mid + 1 jadi 7+1=8)

maka : 8 + 9 = 17

17 / 2 = 8,5 => 8,5 ≈ 8

Note: kl mengambil kebawah, haruskonsisten untuk jawaban selanjutnya jika ada kasus yg sama juga harus kebawah

3. Nomor urut 8 adalah kunci 39 , dimana kunci 39 = 39.

[13, 16, 18, 27, 28, 29, 38, 39, 53]

Contoh 2

Ada 2000 kunci Mahasiswa AKAKOM dengana mengunakan Algoritma Binary Search. Carilah kunci 1345

Cara penyelesaian.

1.     pergi ke tengah yaitu ; record dengan kunci 1000.

2.     pergi ke record tengah pada separuh bagian ke-dua yaitu ; record sementara(1001+2000)/2 ketemu 1500, maka Record yang di cari ada diantara 1001- 1500.

3.     pergi ke bagian tengah antara (1001+1499)/2, yaitu ; record 1250. Record yang dicari 1345 > 1250 berarti ada di antara 1250 - 1499.

4.     pergi ke bagian tengah antara (1251+1499)/2 , yaitu ; 1375. Record yang di cari 1345 < 1375 , berarti ada di antara 1251 – 1274.

5.     pergi ke bagian tengah antara (1251+1374)/2 atau 1312,5. Record yang di cari 1345 > 1312 , berarti ada di antara 1313 – 1374.

6.     pergi ke-bagian tengah antara (1313+1374)/2 atau 1343,5. Record yang di cari 1345 > 1343, berarti ada di antara 1344 –1374.

7.     pergi ke-bagian tengah antara (1344+1374)/2 atau 1359. Record yang di cari 1345 < 1359, berarti ada di antara 1334 – 1358.

8.     pergi ke-bagian tengah antara (1344+1358)/2 atau 1351. Record yang di cari 1345 < 1351, berarti ada di antara 1344 – 1350.

9.     pergi ke-bagian tengah antara (1344+1350)/2, atau 1347. Record yang di cari 1345 <1347, berarti ada di antara 1344 – 1346.

10.   pergi ke bagian tengah antara (1344+1346)/2, atau 1345. Record yang di cari1345 = 1345, ketemu.

Contoh 3

Dari data berikut gunakanlah metode binary search

Cari nomer kunci dari 232 , sedangkan jumlah seluruh mahasiswa sebanyak 700 orang.

Pembahasaan :

(1 + 700)/2 = 350

angka 350 lebih besar dari 232, maka kita harus mencarinya kembali.

(1+ 349)/2 = 175

angka 175 lebih kecil dari 232, maka kita akan mencari kembali

(176 + 349)/2 = 262 

angka 362 lebih besar dari 232, maka kita akan melakukan pencarian lagi.

(176 + 261)/2 = 218

angka 218 lebih kecil dari 232 maka dicari lagi

(219 + 261)/2 = 240

angka 240 lebih besar dari 232, maka akan dicari lagi

(219 + 239)/2 = 229

angka 229 lebih kecil dari 232, maka akan dicari lagi

(230 + 239)/2 = 234

angka 234 lebih besar dari 232, maka akan dicari lagi

(230 + 233)/2 = 231

angka 231 lebih kecil dari 232, maka

(232 + 233)/2 = 232

sudah ditemukan

contoh 4

Di bawah ini adalah kunci–kunci carilah kunci 17 dan 39 dengan mengunakan algorithmBinary Search.

[13, 16, 18, 27, 28, 29, 38, 39, 53].

Jawab :

File ini dinamakan File Sequential (secara berurutan).

Cara penyelesaian.

Bila di cari kunci 39 maka

Bila terendah = 1, dan tertinggi = 9,

maka 1 + 9 = 10 , lalu 10 / 2 = 5

1· Nomor urut 5, adalah kunci 28 , tapi 28 < 39,

[13, 16, 18, 27, 28, 29, 38, 39, 53].

maka terendah = 6, dan tertinggi = 9

maka 6 + 9 = 15 lalu 15 / 2 = 7

2· Nomor urut 7 adalah 38 , tapi 38 < 39,

[13, 16, 18, 27, 28, 29, 38, 39, 53].

maka terendah = 8, dan tertinggi = 9,

maka 8 + 9 = 17, lalu 17 / 2 = 8.

3· Nomor urut 8 adalah kunci 39 , dimana kunci 39 = 39.

[13, 16, 18, 27, 28, 29, 38, 39, 53]

Contoh 5

Dari daftar kunci berikut

2,5,11,12,14,19,30,32,41,42,47,49,51,52

Dicari suatu kunci 12 dan 42, tentukan pencarian tersebut dengan metode binary search

Cara penyelesaian.

Jika kita hendak mencari suatu kunci dari daftar berikut maka terlebih dahulu kita harus mengetahui daftar tertinggi dan daftar terendah jadi langkah pertama yang harus di ambil, yaitu :

1· mencari kunci dari angka 12 maka :

nilai terendah = 1 dan nilai tertinggi = 14

maka 1 + 14 = 15, lalu 15/2 = 7,5

2· karena nomer urut 7 adalah 30, maka 30 > 12

[2, 5, 11, 12, 14, 19, 30, 32, 41, 42, 47, 49, 51, 52,]

maka didapat nilai terendah = 1, dan nilai tertinggi adalah = 7

sehingga didapat : 1 + 6 = 7, lalu 7 / 2 = 3.

3· karena nomer urut dari nomer 3 adalah 11, maka 11 < 12

[2, 5, 11, 12, 14, 19, 30, 32, 41, 42, 47, 49, 51, 52,]

maka didapat nilai terendah = 4, dan nilai tertinggi adalah = 6

sehingga didapat : 4 + 6 = 10, lalu 10 / 2 = 5.

4· karena nomer urut dari nomer 5 adalah 14, maka 14 > 12

[2, 5, 11, 12, 14, 19, 30, 32, 41, 42, 47, 49, 51, 52,]

maka didapat nilai terendah = 4, dan nilai tertinggi adalah = 4

sehingga didapat : 4 + 4 = 8, lalu 8 / 2 = 4.

nomer 4 adalah kunci dari nomer 12, dimana kunci 12 = 12. ketemu

Untuk mencari kunci nomer 42 dengan methode Binary Search, maka :

1. dari daftar dibawah ini dapat kita lihat bahwa :

[2, 5, 11, 12, 14, 19, 30, 32, 41, 42, 47, 49, 51, 52,]

didapat nilai terendah = 1, dan nilai tertinggi = 14

hingga di dapat : 1 + 14 = 15, lalu 15 / 2 = 7,5

2. karena nomer urut 7 adalah 30, dan 30 < 42

[2, 5, 11, 12, 14, 19, 30, 32, 41, 42, 47, 49, 51, 52,]

maka di dapat nilai terendah = 8, dan nilai tertinggi = 14

jadi 8 + 14 =22, lalu 22/2 =11

3. karena nomer urut 11 adalah 47, dan 47 > 42

[2, 5, 11, 12, 14, 19, 30, 32, 41, 42, 47, 49, 51, 52,]

maka di dapat nilai terendah = 8, dan nilai tertinggi = 10

jadi 8 + 10 =18, lalu 18/2 =9

4. karena nomer urut 9 adalah 41, dan 41 < 42

[2, 5, 11, 12, 14, 19, 30, 32, 41, 42, 47, 49, 51, 52,]

maka di dapat nilai terendah = 10, dan nilai tertinggi = 10

jadi 10 + 10 =20, lalu 20/2 =10

nomer 10 adalah kunci dari nomer 42, dimana kunci 42 = 42, ketemu