NPM : 59414226
Kelas : 1IA17
Mata Kuliah : Algoritma dan Pemrograman 1A
Dosen : Kunto Bayu A, ST
Quick Sort
Quick Sort merupakan suatu algoritma pengurutan data yang menggunakan teknik pemecahan data menjadi partisi-partisi, sehingga metode ini disebut juga dengan nama partition exchange sort.
Algoritma ini hanya memiliki 2 langkah sebagai berikut :
- Divide = bisa dikatakan Memilah rangkaian data menjadi dua sub-rangkaian A[p…q-1] dan A[q+1…r] dimana setiap elemen A[p…q-1] adalah kurang dari atau sama dengan A[q] dan setiap elemen pada A[q+1…r] adalah lebih besar atau sama dengan elemen pada A[q]. A[q] disebut sebagai elemen pivot. Perhitungan pada elemen q merupakan salah satu bagian dari prosedur pemisahan.
- Conquer = dengan cara Mengurutkan elemen pada sub-rangkaian secara rekursif. Pada algoritma quicksort, langkah ”kombinasi” tidak di lakukan karena telah terjadi pengurutan elemen – elemen pada sub-array
1. Pivot adalah elemen pertama, elemen terakhir, atau elemen tengah tabel. Cara ini hanya bagus jika elemen tabel tersusun secara acak, tetapi tidak bagus jika elemen tabel semula sudah terurut. Misalnya, jika elemen tabel semula menurun, maka semua elemen tabel akan terkumpul di upatabel kanan.
2. Pivot dipilih secara acak dari salah satu elemen tabel. Cara ini baik, tetapi mahal, sebab memerlukan biaya (cost) untuk pembangkitan prosedur acak. Lagi pula, itu tidak mengurangi kompleksitas waktu algoritma.
3. Pivot adalah elemen median tabel. Cara ini paling bagus, karena hasil partisi menghasilkan dua bagian tabel yang berukuran seimbang (masing masing ≈ n/2 elemen). Cara ini memberikan kompleksitas waktu yang minimum. Masalahnya, mencari median dari elemen tabel yang belum terurut adalah persoalan tersendiri.
Langkah-Langkah pengerjaannya ialah:
Ambil sebuah elemen, yang disebut dengan pivot, pada sebuah daftar.
Urutkan kembali sebuah list sehingga elemen dengan nilai yang kecil dari pivot berada sebelum pivot, sedangkan seluruh element yang memiliki nilai yang lebih besar dari pivot berada setelahnya (nilai yang sama dapat berada pada pivot setelahnya). Setelah pemisahan, pivot berada pada posisi akhirnya. Operasi ini disebut Partition.
Sub list kemudian disortir secara recursif dari elemen yang lebih kecil dan sub list dari elemen yang lebih besar.
Untuk memulai irterasi pengurutan, pertama-tama sebuah elemen dipilih dari data, kemudian elemen-elemen data akan diurutkan diatur sedemikian rupa, sehingga nilai variabel Sementara berada di suatu posisi ke I yang memenuhi kondisi sebagai berikut :
Untuk memulai irterasi pengurutan, pertama-tama sebuah elemen dipilih dari data, kemudian elemen-elemen data akan diurutkan diatur sedemikian rupa, sehingga nilai variabel Sementara berada di suatu posisi ke I yang memenuhi kondisi sebagai berikut :
- Semua elemen di posisi ke 1 sampai dengan ke I-1 adalah lebih kecil atau sama dengan Sementara.
- Semua elemen di posisi ke I+1 sampai dengan ke N adalah lebih besar atau sama dengan Sementara.
Sebagai contoh, data yang akan diurutkan sejumlah 12 elemen sebagai berikut :
33 45 18 7 5 99 57 25 55 10 40 50
Misalnya element yang dipilih adalah element yang pertama, maka variabel Sementara bernilai 33. Setelah diatur, maka nilai 33 akan menempati posisi ke I, yaitu posisi urutan ke 6 sebagai berikut :
33 45 18 7 5 99 57 25 55 10 40 50
Misalnya element yang dipilih adalah element yang pertama, maka variabel Sementara bernilai 33. Setelah diatur, maka nilai 33 akan menempati posisi ke I, yaitu posisi urutan ke 6 sebagai berikut :
Tampak bahwa kondisi berikut terpenuhi, yaitu :
- Semua elemen di posisi ke 1 sampai dengan posisi ke 5 (10, 25, 18, 7,dan 5) akan lebih kecil atau sama dengan nilai 33 yang dipilih.
- Semua elemen di posisi ke 7 sampai dengan ke 12 (57,99,55,45,40 dan 50) aka lebih besar atau sama dengan nilai 33 yang dipilih.
Dengan demikian, data tersebut akan terpecah menjadi 2 partisi, sebagai berikut :
(10 25 18 7 5) 33 (57 99 55 45 40 50)
Proses ini diulangi kembali untuk masing-masing partisi data, yaitu untuk data (10, 25, 18, 7, 5) dan data (57, 99, 55, 45, 40, 50). Untuk partisi yang pertama, bila nilai Sementara yang diambil adalah data pertama kembali dalam partisi bersangkutan, yaitu 10 dan diatur kembali sedemikian rupa, maka nilai data yang dipilih akan terletak di posisi sebagai berikut:
(5 7) 10 (18 25) 33 (57 99 55 45 40 50)
Untuk mengurutkan masing-masing partisi, maka proses tersebut diulangi kembali dan tiap-tiap partisi dipecah-pecah kembali lebih lanjut. Kurung yang menutupi partisi menunjukkan data yang belum urut dan perlu diurutkan kembali. Sedang data yang tidak berada diantara tanda kurung merupakan data yang sudah diurut. Iterasi selanjutya sampai didapatkan data yang telah urut semuanya adalah sebagai berikut ini.
5 ( 7) 10 (18 25) 33 (57 99 55 45 40 50)
5 7 10 18 (25) 33 (57 99 55 45 40 50)
5 7 10 18 25 33 (50 40 55 45) 57 (99)
5 7 10 18 25 33 (50 40 55 45) 57 99
5 7 10 18 25 33 (45 40) 50 (55) 57 99
5 7 10 18 25 33 (45 40) 50 55 57 99
5 7 10 18 25 33 40 (45) 50 55 57 99
5 7 10 18 25 33 40 45 50 55 57 99
Sumber:
Tidak ada komentar:
Posting Komentar