Pengertian Quick Sort beserta coding dalam c++

Salah satu algoritma yang menggunakan paradigma Divide and Conquer adalah Algoritma Quick Sort. Algoritma ini mengambil salah satu elemen secara acak (biasanya dari tengah) yang disebut dengan pivot lalu menyimpan semua elemen yang lebih kecil di sebelah kiri pivot dan semua elemen yang lebih besar di sebelah kanan pivot. Hal ini dilakukan secara rekursif terhadap elemen di sebelah kiri dan kanannya sampai semua elemen sudah terurut.

Ide dari algoritma ini adalah sebagai berikut:

a. Pilih satu elemen secara acak sebagai pivot

b. Pindahka semua elemen yang lebih kecil ke sebelah kiri pivot dan semua elemen yang lebih besar ke sebelah kanan pivot. Elemen yang nilainya sama bisa disimpan di salah satunya.

c. Lakukan sort secara rekursif terhadap sub-array sebelah kiri dan kanan pivot

Berikut ini implementasi Algoritma Quick Sort menggunakan C++ dengan Tool yang digunakan Code Block 8.02

-----------------------------------------------------------------------------------------------------------------

#include <iostream>
#define n 20

using namespace std;
int Ar[n];
void quickSort(int arr[], int left, int right);

int main()
{   int jumlahBil=5;

cout<<"Masukkan jumlah bilangan dalam arry [Maksimal 20]"<<endl;
cin>>jumlahBil;
int Ar[jumlahBil];
for(int i=0; i<jumlahBil;i++)
{
cout<<"Bilangan ke-"<< i+1 << endl;
cin>>Ar[i];
}
quickSort(Ar,0,jumlahBil-1 );
cout<<"Data yang telah diurutkan"<<endl;
for(int i=0; i<jumlahBil;i++)
{
cout<<Ar[i]<<"\n";
}

}
void quickSort(int arr[], int left, int right)
{
int i = left, j = right;

int tmp;

int pivot = arr[(left + right) / 2];
while (i <= j) {

while (arr[i] < pivot)

i++;

while (arr[j] > pivot)

j--;

if (i <= j) {
tmp = arr[i];

arr[i] = arr[j];

arr[j] = tmp;

i++;

j--;

}

};

if (left < j)

quickSort(arr, left, j);

if (i < right)



quickSort(arr, i, right);
}

----------------------------------------------------------------------------------------------------------------- tampilan jika sudah jadi akan seperti ini :

Semoga bermanfaat.

terimakasih