ouick sort

  Metode Quick

Metode Quick sering disebut juga metode partisi (partition exchange sort).Metode ini diperkenalkan pertama kali oleh C.A.R. Hoare pada tahun 1962.Untuk mempertinggi efektifitas dari metode ini, digunakan teknik menukarkan dua elemen dengan jarak yang cukup besar.

Proses penukaran dengan metode quick dapat dijelaskan sebagai berikut.: mula mula dipilih data tertentu yang disebut pivot, misalnya x. Pivot dipilih untuk mengatur data di sebelah kiri agar lebih kecil daripada pivot dan data di sebelah kanan agar lebih besar daripada pivot. Pivot ini diletakkan pada posisi ke j sedemikian sehingga data antara 1 sampai dengan j-1 lebih kecil daripada x. Sedangkan data pada posisi ke j+1 sampai N lebih besar daripada x. Caranya dengan menukarkan data diantara posisi 1 sampai dengan j-1 yang lebih besar daripada x dengan data diantara posisi j+1 sampai dengan N yang lebih kecil daripada x. Ilustrasi dari metode quick dapat dilihAat pada Gambar.

Gambar diatas menunjukkan pembagian data menjadi sub-subbagian. Pivotdipilih dari data pertama tiap bagian maupun sub bagian, tetapi sebenarnya kita bisa memilih sembarang data sebagai pivot. Dari ilustrasi diatas bisa kita lihat bahwa metodeQuick Sort ini bisa kita implementasikan menggunakan dua cara, yaitu dengan cara nonrekursif dan rekursif. Pada kedua cara diatas, persoalan utama yang perlu kita perhatikanadalah bagaimana kita meletakkan suatu data pada posisinya yang tepat sehinggamemenuhi ketentuan diatas dan bagaimana menyimpan batas-batas subbagian. Dengancara seperti yang diperlihatkan pada Gambar 6.1, kita hanya menggerakkan data pertamasampai di suatu tempat yang sesuai. Dalam hal ini kita hanya bergerak dari satu arahsaja.Untuk mempercepat penempatan suatu data, kita bisa bergerak dari dua arah, kiridan kanan. Caranya adalah sebagai berikut : misalnya kia mempunyai 10 data (N=9) :

12    35        9          11        3          17        23        15        31        20

i=0                                                                                                  j=9

Pertama kali ditentukan i=0 (untuk bergerak dari kiri ke kanan), dan j=N (untuk bergerak dari kanan ke kiri). Proses akan dihentikan jika nilai i lebih besar atau sama dengan j.Sebagai contoh, kita akan menempatkan elemen pertama, 12 pada posisinya yang tepat dengan bergerak dari dua arah, dari kiri ke kanan dan dari kanan ke kiri secarabergantian. Dimulai dari data terakhir bergerak dari kanan ke kiri (j dikurangi 1),dilakukan pembandingan data sampai ditemukan data yang nilainya lebih kecil dari 12yaitu 3 dan kedua elemen data ini kita tukarkan sehingga diperoleh

3      35        9          11        12        17        23        15        31        20

i=0                                      j=4

Setelah itu bergerak dari kiri ke kanan dimulai dari data 3 (i ditambah 1), dilakukanpembandingan pada setiap data yang dilalui dengan 12, sampai ditemukan data yang nilainya lebih besar dari 12 yaitu 35. Kedua data kita tukarkan sehingga diperoleh

3      12        9          11        35        17        23        15        31        20

i=1                               j=4

Berikutnya bergerak dari kanan ke kiri dimulai dari 11. Dan ternyata data 11 lebih kecil dari 12, kedua data ini ditukarkan sehingga diperoleh

3      11        9          12        35        17        23        15        31        20

i=1                   j=3

Kemudian dimulai dari 9 bergerak dari kiri ke kanan. Pada langkah ini ternyata tidakditemukan data yang lebih besar dari 12 sampai nilai i=j. Hal ini berarti proses penempatan data yang bernilai 12 telah selesai, sehingga semua data yang lebih kecil dari 12 beradadi sebelah kiri dan data yang lebih besar dari 12 berada di sebelah kanan seperti terlihat di bawah ini

3

11

9

