QuickSort adalah algoritma bagi & taklukkan. Dalam paradigma desain algoritma Divide & Conquer, kita membagi masalah dalam sub-masalah secara rekursif kemudian menyelesaikan sub-masalah tersebut & akhirnya menggabungkan solusi untuk menemukan hasil akhir. Pada artikel ini kita akan fokus pada QuickSort In
Petunjuk berikut akan dibahas dalam artikel ini,
Mari kita mulai!
Satu hal yang perlu diperhatikan saat membagi masalah menjadi sub masalah adalah bahwa struktur sub masalah tidak berubah seperti masalah aslinya.
Algoritma Divide & Conquer memiliki 3 langkah:
- Bagilah: Memecah masalah menjadi subproblem
- Conquer: Menyelesaikan subproblem secara rekursif
- Gabungkan: Menggabungkan solusi untuk mendapatkan hasil akhir
Ada berbagai macam algoritma berdasarkan paradigma divide & conquer. Sortir cepat & Gabungkan semacam ada di antara mereka.
Meskipun kompleksitas waktu kasus terburuk dari QuickSort adalah O (n2) yang lebih banyak daripada banyak algoritme pengurutan lainnya seperti Merge Sort dan Heap Sort, QuickSort lebih cepat dalam praktiknya, karena loop dalamnya dapat diimplementasikan secara efisien pada sebagian besar arsitektur, dan di sebagian besar data dunia nyata.
Mari membahas tentang penerapan algoritme Pengurutan cepat. Algoritme Quicksort mengambil elemen pivot dan mempartisi array di sekitar elemen pivot. Ada beberapa variasi Quicksot yang bergantung pada cara Anda memilih elemen pivot. Ada beberapa cara untuk memilih elemen pivot:
- Memilih elemen pertama
- Pilih elemen terakhir
- Memilih elemen acak
- Memilih elemen median
Hal penting berikutnya untuk dipahami adalah, fungsi partisi () dalam algoritme Quick sort. Fungsi partisi untuk mengambil elemen pivot, meletakkannya di posisi kanan, memindahkan semua elemen yang lebih kecil dari elemen pivot ke kiri & semua elemen yang lebih besar ke kanan. Quicksort membutuhkan waktu linier untuk melakukannya.
Kemudian array dibagi menjadi dua bagian dari elemen pivot (yaitu elemen kurang dari pivot & elemen lebih besar dari pivot) & kedua array diurutkan secara rekursif menggunakan algoritma Quicksort.
ec2 membuat instance dari snapshot
Sekarang kita telah memahami cara kerja algoritma QuickSort. Mari kita pahami cara menerapkan algoritma Quicksort di Java.
QuickSort Fungsi:
/ * Fungsi Quicksort membutuhkan array untuk diurutkan dengan indeks terendah & tertinggi * /
void sort (int arr [], int lowIndex, int highIndex) {// Hingga lowIndex = highIndex if (lowIndexSekarang mari kita lihat kode partisi untuk memahami cara kerjanya.
Partisi Kode
Pada kode partisi, kita akan memilih elemen terakhir sebagai elemen pivot. Kami melintasi array lengkap (yaitu menggunakan variabel j dalam kasus kami). Kami melacak elemen terkecil terakhir dalam array (yaitu menggunakan variabel i dalam kasus kami). Jika kita menemukan elemen yang lebih kecil dari pivot, kita pindahkan elemen arus swap a [j] dengan arr [i], kalau tidak kita lanjutkan melintasi.
int partisi (int arr [], int lowIndex, int highIndex) {// Menjadikan elemen terakhir sebagai pivot int pivot = arr [highIndex] // Menggunakan i untuk melacak elemen yang lebih kecil dari pivot int i = (lowIndex-1) untuk (int j = lowIndex jSekarang Anda telah memahami fungsi Quicksort & partisi, mari kita lihat kode lengkapnya
QuickSort Kode Java
class QuickSort {// Metode Partisi int partisi (int arr [], int lowIndex, int highIndex) {int pivot = arr [highIndex] int i = (lowIndex-1) untuk (int j = lowIndex j// Metode Penyortiran
void sort (int arr [], int lowIndex, int highIndex) {if (lowIndex// Metode untuk mencetak array
static void printArray (int arr []) {int n = arr.length untuk (int i = 0 i// Metode Utama
public static void main (String args []) {int arr [] = {101, 37, 68, 29, 11, 5} int n = arr.length QuickSort ob = new QuickSort () ob.sort (arr, 0, n-1) System.out.println ('array terurut') printArray (arr)}} Keluaran:
kode java untuk mengakhiri program
Sekarang setelah menjalankan program Java di atas, Anda akan mengerti bagaimana QuickSort bekerja & bagaimana menerapkannya di Java.Jadi kami telah mengakhiri artikel ini tentang 'Quicksort in Java'. Jika Anda ingin mempelajari lebih lanjut,lihat oleh Edureka, perusahaan pembelajaran online terpercaya. Kursus pelatihan dan sertifikasi Java J2EE dan SOA dari Edureka dirancang untuk melatih Anda baik konsep inti dan lanjutan Java bersama dengan berbagai kerangka kerja Java seperti Hibernate & Spring.
Ada pertanyaan untuk kami? Harap sebutkan di bagian komentar blog ini dan kami akan menghubungi Anda kembali secepatnya.