Pengurutan cepat banyak digunakan sebagai algoritma pengurutan yang efisien. Metode Arrays.sort di JDK SUN menggunakan pengurutan cepat.
Penyortiran Cepat mengadopsi gagasan klasik membagi dan menaklukkan:
Bagi: Pilih X primitif (biasanya elemen pertama array), dan bagi array menjadi dua bagian melalui beberapa operasi partisi: separuh kiri lebih kecil atau sama dengan X, dan separuh kanan lebih besar atau sama dengan X .
Conquer: Subarray kiri dan kanan memanggil proses Divide secara rekursif.
Gabungkan: Pengurutan cepat digunakan sebagai algoritma pengurutan di tempat dan tidak memerlukan operasi penggabungan apa pun.
Terlihat bahwa bagian inti dari quick sort adalah proses partisi. Berikut contoh penjelasan detail cara mempartisi array (gambar diambil dari "Pengantar Algoritma")
Inisialisasi: Pilih P=2 primitif, yang merupakan elemen pertama array. i=1,j=i+1=2 (subskrip array dimulai dengan 1)
Loop invarian: Elemen di antara 2~i semuanya kurang dari atau sama dengan P, dan elemen di antara i+1~j semuanya lebih besar atau sama dengan P.
Proses perulangan: j berpindah dari 2 ke n, periksa elemen pada posisi j, dan jika lebih besar atau sama dengan P, lanjutkan perulangan. Jika lebih kecil dari P, tukar elemen pada posisi j (yang seharusnya tidak muncul pada rentang i+1~j) dengan elemen pada posisi i+1 (masih pada rentang i+1~j setelah pertukaran), dan pada saat yang sama mengubah i+1 . Ini mempertahankan invarian loop (lihat deskripsi invarian loop di atas). Sampai j=n, operasi loop terakhir selesai.
Perlu dicatat bahwa setelah menyelesaikan perulangan, elemen pada posisi i perlu ditukar dengan elemen pertama array untuk memenuhi persyaratan yang pertama kali kita tetapkan (sesuai dengan langkah ke-i pada gambar).
Pembaca yang cermat mungkin memikirkan metode partisi lain yang lebih mudah, yaitu mengeluarkan primitif dan menyimpannya dalam larik lain dengan ukuran yang sama. Saat menemukan elemen yang lebih kecil dari primitif, elemen tersebut disimpan di bagian kiri larik elemen yang lebih besar dari primitif, mereka disimpan di bagian kiri array. Kompleksitas operasi tersebut juga bersifat linier yaitu Theta(n). Namun kompleksitas ruang menjadi dua kali lipat. Ini juga merupakan keuntungan dari penyortiran cepat di tempat.
Copy kode kodenya sebagai berikut:
QuickSort kelas publik {
private static void QuickSort(int[] array,int start,int end)
{
jika(mulai<akhir)
{
int key=array[start];//Inisialisasi dan simpan primitif
int i=mulai,j;//Inisialisasi i,j
untuk(j=mulai+1;j<=akhir;j++)
if(array[j]<key)//Jika elemen di sini lebih kecil dari primitif, tukarkan elemen ini dengan elemen di i+1, dan tambahkan 1 ke i. Jika lebih besar atau sama dengan primitif, lanjutkan lingkaran.
{
int suhu=array[j];
larik[j]=susunan[i+1];
susunan[i+1]=temp;
saya++;
}
}
array[start]=array[i];//Tukarkan elemen dan primitif di i
susunan[i]=kunci;
QuickSort(array, start, i-1);//panggilan rekursif
QuickSort(array, i+1, akhir);
}
}
public static void main(String[] args)
{
int[] array=baru int[]{11,213,134,44,77,78,23,43};
QuickSort(array, 0, array.panjang-1);
for(int i=0;i<array.panjang;i++)
{
Sistem.keluar.println((i+1)+"th:"+array[i]);
}
}
}