12

35

17

23

15

31

20

Daftar Pustaka

http://cahyakpop.blogspot.co.id/2012/06/sorting-pengurutan.html

http://cahyakpop.blogspot.co.id/2012/08/pengurutan-dan-pencarian-pemprograman.html

https://www.academia.edu/4444655/BAB_VI Metode_Pengurutan_Jumlah_Pembandingan_Jumlah_Penukaran_Penyisipan_langsung_Penyisipan_biner_Seleksi_Gelembung

http://entin.lecturer.pens.ac.id/Struktur%20Data%20&%20Algoritma/buku/Data%20Structure%20-%20Bab%206.pdf

http://entin.lecturer.pens.ac.id/SD%20&%20Algoritma%20PJJ/Bulan%204/Minggu%2013%20Searching.pdf

http://andiagusta.blogspot.co.id/2014/02/algoritma-pencarian-searching.html

Antony pranata.,2000,Algoritma dan pemrograman,yogyakarta,Indonesia

Lanjutan Sorting Metode Counting dan Metode Shell

Metode Shell

Metode ini disebut juga dengan metode pertambahan menurun (diminishing increment).Metode  dikembangkan oleh Donald L. Shell pada tahun 1959, sehingga sering disebut dengan Metode Shell Sort. Metode ini mengurutkan data dengan cara membandingkan suatu data dengan data lain yang memiliki jarak tertentu, kemudian dilakukan penukaran bila diperlukan.

Proses pengurutan dengan metode Shell dapat dijelaskan sebagai berikut :

·      Pertama-tama adalah menentukan jarak mula-mula dari data yang akan dibandingkan, yaitu N / 2. Data pertama dibandingkan dengan data dengan jarak N / 2. Apabila data pertama lebih besar dari data ke N / 2 tersebut maka kedua data tersebut ditukar. Kemudian data kedua dibandingkan dengan jarak yang sama yaitu N / 2. Demikian seterusnya sampai seluruh data dibandingkan sehingga semua data ke-j selalu lebih kecil daripada data ke-(j + N / 2).

·      Pada proses berikutnya, digunakan jarak (N / 2) / 2 atau N / 4. Data pertama dibandingkan dengan data dengan jarak N / 4. Apabila data pertama lebih besar dari data ke N / 4 tersebut maka kedua data tersebut ditukar. Kemudian data kedua dibandingkan dengan jarak yang sama yaitu N / 4. Demikian seterusnya sampai seluruh data dibandingkan sehingga semua data ke-j lebih kecil daripada data ke-(j + N / 4).

·      Pada proses berikutnya, digunakan jarak (N / 4) / 2 atau N / 8. Demikian seterusnya sampai jarak yang digunakan adalah 1.

Algoritma metode Shell dapat dituliskan sebagai berikut :

Jarak ←N

Selama (Jarak > 1) kerjakan baris 3 sampai dengan 9

Jarak ←Jarak / 2. Sudah ←false

Kerjakan baris 4 sampai dengan 8 selama Sudah = false

Sudah ←true

j←0

Selama (j < N – Jarak) kerjakan baris 8 dan 9

Jika (Data[j] >Data[j + Jarak] maka tukar Data[j], Data[j + Jarak]. Sudah ←true

j←j + 1

Untuk lebih memperjelas langkah-langkah algoritma penyisipan langsung dapat dilihat pada tabel. Proses pengurutan pada tabel 6.4 dapat dijelaskan sebagai berikut:

·      Pada saat Jarak = 5, j diulang dari 0 sampai dengan 4. Pada pengulangan pertama, Data[0] dibandingkan dengan Data[5]. Karena 12<17, maka tidak terjadi penukaran. Kemudian Data[1] dibandingkan dengan Data[6]. Karena 35>23 maka Data[1] ditukar dengan Data[6]. Demikian seterusnya sampai j=4.

·      Pada saat Jarak = 5/2 = 2, j diulang dari 0 sampai dengan 7. Pada pengulangan pertama, Data[0] dibandingkan dengan Data[2]. Karena 12>9 maka Data[0] ditukar dengan Data[2]. Kemudian Data[1] dibandingkan dengan Data[3] juga terjadi penukaran karena 23>11. Demikian seterusnya sampai j=7. Perhatikan untuk Jarak = 2 proses pengulangan harus dilakukan lagi karena ternyata Data[0] > Data[2]. Proses pengulangan ini berhenti bila Sudah=true.

·      Demikian seterusnya sampai Jarak=1.

Di bawah ini merupakan prosedur yang menggunakan metode Shell.

void ShellSort(int N)

{

int Jarak, i, j;

bool Sudah;

Jarak = N;

while(Lompat > 1){

Jarak = Jarak / 2;

Sudah = false;

while(!Sudah){

Sudah = true;

for(j=0; j<N-Jarak; j++){

i = j + Jarak;

if(Data[j] > Data[i]){

61

Tukar(&Data[j], &Data[i]);

Sudah = false;

}

}

}

}

}

Metode Counting 

Untuk dapat melakukan pengurutan dengan counting sort rentang nilai untuk kumpulan data yang akan diurutkan harus diketahui, katakanlah k. Ide dasar dari counting sort adalah menentukan, untuk setiap elemen x, jumlah elemen yang lebih kecil daripada x, yang kemudian informasi ini digunakan untuk menentukan posisi x. Contoh sederhana saja, jika terdapat 12 elemen yang lebih kecil daripada x, maka x akan mendapatkan posisinya di posisi 13.

Tentu saja, sedikit modifikasi harus dilakukan agar metode ini dapat menangani kasus di mana terdapat elemen-elemen lain yang nilainya sama dengan x. Di mana tentu saja kita tidak dapat menempatkan semua elemen yang nilainya sama dengan x di posisi yang sama.

Implementasi Counting Sort

Misal array data yang akan diurutkan adalah A. Counting sort membutuhkan sebuah array C berukuran k, yang setiap elemen C[i] merepresentasikan jumlah elemen dalam A yang nilainya adalah i. Di array inilah penghitungan (counting) yang dilakukan dalam pengurutan ini disimpan. Misal kita akan melakukan pengurutan pada array A sebagai berikut, dengan n adalah 10 dan diasumsikan bahwa rentang nilai setiap A[i] adalah 1..5 :

A

1

3

5

4

5

2

2

3

3

5

1      2      3      4      5      6      7     8      9     10

Dan array C setelah diinisialisasi adalah :

C

0

0

0

0

0

1      2      3      4      5

Kemudian proses penghitungan pun dimulai, proses ini linier, dilakukan dengan menelusuri array A,

Langkah 1 : pembacaan pertama mendapat elemen A[1] dengan isi 1, maka C[1] ditambah 1.

A

1

3

5

4

5

2

2

3

3

5

1      2      3      4      5      6      7     8      9     10

C

1

0

0

0

0

1      2      3      4      5

Langkah 2 : pembacaan kedua mendapat elemen A[2] dengan isi 3, maka C[3] ditambah 1.

A

1

3

5

4

5

2

2

3

3

5

1      2      3      4      5      6      7     8      9     10

C

1

0

1

0

0

1      2      3      4      5

Langkah 3 : pembacaan ketiga mendapat elemen A[3] dengan isi 5, maka C[5] ditambah 1.

A

1

3

5

4

5

2

2

3

3

5

1      2      3      4      5      6      7     8      9     10

C

1

0

1

0

1

1      2      3      4      5

Langkah 4 : pembacaan keempat mendapat elemen A[4] dengan isi 4, maka C[4] ditambah 1.

A

1

3

5

4

5

2

2

3

3

5

1      2      3      4      5      6      7     8      9     10

C

1

0

1

1

1

1      2      3      4      5

Demikian dilakukan terus menerus hingga semua elemen A telah diakses. Hingga setelah langkah ke 10 didapatkan array C sebagai berikut :

C

1

2

3

1

3

1      2      3      4      5

Lalu array C diproses sehingga setiap elemen C, C[i] tidak lagi merepresentasikan jumlah elemen dengan nilai sama dengan i, namun setiap C[i] menjadi merepresentasikan jumlah elemen yang lebih kecil atau sama dengan i. Dan setelah proses tersebut dilakukan didapatkan C sebagai berikut :

C

1

3

6

7

10

1      2      3      4      5

Setelah C didapat dilakukan proses penempatan sesuai dengan posisi yang didapat. Proses ini dilakukan dengan menelusuri kembali A dari belakang. Mengapa dari belakang? Karena kita mengharapkan hasil pengurutan yang stable, yang akan sangat penting dalam pengurutan data majemuk.

Dalam proses ini kita mengakses elemen A[i], kemudian memposisikannya di posisi sebagaimana tercatat dalam C[A[i]], kemudian kita mengurangkan C[A[i]] dengan 1, yang dengan jelas untuk memberikan posisi untuk elemen berikutnya dengan yang isinya sama dengan A[i].

Proses ini memerlukan sebuah array bantu B yang ukurannya sama dengan array A, yaitu n. Yang pada awalnya semua B[i] diinisialisasi dengan nil.

B

-

-

-

-

-

-

-

-

-

-

1      2      3      4      5      6      7     8      9     10

Langkah 1 : elemen A[10] adalah 5, maka karena C[5] adalah 10, maka B[10] diisi dengan 5, dan C[5] dikurangi 1.

A

1

3

5

4

5

2

2

3

3

5

1      2      3      4      5      6      7     8      9     10

B

-

-

-

-

-

-

-

-

-

5

1      2      3      4      5      6      7     8      9     10

C

1

3

6

7

9

1      2      3      4      5

Langkah 2 : elemen A[9] adalah 3, maka karena C[3] adalah 6, maka B[6] diisi dengan 3, dan C[3] dikurangi 1.

A

1

3

5

4

5

2

2

3

3

5

1      2      3      4      5      6      7     8      9     10

B

-

-

-

-

-

3

-

-

-

5

1      2      3      4      5      6      7     8      9     10

C

1

3

5

7

9

1      2      3      4      5

Langkah 3 : elemen A[8] adalah 3, maka karena C[3] adalah 5, maka B[5] diisi dengan 3, dan C[3] dikurangi 1.

A

1

3

5

4

5

2

2

3

3

5

1      2      3      4      5      6      7     8      9     10

B

-

-

-

-

3

3

-

-

-

5

1      2      3      4      5      6      7     8      9     10

C

1

3

4

7

9

1      2      3      4      5

Langkah 4 : elemen A[7] adalah 2, maka karena C[2] adalah 3, maka B[3] diisi dengan 2, dan C[2] dikurangi 1.

A

1

3

5

4

5

2

2

3

3

5

1      2      3      4      5      6      7     8      9     10

B

-

-

2

-

3

3

-

-

-

5

1      2      3      4      5      6      7     8      9     10

C

1

2

4

7

9

1      2      3      4      5

Demikian proses dilakukan hingga elemen A[1] selesai diproses, sehingga didapatkan hasil akhir

B

1

2

2

3

3

3

4

5

5

5

1      2      3      4      5      6      7     8      9     10

Yang telah berupa array dengan elemen-elemennya terurut secara non-decreasing.

2.7 Algoritma dan Kompleksitas Waktu Counting Sort

Dari implementasi yang telah dilakukan tersebut, penulis mengimplementasikannya manjadi sebuah program menggunakan bahasa Pascal sebagai berikut :

procedure CountingSort (A : TArray; var B : TArray);

var

C : array [1..k] of byte;

i : integer;

begin

for i:=1 to k do

C[i] := 0;

for i:=1 to n do

C[A[i]] := C[A[i]] + 1;

for i:=2 to k do

C[i] := C[i] + C[i-1];

for i:=n downto 1 do begin

B[C[A[i]]] := A[i];

C[A[i]] := C[A[i]] - 1;

end;

end;

Waktu yang dibutuhkan untuk mengurutkan data menggunakan counting sort bisa didapatkan dari perhitungan sebagai berikut : Kalang pertama membutuhkan waktu O(k), kalang kedu membutuhkan waktu O(n), kalang ketiga membutuhkan waktu O(k), dan kalang keempat membutuhkan waktu O(n).

Jadi secara total membutuhkan waktu O(k+n), yang seringkali dianggap k = O(n), sehingga waktu total yang dibutuhkan menjadi O(n)