Contoh Program Algoritma Quick Sort C++ Sederhana

Algoritma metode quick sort c++ diperkenalkan pertama kali oleh C.A.R. Hoare pada tahun 1960. Program quick sort c ++ adalah algoritma sorting yang berdasarkan pembandingan dengan metode divide and conquer (bagi dan kuasai). Disebut metode Quick Sort, karena Algoritma quick sort mengurutkan dengan sangat cepat. metode Quick sort c++ disebut juga dengan partition exchange sort, karena konsepnya membuat partisi-partisi, dan sorting dilakukan per partisi.

Contoh Algoritma Quick Sort C++

metode quick sort c++ mengurutkan dengan sangat cepat, namun algoritma ini sangat komplex dan diproses secara rekursif. Dapat memungkinkan untuk menulis algoritma yang lebih cepat untuk beberapa kasus khusus. Tapi untuk kasus umum, sampai saat ini tidak ada yang lebih cepat dibandingkan algoritma metode quick sort c++.

Apa itu Pivot ?

Pada algoritma quick sort, pemilihan pivot ialah hal yang menentukan apakah algoritma quick sort tersebut akan memberikan performa terbaik atau terburuk. Berikut beberapa cara pemilihan pivot :


  1. Pivot merupakan elemen pertama, elemen terakhir, atau elemen tengah dalam array. Cara ini bagus jika elemen tabel tersusun secara acak, tetapi sebaliknya atau tidak bagus jika elemen tabel semula sudah terurut.
  2. Pivot dipilih dengan cara acak dari salah satu elemen array. Cara ini baik tapi belum tentu maksimal, sebab diperlukan prosedur khusus untuk menentukan pivot secara acak.
  3. Pivot adalah elemen median tabel. Cara ini yaitu cara paling bagus, sebab pada hasil partisi menghasilkan dua bagian tabel yang berukuran seimbang. Juga cara ini memberikan kompleksitas waktu yang minimum. Masalahnya, mencari median dari elemen tabel yang belum terurut adalah persoalan tersendiri


Contoh Program Sederhana Quick Sort C++

#include <iostream>
#include <conio.h>
using namespace std;
void quick_sort(int arr[], int left, int right)
{
      int i = left, j = right;int tmp;
      int pivot = arr[(left+right)/2];/* partition */
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--;
                                                    };
      }; /* recursion */
      if (left < j)
            quick_sort(arr, left, j);
      if (i < right)
            quick_sort(arr, i, right);
}
int main()
{
int i,n,data[50];
cout<<"Masukan banyak data: ";cin>>n;
for(i=0;i<n;i++)
{cout<<"Masukan data ["<<i<<"] : ";cin>>data[i];}
cout<<"\nData sebelum diurutkan: "<<endl;
for(i=0;i<n;i++)
{
cout<<data[i]<<" ";
}cout<<"\n";
quick_sort(data,0,n-1);//hasil pengurutan
cout<<"\nHasil pengurutan:\n";
{
int i;
for (i=0;i<n;i++)
cout<<data[i]<<" ";
cout<<"\n";
}getch();
}


Output Program Quick Sort C++



Contoh Program Algoritma Quick Sort C++ Sederhana

No comments for "Contoh Program Algoritma Quick Sort C++ Sederhana"