Bab.9 Pengurutan
Tujuan Instruksional
|
|
·
Mempelajari dan menganalisa efisiensi waktu
berbagai algoritma pengurutan.
·
Merancang, mengimplementasikan, dan
menganalisa pengurutan bubble.
·
Merancang, mengimplementasikan, dan
menganalisa pengurutan merge
·
Merancang, mengimplementasikan, dan
menganalisa pengurutan cepat (quick sort).
|
·
Mendesain dan mengimplementasikan suatu heap.
·
Merancang, mengimplementasikan, dan
menganalisa pengurutan heap.
·
Merancang, mengimplementasikan, dan
menganalisa pengurutan bucket dan pengurutan radix.
·
Merancang, mengimplementasikan, dan
menganalisa pengurutan eksternal untuk jumlah data yang besar di dalam file.
|
9.1
Introduksi
Pengurutan merupakan subjek klasik di dalam
ilmu pemrograman. Ada tiga alasan mengapa perlu belajar pengurutan. Pertama,
algoritma pengurutan mengilustrasikan berbagai pendekatan kreatif terhadap
penyelesaian masalah, dan pendekatan ini dapat diterapkan untuk memecahkan
masalah lain. Kedua, pengurutan perlu dan baik untuk mempraktekkan teknik
pemrograman fundamental menggunakan statemen seleksi, loop, metode, dan array. Ketiga,
algoritma pengurutan merupakan contoh yang baik untuk mendemonstrasikan kinerja
algoritma.
Data yang akan diurutkan bisa berupa integer,
double, karakter, atau objek. Algoritma pengurutan seleksi telah dikenalkan
pada Bab. 1. JAVA API memuat berbagai metode pengurutan teroverload untuk
mengurutkan nilai tipe primitif dan objek di dalam kelas java.util.Arrays dan java.util.Collections.
Demi penyederhanaan, bagian ini mengasumsikan:
1.
Data yang akan diurutkan adalah
integer.
2. Data disimpan dalam
suatu array, dan
3.
Data diurutkan secara menaik.
Program-program di sini dapat dengan mudah
dimodifikasi untuk mengurutkan tipe data lain, untuk mengurutkan secara
menurun, atau untuk mengurutkan data di dalam suatu ArrayList dan LinkedList.
Terdapat banyak algoritma pengurutan. Anda
telah belajar pengurutan seleksi dan pengurutan penyisipan di dalam buku ini.
Bab ini akan mengenalkan pengurutan bubble, pengurutan merge, pengurutan quick,
pengurutan bucket, pengurutan radix, dan pengurutan eksternal.
9.2
Pengurutan Bubble
Algoritma pengurutan bubble membuat beberapa
pelewatan melalui array. Setiap kali pelewatan, pasangan-pasangan bertetangga
dibandingkan. Jika suatu pasangan dalam urutan menurut, maka nilainya ditukar;
sebaliknya, jika pasangan dalam urutan menaik, maka nilainya tidak diubah atau
tetap. Teknik ini disebut dengan pengurutan bubble, karena nilai-nilai yang
lebih kecil secara bertahap dibuat mengambang ke atas dan nilai-nilai yang
lebih besar tenggelam ke bawah. Setelah pelewatan pertama, elemen terakhir
menjadi elemen terbesar di dalam array. Setelah pelewatan kedua, elemen
terakhir kedua menjadi elemen terbesar kedua di dalam array. Proses ini
berlanjut sampai semua elemen diurutkan.
Gambar 9.1 menampilkan pelewatan pertama
pengurutan bubble atas suatu array berukuran enam elemen (2 9 5 4 8 1). Pada
perbandingan pasangan pertama (2 dan 9), tidak terjadi penukaran nilai karena
telah terurut secara menaik. Pada perbandingan pasangan kedua (9 dan 5), 9
ditukar dengan 5 karena 9 lebih besar dari 5. Pada perbandingan pasangan ketiga
(9 dan 4), 9 ditukar dengan 4. Pada perbandingan pasangan keempat (9 dan 8), 9
ditukar dengan 8. Pada perbandingan pasangan keempat (9 dan 1), 9 ditukar
dengan 1. Pasangan-pasangan yang sedang dibandingkan dibayangi dan angka-angka
yang telah diurutkan dibuat miring.
Gambar 9.1 Pada setiap pelewatan dilakukan perbandingan
dan pengurutan pasangan-pasangan secara sekuensial
Pelewatan pertama menempatkan angka terbesar
(9) sebagai elemen terakhir di dalam array. Pada pelewatan kedua, seperti
tertampil pada Gambar 9.1b, Anda membandingkan dan mengurutkan
pasangan-pasangan elemen secara sekuensial. Pasangan terakhir tidak perlu
dipertimbangkan, karena elemen terakhir di dalam array sudah menjadi elemen
terbesar. Pada pelewatan ketiga, seperti ditunukkan pada Gambar 9.1c, Anda membandingkan dan mengurutkan
pasangan-pasangan elemen secara sekuensial, kecuali dua elemen terakhir, karena
keduanya telah terurut. Jadi, pada pelewatan ke-k, Anda tidak perlu
mempertimbangkan k-1 elemen terakhir, karena telah diurutkan. Algoritma untuk
pengurutan bubble dideskripsikan pada kode9.1.
Kode9.1 Algoritma Pengurutan Bubble
1
2
3
4
5
6
7
|
for (int k = 1; k < list.length; k++) {
// Melakukan pelewatan ke-k
for (int i = 0; i <
list.length - k; i++) {
if (list[i] > list[i + 1])
tukar list[i] dengan list[i + 1];
}
}
|
Perhatikan bahwa jika penukaran tidak terjadi
di dalam suatu pelewatan, maka tidak perlu untuk melakukan pelewatan
berikutnya, karena semua elemen telah terurut. Anda bisa memakai sifat ini
untuk memperbaiki algoritma sebelumnya pada kode9.2.
Kode9.2 Algoritma Pengurutan Bubble
Terperbaiki
1
2
3
4
5
6
7
8
9
10
11
12
|
boolean butuhPelewatanBerikutnya = true;
for (int k = 1; k <
list.length && butuhPelewatanBerikutnya; k++) {
// Array bisa jadi telah
terurut dan pelewatan berikutnya tidak dibutuhkan
butuhPelewatanBerikutnya = false;
// Melakukan pelewatan ke-k
for (int i = 0; i <
list.length – k; i++) {
if (list[i] > list[i + 1]) {
tukar list[i] dengan list[i + 1];
butuhPelewatanBerikutnya = true; // Pelewatan berikutnya
dibutuhkan
}
}
}
|
Algoritma ini diterapkan dalam kode9.3
sebagai berikut:
Kode9.3 PengurutanBubble.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
public class PengurutanBubble {
/** Metode pengurutan bubble */
public static void pengurutanBubble(int[]
list) {
boolean butuhPelewatanBerikutnya = true;
for (int k = 1; k < list.length &&
butuhPelewatanBerikutnya; k++) {
// Array bisa jadi telah terurut dan pelewatan berikutnya tidak dibutuhkan
butuhPelewatanBerikutnya = false;
for (int i = 0; i <
list.length - k; i++) {
if (list[i] > list[i + 1]) {
// Tukar list[i] dengan list[i + 1]
int temp = list[i];
list[i] = list[i + 1];
list[i + 1] = temp;
butuhPelewatanBerikutnya = true;
// Pelewatan berikutnya dibutuhkan
}
}
}
}
/** Metode untuk menguji */
public static void main(String[]
args) {
int[] list = {2, 3, 2, 5, 6, 1, -2,
3, 14, 12};
pengurutanBubble(list);
for (int i = 0; i <
list.length; i++)
System.out.print(list[i] + "
");
}
}
|
Keluaran
-2 1 2 2 3 3 5 6 12 14
9.2.1 Waktu Pengurutan Bubble
Dalam kasus terbaik, algoritma pengurutan
bubble hanya membutuhkan pelewatan pertama untuk menemukan bahwa array
sebenarnya telah terurut. Pelewatan berikutnya tidak dibutuhkan. Karena
perbandingan angka sebanyak n - 1 pada pelewatan pertama, waktu yang dibutuhkan
pada kasus terbaik pengurutan bubble ini adalah
(n).
Dalam kasus terburuk, algoritma pengurutan
bubble membutuhkan n – 1 pelewatan. Pelewatan pertama membutuhkan n – 1
perbandingan; pelewatan kedua membutuhkan n – 2 perbandingan; dan seterusnya;
pelewatan terakhir membutuhkan satu perbandingan. Jadi, total jumlah
perbandingan adalah
Oleh karena itu, waktu untuk kasus terburuk
pengurutan bubble adalah
.
9.3 Pengurutan Merge
Algoritma pengurutan merge dapat
dideskripsikan secara rekursif sebagai berikut: algoritma membagi array menjadi
dua bagian dan menerapkan pengurutan merge terhadap setiap bagian secara
rekursif. Setelah kedua bagian diurutkan, keduanya digabungkan kembali.
Algoritma ini diberikan pada kode9.4.
Kode9.4 Algoritma Pengurutan Merge
1
2
3
4
5
6
7
8
|
public static void pengurutanMerge(int[]
list) {
if (list.length
> 1) {
pengurutanMerge (list[0 ...
list.length / 2]);
pengurutanMerge (list[list.length / 2 +
1 ...
list.length]);
menggabungkan list[0 ...
list.length / 2]
dengan
list[list.length / 2
+ 1 ...
list.length];
}
}
|
Gambar 9.2 mengilustrasikan suatu pengurutan
merge terhadap suatu array delapan elemen (2 9 5 4 8 1 6 7). Array awal dipecah
menjadi dua (2 9 5 4) dan (8 1 6 7). Kemudian pada kedua subarray tersebut
diterapkan pengurutan merge secara rekursif untuk memecah (2 9 5 4) menjadi (2
9) dan (5 4) dan (8 1 6 7) menjadi (8 1) dan (6 7). Proses ini berlanjut sampai
subarray hanya memuat satu elemen. Sebagai contoh, (2 9) dipecah menjadi (2)
dan (9). Karena (2) hanya memuat satu elemen, maka tidak bisa dipecah lagi. Sekarang
(2) dan (9) digabungkan menjadi suatu array baru terurut (2 9); (5) dan (4)
digabungkan menjadi (4 5). Kemudian (2 9) dan (4 5) menjadi suatu array baru
terurut (2 4 5 9), dan terakhir (2 4 5 9) dan (1 6 7 8) digabungkan menjadi (1
2 4 5 6 7 8 9).
Pemanggilan rekursif terus membagi array
menjadi sub-subarray sampai setiap subarray hanya memuat satu elemen. Algoritma
kemudian menggabungkan semua subs-subarray kecil ini menjadi sub-subarray
terurut yang lebih besar sampai menjadi satu array hasil terurut.
Algoritma pengurutan merge diimplementasikan
pada kode9.5.
Gambar 9.2 Pengurutan merge menerapkan pendekatan
bagi-gabung untuk mengurutkan array
Kode9.5 PengurutanMerge.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
public class PengurutanMerge {
/**
Metode untuk mengurutkan angka */
public static void pengurutanMerge(int[]
list) {
if
(list.length > 1) {
//
Pengurutan Merge untuk setengah bagian pertama
int[]
setengahPertama = new int[list.length / 2];
System.arraycopy(list,
0, setengahPertama, 0, list.length / 2);
pengurutanMerge(setengahPertama);
// Pengurutan Merge untuk setengah bagian
kedua
int
panjangSetengahKedua = list.length - list.length / 2;
int[]
setengahKedua = new int[panjangSetengahKedua];
System.arraycopy(list,
list.length / 2,
setengahKedua,
0, panjangSetengahKedua);
pengurutanMerge(setengahKedua);
//
Menggabungkan setengahPertama dengan setengahKedua
int[]
temp = gabung(setengahPertama, setengahKedua);
System.arraycopy(temp,
0, list, 0, temp.length);
}
}
/**
Menggabungkan dua list terurut */
private static int[] gabung(int[] list1, int[]
list2) {
int[]
temp = new int[list1.length + list2.length];
int
sekarang1 = 0; // Indeks sekarang dalam list1
int
sekarang2 = 0; // Indeks sekarang dalam list2
int
sekarang3 = 0; // Indeks sekarang dalam temp
while
(sekarang1 < list1.length && sekarang2 < list2.length) {
if
(list1[sekarang1] < list2[sekarang2])
temp[sekarang3++] = list1[sekarang1++];
else
temp[sekarang3++] = list2[sekarang2++];
}
while
(sekarang1 < list1.length)
temp[sekarang3++]
= list1[sekarang1++];
while
(sekarang2 < list2.length)
temp[sekarang3++]
= list2[sekarang2++];
return
temp;
}
/**
Metode untuk menguji */
public
static void main(String[] args) {
int[]
list = {2, 3, 2, 5, 6, 1, -2, 3, 14, 12};
pengurutanMerge(list);
for
(int i = 0; i < list.length; i++)
System.out.print(list[i]
+ " ");
}
}
|
Metode pengurutanMerge
(baris 3-21) menciptakan suatu array baru setengahPertama,
yang merupakan salinan dari setengah bagian pertama dari list (baris 7). Algoritma memanggil pengurutanMerge secara rekursif pada setengahPertama (baris 8). Panjang dari setengahPertama adalah list.length/2
dan panjang dari setengahKedua
adalah list.length-list.length/2.
Array baru setengahKedua diciptakan
untuk memuat setengah bagian kedua dari array awal list. Algoritma memanggil pengurutanMerge
secara rekursif pada setengahKedua(baris
15). Setelah setengahPertama dan setengahKedua diurutkan, keduanya
digabungkan kembali menjadi suatu array baru terurut temp (baris 18). Terakhir, temp
ditugaskan kepada array awal list
(baris 19). Jadi, sekarang array list
telah terurut.
Metode gabung
(baris 24-45) menggabungkan dua array
terurut. Metode ini menggabungkan array list1
dan list2 ke dalam suatu array
temporer temp. Jadi, length.temp sama dengan list1.length + list2.length (baris 25).
sekarang1 dan sekarang2 menunjuk pada elemen sekarang yang ditinjau pada list1 dan list2 (baris 27-28). Metode ini yang secara ulang membandingkan
elemen-elemen sekarang dari list1
dan list2 dan yang memindahkan nilai
yang lebih kecil ke temp.sekarang1 diinkremen
sebesar 1 jika nilai yang lebih kecil ada di list1 (baris 33) dan sekarang2
diinkremen sebesar 1 jika nilai yang lebih kecil ada di list2 (baris 35). Terakhir, semua elemen di dalam salah satu list
dipindahkan ke temp. Jika masih ada
elemen-elemen yang tidak dipindahkan di dalam list1, maka semuanya disalin ke temp (baris 38-39). Jika masih ada elemen-elemen yang tidak
dipindahkan di dalam list2, maka
semuanya disalin ke temp (baris
41-42). Metode kemudian mengembalikan temp
sebagai nilai balik sebagai suatu array baru terurut pada baris 44.
Gambar 9.3 Dua array terurut digabungkan menjadi satu
array terurut
Gambar 9.3 mengilustrasikan bagaimana
menggabungkan dua array list1 (2 4 5
9) dan list2 (1 6 7 8). Awalnya,
nilai-nilai sekarang yang ditinjau di dalam array adalah 1 dan 2. Kemudian
keduanya dibandingkan dan memindahkan 1 ke temp,
seperti tertampil pada Gambar 9.3a. sekarang2
dan sekarang3 diinkremen sebesar 1.
Pembandingan elemen-elemen sekarang dari dua array dan pemindahan nilai yang
lebih kecil ke temp terus dilakukan
sampai salah satu array tuntas dipindahkan. Seperti ditunjukkan pada Gambar
9.3b, semua elemen di dalam list2
dipindahkan ke temp dan sekarang1 menunjuk ke 9 di dalam list1. Nilai elemen 9 dipindahkan ke temp, seperti ditunjukkan pada Gambar
9.3c.
9.3.1 Waktu Pengurutan Merge
Dimisalkan
merupakan waktu yang dibutuhkan
untuk mengurutkan suatu array yang memuat n elemen menggunakan pengurutan
merge. Algoritma pengurutan merge memecah array menjadi dua subarray,
mengurutkan kedua subarray menggunakan algoritma yang sama secara rekursif, dan
kemudian menggabungkan kembali sub-subarray terurut tersebut. Jadi,
Kompleksitas pengurutan merge adalah
. Algoritma ini lebih baik dari pengurutan seleksi, pengurutan
penyisipan, dan pengurutan bubble. Metode sort
di dalam kelas java.util.Arrays
diimplementasikan menggunakan berbagai variasi dari algoritma pengurutan merge.
9.4
Pengurutan Quick
Pengurutan quick, yang dikembangkan oleh
C.A.R. Hoare (1962), bekerja sebagai berikut: Algoritma memilih suatu elemen,
yang disebut dengan pivot, di dalam array. Array kemudian dibagi dua bagian
sehingga semua elemen di bagian pertama kurang dari atau sama dengan pivot dan
semua elemen di bagian kedua lebih dari pivot. Algoritma pengurutan quick
secara rekursif diterapkan pada bagian pertama dan kemudian bagian kedua.
Algoritma ini dideskripsikan pada kode9.6.
Kode9.6 Algoritma Pengurutan Quick
1
2
3
4
5
6
7
8
9
10
|
public
static void pengurutanQuick(int[] list) {
if (list.length
> 1) {
pilih suatu pivot;
partisi list menjadi list1 dan list2 sehingga
semua elemen di dalam list1 <= pivot
dan
semua elemen di dalam list2 > pivot;
pengurutanQuick (list1);
pengurutanQuick (list2);
}
}
|
Setiap partisi pivot di sebelah kanan.
Pemilihan pivot mempengaruhi kinerja algoritma. Idealnya, Anda seharusnya
memilih pivot yang membagi dua bagian array dengan sama. Untuk penyederhanaan,
diasumsikan bahwa elemen pertama di dalam array dipilih sebagai pivot.
Gambar 9.4 mengilustrasikan bagaimana
mengurutkan suatu array (5 2 9 3 8 4 0 1 6 7) menggunakan pengurutan quick. Elemen
pertama 5 dipilih sebagai pivot. Array dipartisi menjadi dua bagian, seperti
tertampil pada Gambar 9.4b. Pivot yang diterangi ditempatkan di sebelah kanan
array. Pengurutan quick diterapkan pada dua array parsial tersebut (4 2 1 3 0)
dan kemudian (8 9 6 7). Pivot 4 mempartisi (4 2 1 3 0) menjadi satu array
parsial (0 2 1 3), seperti tertampil pada Gambar 9.4c. Pengurutan quick
diterapkan pada (0 2 1 3). Pivot 0 mempartisinya menjadi satu array parsial (2
1 3), seperti tertampil pada Gambar 9.4d. Pengurutan quick diterapkan pada (2 1
3). Pivot 2 membaginya menjadi (1) dan (3), seperti tertampil pada Gambar 9.4e.
Pengurutan quick diterapkan pada (1). Karena array hanya memuat satu elemen
saja, partisi tidak dibutuhkan.
Gambar 9.4 Algoritma pengurutan quick secara rekursif
diterapkan pada array-array parsial
Algoritma pengurutan quick diimplementasikan
pada kode9.7. Terdapat dua metode pengurutanQuick
teroverload di dalam kelas. Metode pertama (baris 2) digunakan untuk
mengurutkan suatu array. Metode kedua adalah helper (baris 6) yang mengurutkan
suatu array parsial dengan suatu rentang tertentu.
Kode9.7 PengurutanQuick.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
public class PengurutanQuick {
public static void pengurutanQuick(int[] list) {
pengurutanQuick(list, 0, list.length - 1);
}
private static void
pengurutanQuick(int[]
list, int pertama, int terakhir) {
if (terakhir > pertama) {
int indeksPivot = partisi(list,
pertama, terakhir);
pengurutanQuick(list, pertama, indeksPivot
- 1);
pengurutanQuick(list, indeksPivot + 1,
terakhir);
}
}
/** Mempartisi array list[pertama..terakhir]
*/
private static int partisi(int[] list, int pertama, int terakhir) {
int pivot = list[pertama]; //
Memilih elemen pertama sebaagai pivot
int rendah = pertama + 1; // Indeks
untuk pencarian maju
int tinggi = terakhir; // indeks
untuk pencarian mundur
while (tinggi > rendah) {
// Mencari secara maju dari kiri
while (rendah <= tinggi
&& list[rendah] <= pivot)
rendah++;
//
Mencari secara mundur dari kanan
while (rendah <= tinggi
&& list[tinggi] > pivot)
tinggi--;
// Menukar dua elemen di dalam list
if (tinggi > rendah) {
int temp = list[tinggi];
list[tinggi] = list[rendah];
list[rendah] = temp;
}
}
while (tinggi > pertama
&& list[tinggi] >= pivot)
tinggi--;
// Menukar pivot dengan list[tinggi]
if (pivot > list[tinggi]) {
list[pertama] = list[tinggi];
list[tinggi] = pivot;
return tinggi;
}
else {
return pertama;
}
}
/** Metode untuk menguji */
public static void main(String[]
args) {
int[] list = {2, 3, 2, 5, 6, 1, -2,
3, 14, 12};
pengurutanQuick(list);
for (int i = 0; i <
list.length; i++)
System.out.print(list[i] + "
");
}
}
|
Keluaran
-2 1 2 2 3 3 5 6 12 14
Metode partisi (baris 15-49) mempartisi array list[pertama..terkahir] menggunakan
pivot. Elemen pertama di dalam array parsial dipilih sebagai pivot (baris 16).
Awalnya, rendah menunjuk ke elemen
kedua di dalam array parsial (baris 17) dan tinggi menunjuk ke elemen terakhir di dalam array parsial (baris
18).
Metode
mencari elemen pertama dari kiri secara maju di dalam array yang lebih besar
dari pivot (baris 22-23), dan kemudian mencari elemen pertama dari kanan secara
mundur di dalam array yang lebih kecil atau sama dengan pivot (baris 26-27). Kemudian
kedua elemen tersebut ditukar. Operasi pencarian dan penukaran yang sama
diulangi sampai semua elemen selesai dicari di dalam suatu loop while (baris 20-35).
Metode
mengembalikan indeks baru untuk pivot yang membagi array parsial menjadi dua
bagian jika pivot telah dipindahkan (baris 44). Sebaliknya, indeks awal pivot
yang dijadikan nilai balik (baris 47).
Gambar 9.5 mengilustrasikan bagaimana
mempartisi suatu array (5 2 9 3 8 4 0 1 6 7). Elemen pertama 5 dipilih sebagai pivot. Awalnya,
rendah adalah indeks yang menunjuk
elemen 2 dan tinggi menunjuk elemen
7, seperti tertampil pada Gambar 9.5a. Indeks rendah bergerak maju untuk mencari elemen pertama (9) yang lebih
besar dari pivot dan menggerakkan indeks tinggi secara mundur untuk mencari
elemen pertama (1) yang lebih kecil atau sama dengan pivot, seperti ditunjukkan
pada Gambar 9.5b. Kemudian elemen 9 dan 1 saling ditukar, seperti tertampil
pada Gambar 9.5c. Pencarian terus dilanjutkan dan pemindahan rendah untuk menunjuk ke elemen 8 dan tinggi untuk menunjuk ke elemen 0,
seperti tertampil pada Gambar 9.5d. Kemudian elemen 8 ditukar dengan 0, seperti
ditunjukkan pada Gambar 9.5e. Penggeseran rendah
diteruskan sampai melewati tinggi,
seperti pada Gambar 9.5f. Sekarang, semua elemen telah diperiksa. Kemudian
pivot ditukar dengan elemen 4 pada indeks tinggi.
Partisi terakhir ditampilkan pada Gambar 9.5g. Indeks dari pivot dijadikan
nilai balik ketika metode selesai.
Gambar
9.5 Metode partisi mengembalikan indeks pivot
9.4.1
Waktu Pengurutan Quick
Untuk
mempartisi suatu array n elemen, diperlukan n perbandingan dan n pemindahan
dalam kasus terburuk. Jadi, waktu yang diperlukan untuk partisi adalah
(n).
Pada
kasus terburuk, pivot setiap kali membagi array menjadi satu subarray besar dan
satu subarray kosong. Ukuran subarray besar tersebut adalah lebih kecil satu
dari array sebelum partisi. Algoritma memerlukan (n – 1) + (n – 2) + ...+ 2 + 1
=
komputasi.
Pada
kasus terbaik, pivot setiap kali membagi array menjadi dua bagian yang
berukuran hampir sama. Dimisalkan
adalah waktu yang dibutuhkan untuk mengurutkan
suatu array n elemen menggunakan pengurutan quick, maka
Sama
dengan pengurutan merge, kompleksitas pengurutan quick adalah
.
9.5
Pengurutan Heap
Pengurutan
heap menggunakan suatu heap biner, yang merupakan suatu pohon biner sempurna. Pohon
biner tersebut bisa kosong atau memuat suatu elemen, yang disebut dengan akar,
dan dua pohon biner berbeda yang disebut dengan subpohon kanan dan subpohon
kiri. Panjang suatu path atau jalur adalah jumlah tepi di dalam jalur.
Kedalaman suatu simpul (node) adalah panjang jalur dari akar ke simpul. Heap
adalah suatu pohon biner dengan dua watak sebagai berikut:
·
Merupakan pohon biner sempurna.
·
Setiap simpul lebih besar atau sama dengan anaknya.
Suatu
pohon biner disebut sempurna atau penuh jika setiap levelnya penuh. Tetapi, pada
level terakhir bisa jadi tidak penuh dan pada kasus itu, semua daun pada level
terakhir harus ditempatkan paling kiri. Sebagai contoh, pada Gambar 9.6, pohon
biner pada (a) dan (b) adalah pohon sempurna, tetapi pohon pada (c) dan (d)
adalah pohon biner tidak sempurna. Pohon pada (a) merupakan suatu heap,
sedangkan pada (b) bukan heap, karena akar (39) kurang dari anak kanannya (42).
Gambar
9.6 Heap merupakan suatu pohon biner
sempurna spesial
9.5.1
Menyimpan Heap
Suatu
heap dapat disimpan di dalam suatu ArrayList
atau suatu array jika ukuran heap telah diketahui. Heap pada Gambar 9.8a dapat
disimpan menggunakan array pada Gambar 9.8b. Akar berada pada posisi 0, dan
kedua anaknya pada posisi 1 dan 2. Untuk suatu simpul pada posisi i, anak
kirinya berada pada posisi 2i + 1, anak kananya pada posisi 2i + 2, dan
orangtuanya pada posisi (i – 1)/2. Sebagai contoh, simpul untuk elemen 39
berada pada posisi 4, jadi posisi anak kirinya (elemen 14) pada 9 (2 x 4 + 1),
posisi anak kanannya (elemen 33) pada 10 (2 x 4 + 2), dan posisi orangtuanya
(elemen 42) pada 1 ((4 – 1)/2).
Gambar
9.7 Salah satu perangkat animasi
online memampukan Anda untuk mengentri suatu kunci dan menghapus akar secara
visual
Gambar
9.8 Suatu heap biner
diimplementasikan menggunakan array
9.5.2
Menambah Simpul Baru
Untuk
menambahkan suatu simpul baru pada heap, pertama-tama simpul tersebut
ditambahkan ke ujung heap dan kemudian membangun-ulang pohon sebagai berikut:
Simpul terakhir menjadi simpul
sekarang;
while (simpul
sekarang lebih besar dari orangtuanya) {
Tukar simpul sekarang dengan orangtuanya;
Simpul sekarang menjadi satu level lebih tinggi;
}
Dimisalkan
awalnya heap kosong. Heap ditampilkan pada Gambar 9.9, setelah menambahkan
angka-angka 3, 5, 1, 19, 11, dan 22.
Gambar
9.9 Elemen-elemen 3, 5, 1, 19, 11,
dan 22 disisipkan ke dalam heap
Selanjutnya
perhatikan penambahan 88 ke dalam heap. Simpul baru 88 ditempatkan pada ujung
pohon, seperti tertampil pada Gambar 9.10a. Elemen 88 ditukar dengan 19,
seperti ditunjukkan pada Gambar 9.10b. Elemen 88 ditukar dengan 22, seperti
ditunjukkan pada Gambar 9.10c.
Gambar
9.10 Membangun-ulang heap setelah
menambah suatu simpul baru
9.5.3
Menghapus Akar
Seringkali
Anda ingin menghapus elemen maksimum, yang merupakan akar dari suatu heap. Setelah
akar dihapus, pohon harus dibangun-ulang untuk mempertahankan watak heap.
Algoritma untuk membangun-ulang pohon heap dideskripsikan sebagai berikut:
Memindahkan simpul terakhir untuk
menggantikan akar;
Akar menjadi simpul sekarang;
while (simpul
sekarang memiliki anak dan simpul sekarang lebih
kecil
dari salah satu anaknya) {
Tukar simpul sekarang dengan anak yang lebih besar;
Simpul sekarang menjadi satu level lebih tinggi;
}
Gambar
9.11 Membangun-ulang heap setelah akar
62 dihapuskan
Gambar
9.12 Membangun-ulang heap setelah akar
59 dihapuskan
Gambar
9.11 menunjukkan proses pembangunan-ulang suatu heap setelah akar 62 dihapus
dari Gambar 9.8a. Simpul terakhir 9 dipindahkan ke akar seperti tertampil pada
Gambar 9.11a. Elemen 9 ditukar dengan 59 seperti ditunjukkan pada Gambar 9.11b.
Elemen 9 ditukar dengan 44 seperti ditunjukkan pada Gambar 9.11c. Elemen 9
ditukar dengan 30 seperti ditunjukkan pada Gambar 9.11d.
Gambar
9.12 menunjukkan proses pembangunan-ulang suatu heap setelah akar 59 dihapus
dari Gambar 9.11d. Simpul terakhir 17 dipindahkan ke akar seperti tertampil
pada Gambar 9.12a. Elemen 17 ditukar dengan 44 seperti ditunjukkan pada Gambar
9.12b. Elemen 17 ditukar dengan 30 seperti ditunjukkan pada Gambar 9.12c.
9.5.4
Kelas Heap
Sekarang
Anda telah siap untuk mendesain dan mengimplementasikan kelas Heap. Diagram kelas ditampilkan pada
Gambar 9.13. Implementasinya diberikan pada kode9.8.
Gambar
9.13 Kelas Heap menyediakan beberapa operasi untuk memanipulasi suatu heap
Kode9.8 Heap.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
public class Heap<E extends Comparable> {
private
java.util.ArrayList<E> list = new
java.util.ArrayList<E>();
/** Menciptakan suatu heap default */
public
Heap(){
}
/** Menciptakan suatu heap dari array objek
*/
public
Heap(E[] objek){
for (int i = 0; i <
objek.length; i++)
add(objek[i]);
}
/** Menambah suatu objek baru ke dalam heap
*/
public void
add(E objekBaru){
list.add(objekBaru); // Menyambung ke heap
int indeksSekarang = list.size() -
1; // Indeks dari simpul terakhir
while (indeksSekarang > 0) {
int indeksOrangtua =
(indeksSekarang - 1) / 2;
// Menukar jika objek sekarang lebih
besar dari orangtuanya
if
(list.get(indeksSekarang).compareTo(
list.get(indeksOrangtua)) > 0) {
E temp = list.get(indeksSekarang);
list.set(indeksSekarang,
list.get(indeksOrangtua));
list.set(indeksOrangtua, temp);
}
else
break; // Pohon menjadi suatu
heap sekarang
indeksSekarang = indeksOrangtua;
}
}
/** Menghapus akar dari heap */
public E
remove(){
if (list.size() == 0) return
null;
E objekDihapus = list.get(0);
list.set(0, list.get(list.size() - 1));
list.remove(list.size() - 1);
int indeksSekarang = 0;
while (indeksSekarang <
list.size()) {
int indeksAnakKiri = 2 *
indeksSekarang + 1;
int indeksAnakKanan = 2 *
indeksSekarang + 2;
// Mencari maksimum dari dua anak
if (indeksAnakKiri >=
list.size()) break; // Pohon adalah suatu heap
int indeksMaks = indeksAnakKiri;
if (indeksAnakKanan <
list.size()) {
if
(list.get(indeksMaks).compareTo(
list.get(indeksAnakKanan)) < 0)
{
indeksMaks = indeksAnakKanan;
}
}
// Menukar jika simpul sekarang kurang
dari maksimum
if
(list.get(indeksSekarang).compareTo(
list.get(indeksMaks)) < 0) {
E temp = list.get(indeksMaks);
list.set(indeksMaks, list.get(indeksSekarang));
list.set(indeksSekarang, temp);
indeksSekarang = indeksMaks;
}
else
break; // Pohon adalah suatu
heap
}
return objekDihapus;
}
/** Mendapatkan jumlah simpul di dalam pohon
*/
public int
getSize(){
return list.size();
}
}
|
Suatu
heap direpresentasikan secara internal (baris 2). Anda bisa mengubahnya menjadi
struktur data yang lain, tetapi kontrak kelas Heap tetap tidak berubah.
Metode add (baris 15-33) menyambungkan objek
ke pohon dan kemudian menukarnya dengan orangtuanya jika objek tersebut lebih
besar dari orangtuanya. Proses ini berlanjut sampai objek baru tersebut menjadi
akar atau sampai tidak lebih besar dari orangtuanya.
Metode remove(baris 36-71) menghapus dan
menjadikan akar sebagai nilai balik. Untuk mempertahankan watak heap, metode
ini memindahkan objek terakhir ke posisi akar dan menukarnya dengan anak yang
lebih besar jika objek tersebut kurang dari anak yang lebih besar. Proses ini
berlanjut sampai objek terakhir menjadi daun atau kurang dari anaknya.
9.5.5
Pengurutan Menggunakan Kelas Heap
Kode9.9
menyajikan suatu algoritma untuk mengurutkan suatu array menggunakan heap.
Kode9.9 PengurutanHeap.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public class PengurutanHeap {
/** Metode pengurutan Heap */
public static <E extends Comparable> void pengurutanHeap(E[]
list) {
// Menciptakan suatu heap integer
Heap<E> heap = new
Heap<E>();
// Menambah elemen ke heap
for (int i = 0; i <
list.length; i++)
heap.add(list[i]);
// Menghapus elemen dari heap
for (int i = list.length -
1; i >= 0; i--)
list[i] = heap.remove();
}
/** Metode untuk menguji */
public static void main(String[]
args) {
Integer[] list = {2, 3, 2, 5, 6, 1, -2, 3,
14, 12};
pengurutanHeap(list);
for (int i = 0; i <
list.length; i++)
System.out.print(list[i] + "
");
}
}
|
Keluaran
-2 1 2 2 3 3 5 6 12 14
9.5.6
Kompleksitas Waktu Pengurutan Heap
Sekarang
perhatian diarahkan untuk menganalisa kompleksitas waktu pengurutan heap.
Dimisalkan h adalah tinggi suatu heap yang memuat n elemen. Karena heap
merupakan pohon biner sempurna, level pertama memiliki satu simpul, level kedua
dua simpul, level ke-k memiliki
simpul, level ke-(h - 1) memiliki
simpul, dan level ke-h memiliki paling sedikit
1 simpul dan paling banyak
simpul. Oleh karena itu,
Jadi,
dan
. Oleh karen itu,
. Jadi, ketinggian heap
adalah
.
9.6
Pengurutan Bucket dan Pengurutan Radix
Semua
algoritma pengurutan yang telah didiskusikan sejauh ini merupakan algoritma
pengurutan umum yang dapat diterapkan pada sembarang tipe kunci (integer,
string, dan sembarang objek yang bisa dibandingkan). Semua algoritma ini
mengurutkan elemen menggunakan kunci. Batas bawah algoritma pengurutan yang
telah dipelajari adalah
. Jadi, tidak ada algoritma
yang berbasis perbandingan yang dapat bekerja lebih baik dari
. Tetapi, jika kuncinya
adalah integer-integer kecil, maka Anda bisa menggunakan pengurutan bucket
tanpa perlu membandingkan kunci-kunci.
Algoritma
pengurutan bucket bekerja sebagai berikut. Diasumsikan kunci ada dalam rentang
0 sampai N – 1. Dibutuhkan N bucket yang diberi label 0, 1, ..., dan N – 1.
Jika kunci suatu elemen adalah i, maka elemen tersebut ditempatkan ke dalam
bucket i. Setiap bucket memuat elemen-elemen dengen nilai kunci sama. Anda bisa
menggunakan suatu ArrayList untuk
mengimplementasikan suatu bucket.
Algoritma
pengurutan bucket dideskripsikan sebagai berikut:
void pengurutanBucket(E[]
list) {
E[] bucket = (E[])new java.util.ArrayList[N];
// Mendistribusikan elemen-elemen dari list ke bucket
for (int i
= 0; i < list.length; i++) {
int kunci =
list[i].getKey();
if (bucket[kunci] ==
null)
bucket[kunci] = new java.util.ArrayList();
bucket[kunci].add(list[i]);
}
// Sekarang memindahkan kembali elemen-elemen dari bucket ke list
int k = 0;
// k adalah suatu indeks untuk list
for (int i
= 0; i < bucket.length; i++)
{
if (bucket[i] != null)
{
for (int
j = 0;
j < bucket[i].size(); j++)
list[k++] = bucket[i].get(j);
}
}
}
Jelaslah
bahwa diperlukan
waktu untuk mengurutkan list, dimana
adalah ukuran list.
Perhatikan
jika N terlalu besar, maka pengurutan bucket menjadi tidak realistis. Dan pada kasus
ini, Anda bisa menggunakan pengurutan radix. Pengurutan radix adalah pengurutan
yang berbasis pengurutan bucket.
Patut
diketahui bahwa pengurutan bucket adalah pengurutan stabil, yang berarti bahwa
jika dua elemen di dalam list memiliki kunci sama, maka urutannya tidak berubah
di dalam list terurut. Yaitu, jika elemen e1
dan elemen e2 memiliki kunci sama
dan e1 mendahului e2 di dalam list awal, maka e1 masih tetap mendahului e2 di dalam list terurut.
Diasumsikan
bahwa kunci adalah integer positif. Ide pengurutan radix adalah membagi
kunci-kunci ke dalam sub-subgrup berdasarkan pada posisi radiksnya. Kemudian
pengurutan bucket diterapkan secara berulang untuk nilai-nilai kunci pada
posisi-posisi radiks, dimulai dari posisi yang paling kurang signifikan.
Perhatikan
pengurutan elemen-elemen dengan kunci-kunci:
331, 454, 230, 34, 343, 45,
59, 453, 345, 231, 9
Pengurutan
bucket diterapkan pada posisi radiks terakhir. Elemen-elemen ditempatkan ke
dalam bucket sebagai berikut:
Setelah
dihapus atau dibuang dari bucket, elemen-elemen menjadi urutan berikut:
Pengurutan
bucket diterapkan pada posisi radiks kedua terakhir. Elemen-elemen ditempatkan
ke dalam bucket sebagai berikut:
Setelah
dihapus atau dibuang dari bucket, elemen-elemen menjadi urutan berikut:
Pengurutan
bucket diterapkan pada posisi radiks ketiga terakhir. Elemen-elemen ditempatkan
ke dalam bucket sebagai berikut:
Setelah
dihapus atau dibuang dari bucket, elemen-elemen menjadi urutan berikut:
Elemen-elemen
sekarang telah terurut.
9.7
Pengurutan Eksternal
Semua
algoritma pengurutan yang didiskusikan terdahulu mengasumsikan bahwa semua data
yang akan diurutkan tersedia pada satu waktu di dalam memori internal seperti
suatu array. Untuk mengurutkan data yang disimpan di dalam file eksternal, Anda
pertama-tama bisa membawa data ke memori, kemudian mengurutkannya. Namun, jika
file terlalu besar, maka semua data di dalam file tidak bisa dibawa ke memori
pada waktu bersamaan. Bagian ini akan mendiskusikan bagaimana mengurutkan data
di dalam suatu file eksternal yang besar.
Untuk
penyederhanaan, diasumsikan dua juta nilai int
disimpan di dalam suatu file biner yang dinamai databesar.dat. File diciptakan menggunakan program pada kode9.10.
Kode9.10 MenciptakanFileBesar.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
import java.io.*;
public class MenciptakanFileBesar {
public static void main(String[]
args) throws Exception {
DataOutputStream keluaran = new DataOutputStream(
new BufferedOutputStream(
new FileOutputStream("databesar.dat")));
for (int i = 0; i <
800004; i++)
keluaran.writeInt((int)(Math.random() * 1000000));
keluaran.close();
// Menampilkan 30 angka pertama
DataInputStream masukan =
new DataInputStream(new
FileInputStream("databesar.dat"));
for (int i = 0; i < 30;
i++)
System.out.print(masukan.readInt() +
" ");
masukan.close();
}
}
|
Keluaran
682227 188680 436686 103474
600817 12877 743184 334112 687718 905047 115252 163525 292181 950727 455400
644322 156273 954889 821198 280504 931124 432318 456628 756805 548823 892390
410171 328903 824500 573308 ...
Gambar
9.14 File awal atau asli diurutkan
dalam segmen-segmen
Suatu
variasi dari pengurutan merge dapat dipakai untuk mengurutkan file ini dalam
dua fase:
Fase I: Secara
berulang membawa data dari file ke suatu array, mengurutkan array tersebut
menggunakan algoritma pengurutan internal, dan mengeluarkan data dari array ke
suatu file temporer. Proses ini ditampilkan pada Gambar 9.14. Idealnya, Anda ingin
menciptakan suatu file besar, tetapi ukuran maksimumnya bergantung pada berapa
banyak memori yang dialokasikan ke JVM oleh sistem operasi. Diasumsikan bahwa
ukuran array maksimum adalah 100000 nilai int.
Di dalam file temporer, setiap int
diurutkan, dalam segmen-segmen
,
dan
.
Fase II: Pasangan
segmen-segmen terurut digabungkan (yaitu,
dengan
,
dengan
, dan seterusnya) menjadi
suatu segmen terurut yang lebih besar dan menyimpan segmen baru tersebut ke
suatu file temporer yang baru. Proses yang sama diulangi sampai menghasilkan
satu segmen terurut. Gambar 9.15 menunjukkan bagaimana menggabung delapan
segmen.
Gambar
9.15 Segmen-segmen terurut digabungkan
secara iteratif
9.7.1
Implementasi Fase I
Kode9.11
menyajikan metode yang membaa setiap segmen data dari file, mengurutkan segmen,
dan menyimpan segmen-segmen terurut tersebut di dalam suatu file baru. Metode
ini mengembalikan jumlah segmen yang telah diurutkan.
Kode9.11 Menciptakan Segmen-Segmen
Terurut Inisial
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
/** Mengurutkan file awal menjadi
segmen-segmen terurut */
private static int InisialisasiSegmen
(int ukuranSegmen, String fileAsli,
String f1)
throws Exception {
int[] list = new int[ukuranSegmen];
DataInputStream masukan = new
DataInputStream(
new BufferedInputStream(new
FileInputStream(fileAsli)));
DataOutputStream keluaran = new
DataOutputStream(
new BufferedOutputStream(new
FileOutputStream(f1)));
int jumlahSegmen = 0;
while (masukan.available() > 0) {
jumlahSegmen++;
int i = 0;
for ( ; masukan.available() > 0
&& i < ukuranSegmen; i++) {
list[i] = masukan.readInt();
}
// Mengurutkan suatu list array[0..i-1]
java.util.Arrays.sort(list, 0, i);
// Menulis array ke f1.dat
for (int j = 0; j < i;
j++) {
keluaran.writeInt(list[j]);
}
}
masukan.close();
keluaran.close();
return jumlahSegmen;
}
|
Metode
menciptakan suatu array dengan ukuran maksimum pada baris 5, suatu aliran
masukan data untuk file awal pada baris 6, dan suatu aliran keluaran data untuk
suatu file temporer pada baris 8. Aliran-aliran tersangga digunakan untuk
memperbaiki kinerja .
Baris
14-17 membaca suatu segmen data dari file ke array. Baris 20 mengurutkan array.
Baris 23-25 menulis data di dalam array ke file temporer.
Jumlah
segmen dikembalikan pada baris 31.
Gambar
9.16 Segmen-segmen terurut digabungkan
secara iteratif
9.7.2
Implementasi Fase II
Pada
setiap tahap penggabungan, dua segmen terurut digabung untuk membentuk suatu
segmen baru. Ukuran segmen baru tersebut adalah dua kalinya. Jumlah segmen
tereduksi setengahnya setelah tiap tahap penggabungan dilakukan. Suatu segmen
terlalu besar untuk dibawa ke suatu array di dalam memori. Untuk
mengimplementasikan suatu langkah penggabungan, setengah dari jumlah segmen di
dalam file f1.dat disalin ke suatu
file temporer f2.dat. Kemudian
segmen pertama yang tersisa di dalam file f1.dat
digabungkan dengan segmen pertama di
dalam file f2.dat dan hasilnya
disimpan ke dalam file f3.dat,
seperti tertampil pada Gambar 9.16.
Kode9.12
menyajikan suatu metode yang menyalin setengah segmen-segmen pertama di dalam f1.dat ke f2.dat. Kode9.13 menyajikan suatu metode untuk menggabungkan
sepasang segmen-segmen di dalam f1.dat
dan f2.dat. Kode9.14 menyajikan
suatu metode yang menggabungkan dua segmen.
Kode9.12 Menyalin Setengah Segmen
Pertama
1
2
3
4
5
6
7
|
private
static void salinSetengahKeF2(int
jumlahSegmen,
int ukuranSegmen,
DataInputStream f1, DataOutputStream f2)
throws Exception
{
for (int i = 0; i < (jumlahSegmen / 2) * ukuranSegmen; i++) {
f2.writeInt(f1.readInt());
}
}
|
Kode9.13 Menggabungkan Semua Segmen
1
2
3
4
5
6
7
8
9
10
11
12
|
private
static void gabungSegmen(int jumlahSegmen,
int ukuranSegmen,
DataInputStream f1, DataInputStream f2,
DataOutputStream f3) throws Exception {
for (int i = 0; i < jumlahSegmen; i++) {
gabungDuaSegmen(ukuranSegmen, f1, f2,
f3);
}
// f1 bisa memiliki satu segmen ekstra, menyalin
ke f3
while (f1.available()
> 0) {
f3.writeInt(f1.readInt());
}
}
|
Kode9.14 Menggabungkan Dua Segmen
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
private
static void gabungDuaSegmen(int ukuranSegmen,
DataInputStream f1, DataInputStream f2,
DataOutputStream f3) throws Exception {
int intDariF1
= f1.readInt();
int intDariF2
= f2.readInt();
int f1Hitung
= 1;
int f2Hitung
= 1;
while (true) {
if (intDariF1 < intDariF2) {
f3.writeInt(intDariF1);
if
(f1.available() == 0 || f1Hitung++ >= ukuranSegmen)
{
f3.writeInt(intDariF2);
break;
}
else {
intDariF1 = f1.readInt();
}
}
else {
f3.writeInt(intDariF2);
if (f2.available() == 0 || f2Hitung++ >= ukuranSegmen)
{
f3.writeInt(intDariF1);
break;
}
else {
intDariF2 = f2.readInt();
}
}
}
while (f1.available() > 0 && f1Hitung++ < ukuranSegmen)
{
f3.writeInt(f1.readInt());
}
while (f2.available() > 0 && f2 Hitung++ < ukuranSegmen)
{
f3.writeInt(f2.readInt());
}
}
|
9.7.3
Menggabungkan Dua Fase
Kode9.15
menyajikan suatu program utuh untuk mengurutkan nilai-nilai int di dalam databesar.dat dan menyimpan data terurut di dalam fileterurut.dat.
Kode9.15 UrutFileBesar.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
|
import java.io.*;
public class UrutFileBesar {
public static final int
UKURAN_ARRAY_MAKS = 100000;
public static final int UKURAN_BUFFER
= 100000;
public static void main(String[]
args) throws Exception {
// Mengurutkan databesar.dat ke
fileterurut.dat
urut("databesar.dat",
"fileterurut.dat");
// Menampilkan 100 angka pertama di dalam
fileterurut.dat
tampilFile("fileterurut.dat");
}
/**
Mengurutkan data di dalam file sumber ke file target */
public static void urut(String filesumber, String filetarget)
throws Exception {
// Implement Phase 1: Create initial
segments
int jumlahSegmen =
inisialisasiSegmen(UKURAN_ARRAY_MAKS, filesumber, "f1.dat");
// Implement Phase 2: Merge segments
recursively
gabung(jumlahSegmen, UKURAN_ARRAY_MAKS,
"f1.dat", "f2.dat", "f3.dat",
filetarget);
}
/** Mengurutkan file awal menjadi
segmen-segmen terurut */
private static int inisialisasiSegmen
(int ukuranSegmen, String fileAwal,
String f1)
throws Exception {
int[]
list = new int[ukuranSegmen];
DataInputStream
masukan = new DataInputStream(
new BufferedInputStream(new
FileInputStream(fileAwal)));
DataOutputStream keluaran = new
DataOutputStream(
new BufferedOutputStream(new
FileOutputStream(f1)));
int
jumlahSegmen = 0;
while (masukan.available() > 0) {
jumlahSegmen++;
int i = 0;
for ( ; masukan.available() > 0
&& i < ukuranSegmen; i++) {
list[i] = masukan.readInt();
}
// Mengurutkan suatu list array[0..i-1]
java.util.Arrays.sort(list, 0, i);
// Menulis array ke f1.dat
for (int j = 0; j < i;
j++) {
keluaran.writeInt(list[j]);
}
}
masukan.close();
keluaran.close();
return jumlahSegmen;
}
private static void gabung(int
jumlahSegmen, int ukuranSegmen,
String f1, String f2, String f3, String
filetarget)
throws Exception {
if (jumlahSegmen > 1) {
gabungSatuLangkah(jumlahSegmen, ukuranSegmen, f1, f2, f3);
gabung((jumlahSegmen + 1) / 2, ukuranSegmen * 2,
f3, f1, f2, filetarget);
}
else { // Menamai-ulang f1 sebagai
file terurut akhir
File fileDiurutkan = new
File(filetarget);
if (fileDiurutkan.exists())
fileDiurutkan.delete();
new
File(f1).renameTo(fileDiurutkan);
}
}
private static void
gabungSatuLangkah(int jumlahSegmen,
int ukuranSegmen, String f1,
String f2, String f3)
throws Exception {
DataInputStream f1Masukan = new
DataInputStream(
new BufferedInputStream(new
FileInputStream(f1), UKURAN_BUFFER));
DataOutputStream f2Output = new
DataOutputStream(
new BufferedOutputStream(new
FileOutputStream(f2), UKURAN_BUFFER));
// Menyalin setengah jumlah segmen dari
f1.dat ke f2.dat
salinSetengahKeF2(jumlahSegmen, ukuranSegmen, f1Masukan, f2Output);
f2Output.close();
// Menggabungkan segmen sisa dalam f1 dengan segmen sisa dalam f2 ke
f3
DataInputStream f2Masukan = new
DataInputStream(
new BufferedInputStream(new
FileInputStream(f2), UKURAN_BUFFER));
DataOutputStream f3Keluaran = new
DataOutputStream(
new BufferedOutputStream(new
FileOutputStream(f3), UKURAN_BUFFER));
gabungSegmen(jumlahSegmen / 2,
ukuranSegmen, f1Masukan, f2Masukan, f3Keluaran);
f1Masukan.close();
f2Masukan.close();
f3Keluaran.close();
}
/** Menyalin setengah jumlah segmen pertama dari
f1.dat ke f2.dat */
private static void
salinSetengahKeF2(int jumlahSegmen,
int ukuranSegmen, DataInputStream
f1, DataOutputStream f2)
throws Exception {
for
(int i = 0; i < (jumlahSegmen / 2) * ukuranSegmen; i++) {
f2.writeInt(f1.readInt());
}
}
/** Menggabungkan semua segmen */
private static void gabungSegmen(int
jumlahSegmen,
int ukuranSegmen, DataInputStream f1,
DataInputStream f2,
DataOutputStream f3) throws
Exception {
for
(int i = 0; i < jumlahSegmen; i++) {
gabungDuaSegmen(ukuranSegmen, f1, f2, f3);
}
// f1 bisa memiliki satu segmen ekstra,
menyalin ke f3
while (f1.available() > 0) {
f3.writeInt(f1.readInt());
}
}
/** Menggabungkan dua segmen */
private static void gabungDuaSegmen(int
ukuranSegmen,
DataInputStream f1, DataInputStream f2,
DataOutputStream f3) throws
Exception {
int intDariF1 = f1.readInt();
int intDariF2 = f2.readInt();
int f1Hitung = 1;
int f2Hitung = 1;
while (true) {
if (intDariF1 < intDariF2) {
f3.writeInt(intDariF1);
if (f1.available() == 0 ||
f1Hitung++ >= ukuranSegmen) {
f3.writeInt(intDariF2);
break;
}
else {
intDariF1 = f1.readInt();
}
}
else {
f3.writeInt(intDariF2);
if (f2.available() == 0 ||
f2Hitung++ >= ukuranSegmen) {
f3.writeInt(intDariF1);
break;
}
else {
intDariF2 = f2.readInt();
}
}
}
while (f1.available() > 0
&& (f1Hitung++ < ukuranSegmen)) {
f3.writeInt(f1.readInt());
}
while (f2.available() > 0
&& (f2Hitung++ < ukuranSegmen)) {
f3.writeInt(f2.readInt());
}
}
/** Menampilkan 100 angka pertama di dalam
file tertentu */
public static void tampilFile(String
namafile) {
try {
DataInputStream masukan =
new DataInputStream(new
FileInputStream(namafile));
for (int i = 0; i <
100; i++)
System.out.print(masukan.readInt() +
" ");
masukan.close();
}
catch (IOException ex) {
ex.printStackTrace();
}
}
}
|
Keluaran
0 3 6 7
7 9 10 11 16 18 19 20 20 22 23 27 28 32 33 33 34 35 36 36 37 37 38 41 42 44 47
48 48 49 51 51 54 54 57 57 58 60 62 63 63 63 63 64 65 68 70 71 72 74 74 75 78
79 81 82 84 85 86 87 89 90 91 91 91 91 95 97 98 99 100 100 101 102 103 105 107
107 110 110 111 112 112 112 112 113 113 117 120 122 123 131 131 131 134 136
No comments:
Post a Comment