Quick Sort

Hai hai kembali lagi dengan saya. Untuk kali ini saya akan berbagi ilmu tentang Quick sort.

Oke, tanpa banyak basa basi. Langsung saja simak penjelasannya dibawah ini.


Apa sih quick sort? Quick sort sendiri dikembangkan oleh Tony Hoare pada tahun 1960 dan mulai diperkenalkan dua tahun setelahnya yaitu pada tahun 1962.

Kok bisa disebut quick sih? Apa beneran cepat atau cuman namanya saja yang cepat? Quick sort memanglah yang tercepat untuk soal menyusun data dibandingkan dengan metode sorting lainnya. Dan metode ini pun memiliki kompleksivitas dan pemprosesanya pun dilakukan secara rekursif atau berulang-ulang.

Langsung saja pada contoh dan ilustrasi dibawah ini.

Kita memiliki data seperti pada gambar diatas. Nah langkah berikutnya adalah menentukan pivot atau elemen awal, tengah ataupun akhir dalam suatu array. Cara menentukannya adalah dengan cara, pivot = (i + j) / 2. pivot = (1 + 8)/2 = 4.5. Karena hasilnya mengandung koma lebih dari sama dengan 5, maka kita dapat memilih angka yang akan diambil. Angka 4 atau angka 5 (hasil pembulatan dari 4.5). Untuk kali ini kita akan mengambil angka 4 sebagai pivotnya.

Langkah selanjutnya adalah mengecek i dan j. Apakah i > pivot, jika iya maka i akan berhenti, jika tidak maka i + 1. Begitu pula dengan j, hanya saja jika j tidak lebih kecil dari pivot maka j - 1. Untuk tau kapan penukarannya dilakukan, penukaran elemen dilakukan ketika i sudah tidak berpindah ke elemen berikutnya begitu juga dengan j hanya saja j berpindah ke elemen sebelumnya (karena j - 1). Oke langsung saja lakukan penukaran. Dan di bawah ini adalah hasil pertukarannya

Gambar diatas adalah hasil dari penukarannya. Eits, ini belum selesai karena i > j maka pembagian partisi pun sudah terbagi menjadi dua partisi.

Kita bisa mulai mencarinya di partisi sebelah kiri. Lakukan langkah yang sama untuk setiap partisinya.

Dan hasil akhirnya adalah sebagai berikut :

Nah, itu adalah hasil akhir dari proses quick sort. Cepat kan prosesnya hanya saja algoritmanya yang lebih kompleks dibandingkan dengan sorting yang lain. Gak percaya kalau quick sort algoritmanya lebih kompleks dari sorting yang lainnya? Coba lihat contoh program quick sort dalam bahasa c++ dibawah ini.


Pusingkan?

Terima kasih atas waktunya. Jika ada pertanyaan bisa langsung komentar saja di post ini!!!

Sumber :
https://id.wikipedia.org/wiki/Quicksort
https://rizarulham.wordpress.com/2009/10/07/algoritma-quick-sort/
http://dtugasalgoritma.blogspot.co.id/2010/12/quick-sort-algoritma.html
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/quickSort.htm

Numerical Problem

Hello, kali ini kita akan membahas sedikit tentang Numerical problem, adalah masalah yang melibatkan perhitungan objek matematika : persamaan, komputasi integral, mengevaluasi fungsi, dan sebagainya.

Dapat diimplementasi pada :
 - Sistem informasi,
 - Pengiriman dan penerimaan data melalui internet,
 - Random generic number,
 - Perkalian matriks,
 - Pengurangan banwidth
 - dll.

Sekian beberapa informasi tentang numerical problem jika ada masukan silakan beri komentar pada tautan kami.

Cheers!!

Sumber :

-http://www3.cs.stonybrook.edu/~algorith/major_section/1.2.shtml
-Anany Levitin, Intro 2 Design&Analysis Algorithms.

Shell Sort

