Home > Ren's Free Time > Mengurutkan Bilangan pada Array menggunakan Algoritma Quick Sort

Mengurutkan Bilangan pada Array menggunakan Algoritma Quick Sort

November 21, 2010 Leave a comment Go to comments

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);
}

Semoga membantu😀

Jika salah tolong koreksi saya.

Referensi : dari berbagai sumber

  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: