dijual hamster campbell dengan harga satuan maupun grosir...... tersedia pula jenis lainnya....
cp: 085692811714(eko)
Kamis, 21 Mei 2009
Rabu, 20 Mei 2009
buat para pencinta games the sims gw pny cheatnya.yang mau silahkan dicopy ja.....
Misc. Codes
Hit ctrl+shift+C to bring up the cheat entry window then type in one of the following codes.
| Cheat | Effect |
| setHighestAllowedLevel # | Make # the number of allowed floors you want to able to build. |
| move_objects on or off | Let's you move and delete things you couldn't before (including your Sims!) |
| boolProp TestingCheatsEnabled true | (This cheat is case sensitive) Once the cheat has been entered, hold down shift and left click on any Sim or object. You'll get new options. |
| Kaching | $1,000 |
| Motherlode | $50,000 |
| MaxMotives | Sets all needs for all playable sims on the lot to full. |
| MotiveDecay on/off | Turns natural need decay on or off. |
| LockAspiration on/off | Freezes Aspiration point decay for all sims on the lot. |
| AspirationPoints # | Permits for more expensive aspiration reward objects. |
| RoofSlopeAngle (15-75) | In build mode, it adjusts the slope angle on all roofs on a lot. |
| ShowHeadlines on/off | Makes invisible thought balloons. Useful for movie making. |
| AspirationLevel (0-5) | 0 puts them at the lowest, 5 in the platinum level. |
| AgeSimsCheat on/off | Adds "Set Age" to the interaction menu. Any sim you click on can be set to any age group. |
| UnlockCareerRewards | Allows access to all career rewards. |
| Aging off/on | Turns aging off or on. Every sim living on the lot is affected. |
| familyfunds (insert family surname) # | This code can be used to increase the beginning funds of the family named to what you want |
| boolprop constrainFloorElevation false | Allows you to change elevation of floor tiles. |
| boolprop displayNeighborhoodRoadsWithModel (True/False) | Set to false to remove bridges from neighborhood |
| clear | Clears all cheat codes on the screen, but codes are still in effect. |
| exit | closes cheat window |
| boolprop constrainFloorElevation true | Disables the ability to change elevation of floor tiles. |
| expand | expands or contracts cheat window |
| vsync (on/off) | increases game performance but lowers graphics |
| boolprop ShowLotPackageFilename (True/False) | In neighborhood, shows filename of house when lot is highlighted |
| StretchSkeleton | makes your sims larger or smaller |
| slowmotion | Puts the game in slow motion. Enter any number that 0 through 8 (0=fastest and 8=slowest) |
| boolprop lotTerrainLighting (True/False) | Set to false and lots will not light up when highlighted in neighborhood |
| boolprop locktiles (True/False) | Set to false to place floor tiles outside lot |
| boolprop lotTerrainPaints (True/False) | Set to false to remove floorpainting on lot |
| boolprop displayNeighborhoodProps (True/False) | Set to false to remove props like rocks and towers from neighborhood |
| boolprop objectShadows (True/False) | Set to false to remove removes shadows on objects outside house |
| boolprop lotWater (True/False) | Set to false to remove removes water (ponds) from lots |
| boolprop displayNeighborhoodRoads (True/False) | Set to false to remove roads from neighborhood |
| boolProp guob (True/False) | Set to false to remove shadows on objects inside house |
| boolprop displayNeighborhoodWater (True/False) | Set to false to remove water from neighborhood |
| boolprop displayLotImposters (True/False) | Set to false to removes house graphics from neighborhood |
| boolprop displayNeighborhoodFlora (True/False) | Set to false to removes trees/plants from neighborhood |
| boolprop displayLookAtBoxes (True/False) | Set to true and blocks appear on Sims faces and on parts where Sims look at |
| boolprop carsCompact (True/False) | Set to true and cars will have more detail in neighborhood |
| boolprop renderSelectedSimLevel (True/False) | Set to true and walls will no longer cut away from selected Sim |
| boolprop allObjectLightsOn (True/False) | Set to true to light up objects continuously instead of only when used |
| boolProp displayPaths (True/False) | Set to true to see the path where the selected Sim walks to |
| boolprop lotInfoAdvancedMode (True/False) | Set to true to show lot information |
| boolprop lotInfoAdvancedMode (True/False) | boolProp simShadows (True/False) |
| aging on | turn on aging |
| faceBlendLimits (on/off) | turns off facial bounding limitations. It prevents the normal corrections the game will make for two parents with very different facial structures. |
| intProp maxNumOfVisitingSims # | You can invite more people to your parties. |
| boolProp snapObjectsToGrid true/false | You can place objects outside the grid. |
| social_debug | You can tell what social reaction will happen before you do it |
| letterBox # | Adds a letterbox effect to the view. (# = 0.0 to 0.4) (require postprocessing on) |
| vignette # # # | Blurry bits at the edge of the screen. (# = 0.0 to 1.0) (require postprocessing on) |
| filmGrain # | Makes the screen grainy. (# = 0.0 to 1.0) (require postprocessing on) |
| bloom rgb # | Sitcom flashback blur effect (# = 0.0 to 1.0) (require postprocessing on) |
| boolProp enablePostProcessing false | Turns Postprocessing off. |
| boolProp enablePostProcessing true | Turns Postprocessing on. |
| deleteAllCharacters | At neighborhood view only, removes every Sim from the neighborhood. |
| TerrainType (desert/temperate) | Only for use in neighborhood view, toggles between the two terrain types. |
| help | brings up a list of all cheats in the game. |
100,000 money
bring up the cheat menu then press and hold shift, the put in "WARIGANOSASH" then press enter
(Cs: Bon5aiM PH Aimbot)
| The Sims 2: Open for Business |
Cheat: 50,000 Simoleans The Sims 2: Double Deluxe Cheat: 50,000 Simoleans
Selama bermain, tekan CTRL, Shift dan C Untuk membuka cheat console. Kemudian, masukkan "motherlode" (minus the quotes) untuk menerima 50,000 Simoleans secara otomatis.
binary search
1. Pendahuluan
Dalam pemrosesan suatu data tidak lepas dari
struktur data berupa tabel (array). Tabel adalah
suatu tipe yang mengacu pada sebuah atau
sekumpulan elemen dan dapat diakses melalui
indeks. Elemen dari tabel dapat diakses langsung jika dan hanya jika indeks terdefinisi (ditentukan harganya dan sesuai dengan domain yang didefinisikan untuk indeks tersebut). Struktur data ini dipakai untuk merepresentasikan sekumpulan data yang bertipe sama (misal :integer, karakter) dan disimpan dengan urutan yang sesuai dengan definisi indeks secara kontigu dalam memori komputer. Untuk makalah ini akan dibahas tabel dengan sekumpulan elemen yang bertipe integer. Pemrosesan terhadap struktur data tabel dapat dilakukan secara linear (sequential) ataupun rekursif. Pemrosesan terurut terhadap suatu tabel adalah pemrosesan terurut tanpa mark. Akses terhadap elemen-elemen yang ada dalam tabel dilakukan dengan memanfaatkan keterurutan indeks. Elemen tabel dengan indeks terkecil adalah elemen pertama dari tabel. Elemen selanjutnya dapat diakses melalui suksesor indeks. Kondisi berhenti adalah jika indeks sudah mencapai harga indeks terbesar yang telah terdefinisi. Struktur data tabel tidak mungkin kosong. Jika kita mendefinisikan suatu tabel, maka minimal mengandung sebuah elemen. Skema umum pemrosesan terhadap tabel integer adalah (ditulis dalam notasi algoritmik) sebagai berikut. Skema pemrosesan tersebut hanyalah skema umum dari pemrosesan terhadap sebuah tabel. Tidak menutup kemungkinan suatu proses terhadap tabel dapat mempunyai skema yang berbeda dari skema umum. Pemrosesan yang paling sering dilakukan terhadap suatu tabel bertipe integer adalah pencarian nilai (searching) dan pengurutan nilai (sorting). Untuk pencarian dan pengurutan nilai terdapat berbagai macam jenis algoritma yang dapat digunakan dengan tingkat keefektifan yang berbeda. Untuk pencarian nilai, ada beberapa jenis metode yaitu pencarian secara linear (sequential search) dan pencarian biner (binary search) untuk table yang telah terurut nilainya(sorted tabel). Pencarian secara linear mempunyai dua jenis metode yaitu dengan boolean dan tanpa boolean. Untuk pengurutan nilai ada beberapa jenis algoritma yaitu count sort (pengurutan dengan mencacah), selection sort (pengurutan dengan menyeleksi), insertion sort (pengurutan dengan penyisipan), quick sort (pengurutan cepat), merge sort (pengurutan dengan penggabungan), heap sort (pengurutan dengan tumpukan), shell sort (pengurutan cangkang), dan bubble sort (pengurutangelembung). Masing-masing metode mempunyai kelebihan dan kekurangan, dari panjang pendeknya kode, kompleksitas kode, waktu pemrosesan, memori yang digunakan, kompatibilitas, dan lain sebagainya. Namun keefektifan suat u algoritma dapat diukur atau dihitung dengan menggunakan teori kompleksitas algoritma yang dipelajari pada
mata kuliah matematika diskrit. Algoritma yang
mangkus adalah algoritma yang dapat meminimumkan kebutuhan waktu dan ruang.
Namun kebutuhan waktu dan ruang dari suatu
algoritma bergantung pada jumlah data yang
diproses dan algoritma yang digunakan. Karena
kompleksitas ruang terkait dengan struktur data
yang digunakan dan di luar bahasan mata kuliah
IF2153 Matematika Diskrit, maka kompleksitas
ruang tidak akan dibahas pada makalah ini.
Makalah ini hanya akan membahas dan
menganalisa kompleksitas waktu untuk masingmasing jenis algoritma.
Kompleksitas waktu untuk algoritma-algoritma
yang dibahas akan dinyatakan dengan notasi O
besar (Big-O notation). Definisi dari notasi O
besar adalah, jika sebuah algoritma mempunyai
waktu asimptotik O(f(n)), maka jika n dibuat
semakin besar, waktu yang dibutuhkan tidak
KAMUS UMUM PEMROSESAN TABEL
INTEGER
constant Nmin: integer = 1
constant Nmax: integer = 100
{Nmin dan Nmax : batas bawah dan
batas atas yang ditentukan}
type Infotype: integer
{suatu tipe terdefinisi, yaitu
integer}
T: array [Nmin..Nmax] of infotype
{tabel T yang didefinisikan
dengan indeks dari Nmin sampai
Nmax dengan elemen bertipe
infotype}
procedure Inisialisasi
{persiapan yang harus dilakukan
sebelum pemrosesan}
procedure Proses (input x:int)
{proses terhadap “currentelement”
pada tabel T}
procedure Terminasi
{penutuoan yang harus dilakukan
setelah pemrosesan selesai}
SKEMA PEMROSESAN TABEL T UNTUK
INDEKS [Nmin..Nmax]
{traversal tabel T untuk indeks
bernilai Nmin..Nmax}
Skema:
Inisialisasi
i ← Nmin
iterate
Proses (Ti)
stop : i = Nmax {EOP}
i ← i + 1 {Next element}
Terminasi
akan pernah melebihi suatu konstanta C dikali
dengan f(n). Jadi f(n) adalah adalah batas atas
(upper bound) dari T(n) untuk n yang besar.
O(n) dihitung berdasarkan banyaknya jumlah
operasi perbandingan yang dilakukan dalam
algoritma tersebut.
2. Pencarian Nilai (Searching)
2.1 Pencarian Secara Linear (Sequential
Search)
Algoritma pencarian secara linear adalah
algoritma untuk mencari sebuah nilai pada tabel
sembarang dengan cara melakukan pass atau
traversal dari awal sampa akhir tabel. Ada dua
macam cara pencarian pada tabel. Algoritma ini
mempunyai dua jenis metode yaitu dengan
boolean dan tanpa boolean.
Implementasi algoritma pencarian secara linear
tanpa boolean dalam bahasa C adalah sebagai
berikut.
void SeqSearch1 (int T[], int Nmax,
int value, int *idx)
/*I.S. T tabel dgn elemen bertipe*/
/* integer, tidak kosong*/
/*F.S. idx terdefinisi sebagai index
tempat value ditemukan, idx = 0 jika
tidak ketemu*/
/*Proses : melakukan pencarian harga
value dalam table T*/
{
/*kamus lokal*/
int i;
/*Algoritma*/
i = 1;
while ((i
value))
{
i = i + 1;
}
if (T[i]==value)
{
*idx = i;
}
else
{
*idx = 0;
}
}
Algoritma di atas melakukan pengulangan
sampai i sama dengan Nmax (ukuran tabel) atau
harga value dalam tabel sudah ditemukan.
Kemudian harga i di-assign ke dalam variabel
idx. Elemen terakhir diperiksa secara khusus.
Sedangkan implementasi algoritma pencarian
secara linear dengan boolean dalam bahasa C
adalah sebagai berikut.
void SeqSearch2 (int T[],int Nmax,
int value, int *idx)
/*I.S. T tabel dgn elemen bertipe*/
/* integer, tidak kosong*/
/*F.S. idx terdefinisi sebagai index
tempat value ditemukan, idx = 0 jika
tidak ketemu*/
/*Proses : melakukan pencarian harga
value dalam table T*/
{
/*kamus lokal*/
int i;
boolean found;
/*algoritma*/
i = 1;
found = false;
while ((i<=Nmax) && (!found))
{
if (T[i] == value)
{
found = true;
}
else
{
i = i + 1;
}
}
if (found)
{
*idx = i;
}
else
{
*idx = 0;
}
)
Algoritma pencairan secara linear melakukan pengulangan sebanyak 1 kali untuk kasus terbaik (value sama dengan elemen pertama dalam tabel) dan Nmax kali untuk kasus terburuk. Sehingga algoritma ini mempunyai kompleksitas algoritma O(n).
2.2 Pencarian Biner (Binary Search)
Algoritma pencarian biner adalah algoritma
untuk mencari sebuah nilai pada tabel teurut
dengan cara menghilangkan setengah data pada setiap langkah. Algoritma ini mencari nilai yangdicari dengan tiga langkah yaitu :
• Mencari nilai tengah dari tabel (median)
• Melakukan perbandingan nilai tengah
dengan nilai yang dicari untuk menentukan
apakah nilai yang dicari ada pada sebelum
atau setelah nilai tengah
• Mencari setengah sisanya dengan cara yang
sama.
Implementasi algoritma pencarian biner dalam
bahasa C adalah sebagai berikut.
void BinSearch (int T[],int Nmax, int
value, int* idx)
/*I.S. T tabel dgn elemen bertipe*/
/* integer, sembarang*/
/*F.S. idx terdefinisi sebagai index
tempat value ditemukan, idx = 0 jika
tidak ketemu*/
/*melakukan pencarian thd harga value
di dalam table T*/
{
/*kamus lokal*/
int i,j,mid;
boolean found;$
/*algoritma*/
found = false;
i = 1;
j = Nmax;
while ((!found) && (i<=j))
{
mid = (i+j) div 2;
if (T[mid] == value)
{
found = true;
}
else
{
if (T[mid]
{
i = mid + 1;
}
else
{
j = mid – 1;
}
}
}
if (found)
{
*idx = mid;
}
else
{
*idx = 0;
Algoritma akan berakhir karena pada setiap pengulangan, jangkauan indeks i dikurang j akan selalu mengecil, dan akhirnya pasti akan menjadi negatif. Algoritma pencairan biner melakukan pengulangan sebanyak 1 kali untuk kasus terbaik (value sama dengan elemen yang berada di tengah tabel) dan 2log Nmax untuk kasus terburuk. Sehingga algoritma ini mempunyai kompleksitas algoritma O(log n). Dan tentu saja algoritma ini lebih cepat dibandingkan dengan pencarian secara linier.
3. Pengurutan Nilai (Sorting)
3.1. Pengurutan Gelembung (Bubble Sort)
Pengurutan gelembung adalah algoritma
pengurutan yang paling tua dan sederhana untuk diimplementasikan. Algoritma ini juga cukup mudah untuk dimengerti. Algoritma pengurutan gelembung dalam implementasi bahasa C adalah sebagai berikut.
void BubbleSort(int *T, int Nmax)
/*I.S. T tabel dgn elemen bertipe*/
/* integer, T tidak kosong*/
/*F.S. T terurut menaik*/
/*Proses : melakukan pengurutan*/
/* dengan metode bubble sort*/
{
/*kamus lokal*/
int i, j, temp;
/*algoritma*/
for (i =(Nmax - 1); i >= 0; i--)
{
for (j = 1; j <= i; j++)
{
if (*T[j-1] > *T[j])
{
temp = *T[j-1];
*T[j-1] = *T[j];
*T[j] = temp;
}
}
}
}
Pengurutan gelembung ini menggunakan dua
buah kalang (loop) for. Kalang yang pertama
melakukan travesal dari indeks terkecil sedangkan kalang yang kedua melakukan
traversal dari indeks terbesar. Kalang yang satu
berada di dalam kalang yang lain dan panjang
masing-masing tergantung pada banyaknya
elemen. Siklus yang pertama melakukan n-1
perbandingan, siklus yang kedua melakukan n-2
perbandingan, siklus yang ketiga melakukan n 3,
dan seterusnya. Sehingga total semua perbandingan
(n-1) + (n-2) + .. +1
yang dapat disederhanakan menjadi n(n-1)/2.
Algoritma ini bekerja dengan cara membandingkan nilai tiap elemen dalam tabel
dengan elemen setelahnya, dan menukar nilainya jika sesuai dengan kondisi yang diperlukan. Proses ini akan terus berulang hingga seluruh elemen dalam tabel telah diproses dan elemen dalam tabel telah terurut.
Algoritma pengurutan gelembung ini adalah
algoritma yang paling lamban dan tidak mangkus dibandingkan dengan algoritma pengurutan yang lain dalam penggunaan secara umum. Dalam kasus terbaik (yaitu list sudah terurut), kompleksitas algoritma pengurutan gelembung adalah O(n). Namun, untuk kasus umum,kompleksitas algoritma pengurutan gelembung adalah O(n2).
Grafik di atas menggambarkan kompleksitas
algoritma dari pengurutan gelembung.
3.2. Pengurutan Dengan Menyeleksi (Selection Sort)
Algoritma pengurutan dengan seleksi dalam
implementasi bahasa C adalah sebagai berikut.
void SelectionSort(int *T, int Nmax)
/*I.S. T tabel dgn elemen bertipe*/
/* integer, sembarang*/
/*F.S. T terurut menaik*/
/*Proses : melakukan pengurutan*/
/* dengan metode selection sort*/
{
/*kamus lokal*/
int i, j;
int min, temp;
/*algoritma*/
for (i = 0; i <>
{
min = i;
for (j = i+1; j <>
{
if (*T[j] < *T[min])
min = j;
}
temp = *T[i];
*T[i] = *T[min];
*T[min] = temp;
Sama seperti algoritma pengurutan gelembung,
algoritma ini mempunyai dua buah kalang, satu
kalang di dalam kalang yang lainnya. Banyaknya
perbandingan yang harus dilakukan untuk siklus
pertama adalah n, perbandingan yang harus
dilakukan untuk siklus yang kedua n-1, dan
seterusnya. Sehingga jumlah keseluruhan
perbandingan adalah n(n+1)/2-1 perbandingan.
Pengurutan seleksi ini bekerja dengan cara
menyeleksi nilai yang paling kecil yang ada pada
tabel. Kemudian nilai tersebut ditukar dengan
nilai yang paling awal yang belum ditukar
nilainya. Algoritma ini memang mudah untuk
diimplementasikan, namun tidak efisien untuk
tabel berukuran besar (menyimpan banyak nilai). Algoritma pengurutan seleksi mempunyai
kompleksitas algoritma O(n2), sama seperti
algoritma pengurutan gelembung. Namun jika
kedua algoritma tersebut dijalankan untuk tabel
dengan data yang sama, algoritma pengurutan
seleksi 60% lebih cepat dibandingkan dengan
algoritma pengurutan gelembung. Jika ingin menggunakan algoritma pengurutan seleksi karena beberapa alasan tertentu, hindari pengurutan nilai dengan data pada tabel lebih
besar dari 1000 buah, dan hindari mengurutkan
tabel lebih dari beberapa ratus kali.
Grafik di atas menggambarkan kompleksitas
algoritma dari pengurutan seleksi.
3.3. Pengurutan Dengan Penyisipan (Insertion Sort)
Pengurutan dengan penyisipan bekerja dengan
cara menyisipkan masing-masing nilai di tempat
yang sesuai (di antara elemen yang lebih kecil
atau sama dengan nilai tersebut dengan elemen
yang lebih besar atau sama dengan nilai
tersebut). Algoritma ini relatif sederhana dan
mudah untuk diimplementasikan.
void InsertionSort(int *T, int Nmax)
/*I.S. T tabel dgn elemen bertipe*/
/* integer, T tidak kosong*/
/*F.S. T terurut menaik*/
/*Proses : melakukan pengurutan*/
/* dengan metode insertion sort*/
{
/*kamus lokal*/
int i, j, index;
/*algoritma*/
for (i=1; i <>
{
index = *T[i];
j = i;
while ((j > 0) && (*T[j-1] >
index))
{
*T[j] = *T[j-1];
j = j - 1;
}
*T[j] = index
}
}
Untuk kasus terbaik algoritma ini berjalan 1 kali,
yaitu jika elemen dalam tabel telah terurut.
Kalang (loop) while tidak pernah dijalankan.
Untuk kasus terburuk algoritma ini berjalan
Nmax kali. Sehingga, seperti pengurutan
gelembung, pengurutan dengan penyisipan
mempunyai kompleksitas algoritma O(n2).
Walaupun mempunyai kompleksitas algoritma
yang sama, namun jika dijalankan dengan data
input yang sama, algritma pengurutan dengan
penyisipan dua kali lebih cepat dan efisien
dibandingkan dengan pengurutan gelembung.
Namun, algoritma ini tetap kurang efisien untuk
tabel berukuran besar (menyimpan banyak nilai).
Grafik di atas menggambarkan kompleksitas
algoritma dari pengurutan seleksi.
Algoritma pengurutan dengan penyisipan ini
kurang lebih dua kali lebih cepat dibandingkan
dengan algoritma pengurutan gelembung dan
hampir 40% lebih cepat dibandingkan algoritma
pengurutan dengan seleksi, walaupun algoritma
ini masih lebih lambat dibandingkan dengan
algoritma shell sort (akan dibahas kemudian).
3.4. Pengurutan Cangkang (Shell Sort)
Shell sort adalah algoritma dengan kompleksitas
algoritma O(n2) dan yang paling efisien
dibanding algoritma-algoritma lain dengan
kompleksitas algoritma yang sama. Algoritma
shell sort lima kali lebih cepat dibandingkan
algoritma pengurutan gelembung dan dua kali
lebih cepat dibandingkan algoritma pengurutan
dengan penyisipan. Dan tentu saja shell sort juga merupakan algoritma yg paling yang paling
kompleks dan sulit dipahami.
void ShellSort(int *T, int Nmax)
/*I.S. T tabel dgn elemen bertipe*/
/* integer, T tidak kosong*/
/*F.S. T terurut menaik*/
/*Proses : melakukan pengurutan*/
/* dengan metode shell sort*/
{
/*kamus lokal*/
int i, j, increment, temp;
/*algoritma*/
increment = 3;
while (increment > 0)
{
for (i=0; i <>
{
j = i;
temp = *T[i];
while ((j >= increment) &&
(*T[j-increment] > temp))
{
*T[j] = *T[j - increment];
j = j - increment;
}
*T[j] = temp;
}
if (increment/2 != 0)
increment = increment/2;
else if (increment == 1)
increment = 0;
else
increment = 1;
}
}
Algoritma shell sort melakukan pass atau
traversal berkali-kali, dan setiap kali pass
mengurutkan sejumlah nilai yang sama dengan
ukuran set menggunakan insertion sort. Ukuran
dari set yang harus diurutkan semakin membesar setiap kali melakukan pass pada tabel, sampai set tersebut mencakup seluruh elemen tabel. Ketika ukuran dari set semakin membesar, sejumlah nilai yang harus diurutkan semakin mengecil. Ini menyebabkan insertion sort yang dijalankan mengalami kasus terbaik dengan kompleksitas algoritma mendekati O(n). Ukuran dari set yang digunakan untuk setiap kali iterasi (iteration) mempunyai efek besar terhadap efisiensi pengurutan.
Tetapi, walaupun tidak se-efisien algoritma
merge sort, heap sort, atau quick sort (akan
dibahas kemudian), algoritma shell sort adalah
algoritma yang relatif sederhana. Hal ini
menjadikan algoritma shell sort adalah pilihan
yang baik dan efisien untuk mengurutkan nilai
dalam suatu tabel berukuran sedang
(mengandung 500-5000 elemen).
Grafik di atas menggambarkan kompleksitas
algoritma dari shell sort.
3.5. Pengurutan dengan Tumpukan (Heap
Sort)
Algoritma heap sort ini lebih cepat dibandingkan
dengan keempat algoritma lain yang telah
dibahas. Tetapi algoritma ini adalah algoritma
yang paling lambat dibanding algoritmaalgoritma
pengurutan lain dengan kompleksitas
algoritma yang sama, yaitu quick sort dan merge
sort (yang akan dibahas kemudian). Tidak seperti quick sort dan merge sort, heap sort tidak rekursif dan tidak memerlukan terlalu banyak tabel temporer untuk menjalankan algoritma. Algoritma dasar heap sort dimulai dengan membangun tumpukan data set, kemudian memindahkan elemen dengan nilai yang paling besar dan menempatkannya di posisi paling akhir dari tabel baru yang akan berisi elemen yang teurut. Setelah memindahkan elemen dengan nilai yang paling besar, algoritma ini merekonstruksi tumpukan dari data yang tersisa dan memindahkan kembali nilai yang paling besar dari tumpukan, dan menempatkannya di tempat kedua sebelum paling akhir dari tabel. Begitu seterusnya sampai tidak ada lagi elemen yang tersisa dalam tumpukan dan tabel yang baru telah penuh. Dalam implementasinya diperlukan dua tabel, satu berisi tumpukan dan satu berisi elemen yang telah terurut. Namun, dalam beberapa kasus memerlukan penghematan ruang atau memori. Kita dapat memodifikasi algoritma dasar heap sort dengan menggunakan tabel yang sama untuk menyimpan tumpukan dan elemen yang telah diurutkan. Ketika sebuah elemen dipindahkan dari tumpukan, algoritma menyediakan ruang atau space di akhir tabel untuk diisi oleh elemen tersebut. Di bawah ini adalah algoritma untuk heap sort yang dilakukan pada satu tabel.
void HeapSort(int *T, int Nmax)
/*I.S. T tabel dgn elemen bertipe*/
/* integer, T tidak kosong*/
/*F.S. T terurut menaik*/
/*Proses : melakukan pengurutan*/
/* dengan metode heap sort*/
{
/*kamus lokal*/
int i, temp;
/*algoritma*/
for (i = (Nmax / 2)-1; i >= 0; i--)
siftDown(T, i, Nmax);
for (i = Nmax-1; i >= 1; i--)
{
temp = *T[0];
*T[0] = *T[i];
*T[i] = temp;
siftDown(T, 0, i-1);
}
}
void siftDown(int *T, int root, int
bottom)
{
/*kamus lokal*/
int done, maxChild, temp;
/*algoritma*/
done = 0;
while ((root*2 <= bottom) &&
(!done))
{
if (root*2 == bottom)
maxChild = root * 2;
else if (*T[root * 2] > *T[root
* 2 + 1])
maxChild = root * 2;
else
maxChild = root * 2 + 1;
if (*T[root] <* T[maxChild])
{
temp = *T[root];
*T[root] = *T[maxChild];
*T[maxChild] = temp;
root = maxChild;
}
else
done = 1;
}
}
Algoritma heap sort mempunyai kompleksitas
algoritma O(n log n). Keuntungan dari algoritma
heap sort ini adalah tidak rekursif (yang berarti
tidak memerlukan memori yang besar) dan dapat dilakukan langsung pada satu tabel. Dengan begitu, algoritma ini adalah algoritma yang tepat untuk mengurutkan data yang sangat banyak (sampai jutaan data). Namun, algoritma ini masih lebih lambat dibandingkan algoritma merge sort dan quick sort walaupun dengan
kompleksitas algoritma yang sama.
Grafik di atas menggambarkan kompleksitas
algoritma dari heap sort.
3.6. Pengurutan Dengan Penggabungan
(Merge Sort)
Algoritma merge sort membagi (split) tabel
menjadi dua tabel sama besar. Masing-masing
tabel diurutkan secara rekursif, dan kemudian
digabungkan kembali untuk membentuk tabel
yang terurut. Implementasi dasar dari algoritma merge sort memakai tiga buah tabel, dua untuk menyimpan elemen dari tabel yang telah dibagi dua dan satu untuk menyimpan elemen yang telah teurut. Namun algoritma ini dapat juga dilakukan langsung pada dua tabel, sehingga menghemat ruang atau memori yang dibutuhkan. Di bawah ini adalah algoritma untuk merge sort yang dilakukan pada dua tabel.
void mergeSort(int *T, int *temp, int
Nmax)
/*I.S. T tabel dgn elemen bertipe*/
/* integer, T tidak kosong*/
/*F.S. T terurut menaik*/
/*Proses : melakukan pengurutan*/
/* dengan metode merge sort*/
{
m_sort(T, temp, 0, Nmax - 1);
}
void m_sort(int *T, int *temp, int
*left, int *right)
{
int mid;
if (*right > *left)
{
mid = (*right + *left) / 2;
m_sort(T, temp, left, mid);
m_sort(T, temp, mid+1, right);
merge(T, temp, left, mid+1,
right);
}
}
void merge(int *T, int *temp, int
left, int mid, int right)
{
int i, left_end, num_elements,
tmp_pos;
left_end = mid - 1;
tmp_pos = left;
num_elements = right - left + 1;
while ((left <= left_end) && (mid <=
right))
{
if (*T[left] <= *T[mid])
{
*temp[tmp_pos] = *T[left];
tmp_pos = tmp_pos + 1;
left = left +1;
}
else
{
*temp[tmp_pos] =* T[mid];
tmp_pos = tmp_pos + 1;
mid = mid + 1;
}
}
while (left <= left_end)
{
*temp[tmp_pos] = *T[left];
left = left + 1;
tmp_pos = tmp_pos + 1;
}
while (mid <= right)
{
*temp[tmp_pos] = *T[mid];
mid = mid + 1;
tmp_pos = tmp_pos + 1;
}
for (i=0; i <= num_elements; i++)
{
*T[right] = *temp[right];
right = right - 1;
}
}
Karena algoritma merge sort adalah algoritma
yang dijalankan secara rekursif maka T(n) dari
algoritma ini adalah
Sehingga, algoritma merge sort memiliki
kompleksitas algoritma O(n log n).
Algoritma merge sort ini sebenernya lebih cepat
dibandingkan heap sort untuk tabel yang lebih
besar. Namun, algoritma ini membutuhkan
setidakny ruang atau emori dua kali lebih besar
karena dilakukan secara rekursif dan memakai
dua tabel. Hal ini menyebabkan algoritma ini
kurang banyak dipakai.
Grafik di atas menggambarkan kompleksitas
algoritma dari merge sort.
3.7. Pengurutan Cepat (Quick Sort)
Algoritma quick sort sangat sederhana dalam
teori, tetapi sangat sulit untuk diterjemahkan ke
dalam sebuah code karena pengurutan dilakukan dalam sebuah list dan diproses secara rekursif. Algoritma ini terdisi dari empat langkah (yang mana menyerupai merge sort) yaitu :
• Memilih sebuah elemen untuk dijadikan
poros atau pivot point (biasanya elemen
paling kiri dari tabel).
• Membagi tabel menjadi dua bagian, satu
dengan elemen yang lebih besar dari poros,
dan satu lagi untuk elemen yang lebih kecil
dari poros.
• Mengulang algoritma untuk kedua buah
tabel secara rekursif.
Tingkat keefektifan dari algoritma ini dangat
bergantung pada elemen yang dipilih menjadi
poros. Kasus terburuk terjadi ketika tabel sudah
terurut dan elemen terkecil di sebelah kiri
menjadi poros. Kasus ini mempunyai
kompleksitas algoritma O(n2). Maka dari itu
sangat disarankan untuk memilih poros bukan
dari elemen paling kiri dari tabel, tetapi dipilih
secara random. Selama poros dipilih secara
random, algoritma quick sort mempunyai
kompleksitas algoritma sebesar O(n log n).
void quickSort(int T[], int Nmax)
/*I.S. T tabel dgn elemen bertipe*/
/* integer, sembarang*/
/*F.S. T terurut menaik*/
/*Proses : melakukan pengurutan*/
/* dengan metode quick sort*/
{
q_sort(T, 0, Nmax - 1);
}
void q_sort(int T[], int left, int
right)
{
int pivot, l_hold, r_hold;
l_hold = left;
r_hold = right;
pivot = T[left];
while (left <>
{
while ((T[right] >= pivot) &&
(left <>
right--;
if (left != right)
{
T[left] = T[right];
left++;
}
while ((T[left] <= pivot) && (left
<>
left++;
if (left != right)
{
T[right] = T[left];
right--;
}
}
T[left] = pivot;
pivot = left;
left = l_hold;
right = r_hold;
if (left <>
q_sort(T, left, pivot-1);
if (right > pivot)
q_sort(T, pivot+1, right);
Algoritma quick sort mengurutkan dengan
sangat cepat, namun algoritma ini sangat
komplex dan diproses secara rekursif. Sanat
memungkinkan untuk menulis algoritma yang
lebih cepat untuk beberapa kasus khusus, namun untuk kasus umum, sampai saat ini tidak ada yang lebih cepat dibandingkan algoritma quick sort.
Walaupun begitu algoritma quick sort tidak
selalu merupakan pilihan yang terbaik. Seperti
yang telah disebutkan sebelumnya, algoritma ini
dilakukan secara rekursif yang berarti jika
dilakukan untuk tabel yang berukuran sangat
besar, walaupun cepat, dapat menghabiskan
memori yang besar pula. Selain itu, algoritma ini
adalah algoritma yang terlalu komplex untuk
mengurutkan tabel yang berukuran kecil (hanya
puluhan elemen misalnya). Selain itu algoritma
quick sort mempunyai tingkat efisiensi yang
buruk ketika dioperasikan pada tabel yang
hampir terurut atau pada tabel yang terurut
menurun.
Grafik di atas menggambarkan kompleksitas
algoritma dari quick sort.
3.8. Pengurutan dengan Mencacah (Count
Sort)
Pengurutan dengan mencacah adalah pengurutan yang paling sederhana. Jika diketahui bahwa tabel yang akan diurutkan nilainya mempunyai daerah atau range tertentu dan merupakan bilangan bulat, misalnya [ElMin..ElMax] maka cara paling sederhana untuk mengurut adalah :
• Sediakan tabel TabCount [ElMin..Elmax]
yang diinisialisasi dengan nol, dan pada
akhir proses TabCount[i] berisi banyaknya
elemen pada tabel asal T yang berharga i;
• Tabel asal T dibentuk kembali dengan
menuliskan harga-harga yang ada dengan
jumlah sesuai dengan yang ada pada
TabCount.
Implementasi algoritma pengurutan dengan
mencacah dalam bahasa C adalah sebagai
berikut.
void CountSort (int *T, int Nmax, int
ElMin, int Elmax )
/*I.S. T tabel dgn elemen bertipe*/
/* integer, sembarang*/
/*F.S. T terurut menaik*/
/*Proses : melakukan pengurutan*/
/* dengan metode count sort*/
{
/*kamus lokal*/
int TabCount[];
int i,k;
/*algoritma*/
/*inisialisasi TabCount*/
for (i=ElMin; i<=ElMax; i++)
/*loop1*/
{
TabCount[i] = 0;
}
for (i=1; i<=Nmax;i++)
/*loop2*/
{
TabCount[T[i]] = TabCount[T[i]] +
1;
}
k = 0;
for (i=ElMin;i<=ElMax;i++)
/*loop3*/
{
while (TabCount[i]!=0)
/*loop4*/
{
k++;
T[k] = I;
}
}
}
Total waktu yang dibutuhkan untuk menjalankan
algoritma ini bergantung pada k yaitu range
ElMin dan ElMax (k = ElMax - ElMin). Jika
pengurutan dengan mencacah dijalankan pada
elemen integer berukuran 32 bit, maka kasus
terbaik terjadi jika tabel hanya berisi satu jenis
elemen (ElMin sama dengan ElMax). Kasus
terburk terjadi ketika ElMin bernilai -232 dan
ElMax bernilai 232.
Loop1 dan loop3 mempunyai O(k). Loop2 dan
loop4 mempunya O(n). Total waktu yang
dibutuhkan adalah O(n+k). Jika kita asumsikan
bahwa k = O(n), maka kompleksitas algoritma
dari algoritma count sort adalah O(n). Namun,
yang harus diperhitungkan di sini adalah range
dari elemen yang ada pada tabel.
4. Kesimpulan
Pencarian nilai (searching) dan pengurutan nilai
(sorting) adalah operasi yang paling sering
dilakukan pada sebuah tabel. Jenis algoritma
untk pencarian dan pengurutan nilai sangat
banyak dengan tingkat keefektifan yang berbedabeda
untuk masing-masing kasus.
Untuk pencarian nilai pada tabel yang telah
terurut nilainya lebih baik menggunakan
algoritma pencarian biner (binary search) karena
algoritma ini lebih efektif. Tetapi jika ingin
melakukan pencarian nilai pada tabel sembarang,
kita harus menggunakan algoritma pencarian
nilai secara linier (sequential search). Untuk
penggunaan boolean pada algoritma ini dapat
disesuaikan dengan kasus yang ditangani.
Untuk melakukan pengurutan nilai, algoritma
yang paling sederhana dan paling mudah
dimengerti adalah algoritma count sort. Namun
algoritma ini tidak efektif untuk digunakan pada
tabel dengan range yang besar.
Algoritma-algoritma pengurutan nilai lainnya,
dapat dibagi menjadi dua kelompok. Algoritma
berkompleksitas O(n2), yaitu pengurutan
gelembung (bubble sort), pengurutan dengan
penyisipan (insertion sort), pengurutan dengan
menyeleksi (selection sort), dan pengurutan
cangkang (shell sort). Algoritma
berkompleksitas O(n log n), yaitu pengurutan
dengan penggabungan (heap sort), pengurutan
dengan penggabungan (merge sort), dan
pengurutan cepat (quick sort).
Grafik di atas menggambarkan perbandingan
kompleksitas algoritma dari algoritma-algoritma
O(n2). Algoritma ini cocok digunakan untuk
tabel dengan ukuran yang tidak terlalu besar
(tidak lebih dari sekitar 10.000 elemen), tidak
terlalu dibutuhkan kecepatan dalam pengurutan
nilai, dan ketika dibutuhkan algoritma
pengurutan yang sederhana.
Grafik di atas menggambarkan perbandingan
kompleksitas algoritma dari algoritma-algoritma
O(n2). Algoritma ini cocok digunakan untuk
tabel dengan ukuran yang besar (hingga jutaan
elemen) dan dibutuhkan kecepatan dalam
pengurutan nilai. Namun perlu diperhatikan
bahwa, dengan menggunakan algoritma ini
diperlukan ruang atau memori yang besar
dikarenakan algoritma yang diproses secara
rekursif dan menggunakan banyak tabel.
Langganan:
Postingan (Atom)