Hai semuanya pada kesempatan kali ini saya akan menjelaskan salah satu pengurutan dalam suatu algoritma . Pada materi sebelumnya kita sudah belajar pengurutan merge ( Merge Sort) dan pada post kali ini saya akan menjelaskan pengurutan shell (Shell Sort) , mungkin kalian sudah tahu apa itu Shell Sort atau dari kalian ada yang belum paham apa itu Shell Sort  . Yapss , disini saya akan mengingatkan kembali apa itu Shell Sort bagi yang sudah tahu sebelumnya dan menjelaskan bagi yang belum mengerti apa itu Shell Sort .

                Algoritma pengurutan Shell diberi nama sesuai penemunya (Donald Shell tahun 1959) [PAR95] . Algoritma ini merupakan perbaikan terhadap metode pengurutan sisip. Kelemahan metode pengurutan sisip sudah disebutkan pada post sebelumnya . Metode Shell Sort disebut juga dengan metode pertambahan menurun (diminshing icrement short). Metode ini mengurutkan data dengan cara membandungkan suatu data lain yang memiliki jarak tertentu sehingga membentuk sebuah sub-list, kemudian dilakukan pertukaran apabila diperlukan.

                Untuk melakukan pengurutan , kita mengurutkan larik setiap k elemen dengan metode pengurutan sisip, misalnya kita urutkan setiap 5 elemen (k kita namakan juga step atau increment). Selanjutnya, kita gunakan nilai step yang lebih kecil, misalnya k = 3, lalu kita urut setiap 3 elemen. Begitu seterusnya sampai nilai elemen k = 1. Karena setiap nilai step selalu berkurang maka Shell Short disebut dengan metode pengurutan penambahan penurunan.

Contoh :

Data sebelum pengurutan

13

40

29

60

80

21

15

37

45

88

22

46

18

Pass 1 (step = 5): Urutkan setiap lima elemen

Data	13	40	29	60	80	21	15	37	45	88	22	46	18
Index	1	2	3	4	5	6	7	8	9	10	11	12	13
	|					|					|
	13	..........................................				21	..........................................				22
		15	..........................................				22	..........................................				40
			18	..........................................				29	..........................................				37
				45	..........................................				60

Hasil pass pertama : 13, 15, 18, 45, 80, 21, 22, 29, 60, 88, 22, 40, 37

Pass 2 (step=3): Urutkan setiap tiga elemen

Data	13	40	29	60	80	21	15	37	45	88	22	46	18
Index	1	2	3	4	5	6	7	8	9	10	11	12	13
	|			|			|			|
	13	...................		15	...................		18	...................		60	...................		88
		22	...................		37	...................		40	...................		80
			21	...................		29	...................		45	...................		46

Hasil pass kedua : 13, 22, 21, 15, 37, 29, 18, 40, 45, 60, 80, 46, 88

Pass 3 (step=1): Urutkan setiap 1 elemen

Data	13	40	29	60	80	21	15	37	45	88	22	46	18
Index	1	2	3	4	5	6	7	8	9	10	11	12	13
	|	|	|	|	|	|	|	|	|	|	|	|	|
	13	15	18	21	22	29	37	40	45	46	60	80	88

Hasil Pass ketiga : 13, 15, 18, 21, 22, 29, 37, 40, 45, 46, 60, 80, 88

Perhatikan bahwa pada pass yang terakhir (step = 1), pengurutan Shell menjadi sama dengan pengurutan sisip biasa .

Nilai-nilai step seperti 5,3 dan 1 bukanlah angka “sihir” (magic). Kita dapat memilih nilai-nilai step yang lain yang merupakan perpangkatan dari dua (seperti 8,4,2,1) dapat mengakibatkan perbandingan elemen yang sama pada suatu pass akan terulang kembali pada pass berikutnya . Meskipun beberapa penelitian telah dibuat pada algoritma Shell, namum tidak seorang pun yang dapat membuktikan bahwa pemilihan step tertentu paling bagus diantara pemilihan step yang lain [KRU91].

Algoritma Pengurutan Shell

Procedure ShellSort(var L : LarikInt; n : integer);

{ Mengurutkan elemen larik L[1..n] sehingga tersusun menaik dengan metode pengurutan Shell. }

{ I.S : Elemen-elemen larik L sudah terdefinisi nilainya }

