Yo~ Konnichiwa sobat Otatechnime
Pengertian
Quick sort merupakan salah satu dari ke enam metode pengurutan dimana ini merupakan metode tercepat bagi komputer untuk melakukkan pengurutan pada data acak. Sesuai dengan sebutannya, "quick" maka bisa kita simpulkan ini merupakan metode yang cepat. Yap memang tercepat daripada metode lain tapi jika kita yang harus megurutkannya secara manual mungkin sedikit lebih sulit. Bagi pencarian manual mungkin ini lebih sulit tapi untuk mengurutkan data skala besar, quick lebih cepat dan efektif.
Quick sort menggunakan teknik sumbu acuan. Sumbu ini akan digunakan untuk menjadi suatu acuan dengan membandingkan data yang lain. Konsepnya tetap menggunakan perbandingan tetapi yang akan kita bandingkan adalah data dengan titik acuan. Sumbu acuan ini kita sebut dengan pivot. Selain pivot, nanti akan ada sumbu kanan dan sumbu kiri. Sumbu kiri digunakan untuk membandingkan data dari kiri dengan pivot, sedangkan sumbu kanan untuk membandingkan data dari kanan dengan pivot. Bagaimanakah langkah penyelesaiannya? Mari kita simak di bagian metode dibawah.
Metode
Quick sort menggunakan pivot, sumbu kiri dan sumbu kanan. Pada contoh pengerjaan dan penyelesaian dibawah nanti, kalian harus mengetahui keterangan untuk memudahkan pembaca sebagai berikut.
Kiri (Sumbu kiri akan diberi warna merah).
Kanan (Sumbu kanan diberi warna biru).
Pivot (Pivot diberi warna hijau).
Lalu kita akan mengurutkan suatu dbaris data acak berikut
5 8 3 4 7 1
Langkah-langkah penyelesaiannya adalah sebagai berikut:
1. Pertama, kita tentukan pivot nya. Boleh sembarang. Perlu diketahui, ketika quick sort diterapkan di mesin komputer, maka pivot akan random. Untuk contoh kali ini biar lebih mudah maka kita tentukan saja pivotnya, misal kita tentukan pivotnya adalah nilai 1 yaitu data paling kanan.
5 8 3 4 7 1
2. Setelah itu, kita tentukan sumbu kiri dan sumbu kanannya. Pada contoh kita berikan sumbu kiri pertama pada data paling kiri yaitu 5.
3. Sedangkan sumbu kanan kita berikan ke data paling kanan. Tapi karena paling kanan sudah pivot, maka nilai berikutnya yaitu 7.
5 8 3 4 7 1
4. Peletakan sumbu selesai, berikutnya adalah melakukkan penguirutan dengan metode quick sort. Sumbu kiri akan dibandingkan dengan pivot dan bergerak ke arah kanan. Sumbu kanan akan dibandingkan dengan pivot dan bergerak ke arah kiri.
Pada contoh. Sumbu kiri yaitu 5 kita bandingkan dengan pivot yaitu satu. Karena nilai 5 lebih besar dari pivot, maka nilai tersebut tetap dan tidak ditukar. Sumbu kiri hanya akan bergerak ke kanan bila belum menemukan data yang lebih besar dari pivot.
5 8 3 4 7 1
5. Begitu pula sumbu kanan. Sumbu akan bergerak ke kiri bila tidak ditemukan data yang lebih kecil dari pivot. Kali ini sumbu kanan yaitu 7 akan kita bandingkan dengan pivotnya yaitu 1. Karena 7 lebih besar dari 1 maka sumbu kanan bergerak ke kiri.
5 8 3 4 7 1
6. Nilai 4 ternyata masih lebih besar dari 1, maka sumbu kanan terus bergerak ke kiri.
5 8 3 4 7 1
7. Nilai 3 ternyata masih lebih besar dari 1, maka sumbu kanan terus bergerak ke kiri.
5 8 3 4 7 1
8. Nilai 8 ternyata masih lebih besar dari 1, maka sumbu kanan terus bergerak ke kiri.
5 8 3 4 7 1
9. Nilai 5 ternyata masih lebih besar dari 1, tapi karena nilai 5 itu merupakan sumbu kanan, maka jika sumbu kanan dan sumbu kiri bertemu, nilai tersebut harus ditukarkan dengan pivot sehingga menjadi berikut.
1 8 3 4 7 5
10. Lalu kita ulangi langkah pertama yaitu menentukan pivot, sumbu kiri dan kanan. Pivotnya kita tentukan yaitu 5, dengan sumbu kirinya 8 dan kanannya 7. Nilai 1 sudah tidak masuk hitungan karena sudah merupakan nilai terkecil dan sudah terurut berdasarkan letaknya yaitu paling kiri.
1 8 3 4 7 5
11. Nilai 8 lebih besar dari 5 maka sumbu kiri tidak bertukar. Sumbu kanan bernilai 7 lebih besar dari 5 maka sumbu bergerak ke kiri.
1 8 3 4 7 5
12. Lalu sumbu kanan dengan nilai 4 ternyata lebih kecil dari pivot, maka kita stop. Langkah berikutnya adalah menukarkan nilai sumbu kiri dengan nilai sumbu kanan. Kita tukarkan letak nilai 8 dengan 4.
1 4 3 8 7 5
13. Lakukan langkah pertama kembali. Pivot tetap pada 5. Kita bandingkan 5 dengan 4. Nilai 4 lebih kecil sehinggan sumbu bergerak ke kanan. Lalu nilai 5 dengan 8. Karena sudah ketemu yang lebih besar, sumbu berhenti.
1 4 3 8 7 5
14. Lalu sumbu kanan kita bandingkan dengan pivot. Ternyata lebih besar maka bergeser ke kiri.
1 4 3 8 7 5
15. Karena sumbu kiri dan kanan bertemu, maka nilai tersebut ditukar dengna pivot.
1 4 3 5 7 8
16. Berikutnya kita berikan pivot. Karena 7 dan 8 sudah bersebelahan dan sudah terurut maka tidak bisa kita jadikan pivot. Kita berikan ke 5. Untuk sumbu kiri nya 4 dan sumbu kanannya 3.
1 4 3 5 7 8
17. Kita bandingkan pivot dengan sumbu kiri. Karena 4 lebih kecil, maka sumbu bergerak ke kanan. Dan ternyata ketemu dengan sumbu kanan. Maka nilai tersebut ditukarkan dengan pivot menjadi berikut
1 5 3 4 7 8
18. Pivot kita letakkan ke nilai 4, sumbu kiri 5 dan sumbu kanan 3.
1 5 3 4 7 8
19. Nilai 5 lebih besar dari 4 maka letaknya tetap. Lalu sumbu kanan bernilai 3 lebih kecil dari pivot maka letak sumbu masing-masing kita ubah.
1 3 5 4 7 8
20. Pivot kita berikan ke nilai 4, lalu sumbu kirinya 3 dan kanannya 5.
1 3 5 4 7 8
21. Kita bandingkan 4 dengan 3, karena 3 lebih kecil maka bergeser ke kanan. Dan ternyata pertemuan kedua sumbu, maka nilai tersebut kita tukar dengan pivot.
1 3 4 5 7 8
22. Dan yap, nilai sudah terurut dengan menggunakan quick sort.
Perlu diketahui, saya berikan langkah diatas untuk memberi tahu kalian secara detail cara pengerjaannya jika kalian menemukan data yang ukurannya tidak diketahui. Jika diperhatikan, sebenarnya langkah bisa kita potong cukup sampai langkah ke-15 lalu tinggal menukarkan nilai 4 dan 3. Karena data contoh diatas sedikit dan nilai yang pasti sudah kalian ketahui. Tapi jika nilai tersebut desimal atau longkapnya cukup jauh maka lebih baik dilakukkan hingga proses langkah terakhir.
Demikian penyelesaian menurut metode quick sort. Memang repot dilakukkan manual tapi untuk komputer, ini lebih cepat dan efektif.
Semoga bermanfaat~
Metode yang lain
kak sekalian dimasukan contoh code pemograman nya biar dapat di aplikasikan
ReplyDeletegood job gan
ReplyDeleteLampu servis hp