{ F.S : Elemen-elemen larik L terurut menaik sedemikian sehingga L[1] ≤ L[2] ≤ .. ≤ L[n] }

var

     Step, start : integer;

begin

     step := n;

     while step > 1 do

     begin

          step := step div 3 + 1;

          for start := 1 to step do

           InsSort (L, N, start, step)

          {endfor}

     end; {endwhile}

end; {endprocedure}

Kelebihan Shell Sort

1.       Algoritma ini sangat rapat dan mudah diimplementasikan

2.       Operasi pertukarannya hanya dilakukan sekali saja

3.       Waktu pengurutannya dapat lebih ditekan

4.       Mudah menggabungkannya kembali

5.       Kompleksitas selection sort relatif lebih kecil

Kekurangan Shell Sort

1.       Membutuhkan method tambahan

2.       Sulit untuk membagi masalah

https://betaraubd.wordpress.com/2012/11/23/kekurangan-dan-kelebihan-algoritma-insertion-sort-dan-sell-sort/

http://casey-school.blogspot.co.id/2014/03/metode-pengurutan-shell-short.html

Heap Sort

Heap Sort, apa sih Heap Sort? Penjelasan singkatnya adalah Heap sort merupakan salah satu metode pengurutan data dari suatu array yang digambarkan menjadi sebuah pohon atau tree dan nilai pada masing-masing indeksnya akan diurutkan.

Pada metode ini memiliki 3 bagian, yaitu Node, Root, Link, dan Leaf. Apa sih itu? Node adalah indeks yang berada pada array, root adalah node awal pada tree, link adalah sebuah garis yang menyambungkan antara node satu ke node lainnya, dan Leaf adalah node yang tidak memiliki anak atau tidak memiliki node turunan. Untuk ilustrasinya bisa dilihat dari gambar dibawah ini.

Contoh dari Heap Tree dapat dilihat dibawah ini.

Adapun proses dari Heap Sort :

1. Pembentukan Heap
2. Pengurutan Data pada Heap

Pada pembentukan Heap adapun cara-caranya yaitu dengan,

Dari sebuah array dibuat menjadi Complete Binary Tree, lalu

Jika sudah menjadi CBT lalu lakukan proses pengurutan secara max heap dengan cara banyaknya simpul dibagi dua untuk mencari nilai tengah dari sebuah array, sebagai contoh N = 6, Tengah = 6/2 = 3. Lalu lakukan reorganisasi pada simpul atau node ke-3. Dengan cara jika angka yang sekarang dibandingkan dengan angka selanjutnya yang ada di node turunannya itu lebih kecil maka tukar posisi.

Lalu, lakukan reorganisasi pada simpul ke-2.

Lalu lakukan juga pada simpul ke-1.

Kok itu dua kali sih? Karena angka 7 itu lebih kecil dari 14 dan 11, tetapi tidak lebih kecil dari 3. Maka dari itu dipindah posisikan sebanyak dua kali. Dan hasilnya adalah sebagai berikut

Dari data max heap tersebut. Barulah dapat kita lakukan pengurutan data heap dengan syarat :

1. Binary Tree dalam keadaan Max Heap, lalu
2. Hapus atau "Pecat" root dan tukarkan dengan simpul pada posisi terakhir.
3. Banyaknya simpul dikurangi 1
4. Jika n lebih dari 1, maka lakukan reorganisasi heap
5. Lakukan langkah ke-2 hingga ke-5 sampai n = 0.

Dapat dilihat dari ilustrasi dibawah ini.

Karena datanya Binary Tree tidak dalam keadaan Max Heap, maka harus dilakukan lagi pembentukan heap agar menjadi max Heap. Lakukan terus hingga n = 0. Sehingga hasilnya dapat dilihat sebagai berikut.

Dan, waalaa hasil heap sort sudah selesai.

Jika ada pertanyaan bisa langsung tulis di kolom komentar.

Terima Kasih!!!

Sumber :

http://loserbombti.blogspot.co.id/2014/07/algoritma-heap-sort.html
http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L13-HeapSortEx.htm