jenis metode Quick sort pada c++ |sorting c++

SOBAT WINDOWS

1 Mar, 2021

Quick Sort

Quick Sort merupakan metode tercepat dalam proses pengurutan data dengan menggunakan prinsip rekursif. Metode ini menggunakan strategi “pecah-belah” dengan mekanisme berikut ini.

Misalkan kita mempunyai array Nilai[k..l]. Array dipartisi menjadi dua bagian array kiri Nilai[k..m] dan array kanan Nilai[m+1..l]. Dasar mempartisi array menjadi dua adalah dengan mengambil elemen pertama sebagai elemen pivot. Letakkan semua elemen array yang lebih kecil dari pivot ke sebelah pivot dan semua elemen array yang lebih besar dari pivot ke sebelah kanan pivot. Elemen-elemen yang di sebelah kiri elemen pivot merupakan elemen-elemen array Nilai[k..m] sedangkan elemen-elemen array Nilai[m+2..l] adalah semua elemen yang lebih besar dari pivot. Lakukan hal yang sama seperti di atas terhadap array Nilai[k..m] dan Nilai[m+1..l] hingga tidak dapat dipartisi lagi.

Contoh: Misalkan kita mempunyai array Nilai sebanyak 8 elemen akan diurutkan secara menaik dengan metode Maximum Sort: 25, 72, 30, 45, 20, 15, 6, 50. Urutan langkah pengurutannya seperti berikut dan programnya dapat dilihat pada program Lat_Sorting_02a.

Ambil elemen pertama sebagai elemen pivot, letakkan semua elemen array yang lebih kecil dari pivot ke sebelah kiri elemen pivot dan letakkan semua elemen array yang lebih besar dari pivot ke sebelah kanan elemen pivot.

Gunakan array Nilai[0..2]. Ambil elemen pertama sebagai elemen pivot, letakkan semua elemen array yang lebih kecil dari pivot ke sebelah kiri elemen pivot dan letakkan semua elemen array yang lebih besar dari pivot ke sebelah kanan elemen pivot.

Perhatikan array Nilai[2] tidak dapat lagi dipartisi maka berhenti sampai disana.

Gunakan array Nilai[0..1]. Ambil elemen pertama sebagai elemen pivot, letakkan semua elemen array yang lebih kecil dari pivot ke sebelah kiri elemen pivot dan letakkan semua elemen array yang lebih besar dari pivot ke sebelah kanan elemen pivot.

Perhatikan array Nilai[0] dan Nilai[1] tidak dapat lagi dipartisi maka berhenti sampai di sana.

Gunakan array Nilai[4..7]. Ambil elemen pertama sebagai elemen pivot, letakkan semua elemen array yang lebih kecil dari pivot ke sebelah kiri elemen pivot dan letakkan semua elemen array yang lebih besar dari pivot ke sebelah kanan elemen pivot.

Gunakan array Nilai[4..6]. Ambil elemen pertama sebagai elemen pivot, letakkan semua elemen array yang lebih kecil dari pivot ke sebelah kiri elemen pivot dan letakkan semua elemen array yang lebih besar dari pivot ke sebelah kanan elemen pivot.

Gunakan array Nilai[5..6]. Ambil elemen pertama sebagai elemen pivot, letakkan semua elemen array yang lebih kecil dari pivot ke sebelah kiri elemen pivot dan letakkan semua elemen array yang lebih besar dari pivot ke sebelah kanan elemen pivot.

Karena semua elemen array sudah tidak dapat dipartisi maka proses pengurutan berakhir dan hasilnya diperoleh seperti berikut (gabungkan mulai Nilai[0] hingga Nilai[7]):

Untuk melakukan proses pengurutan data secara menurun dengan metode Quick Sort dilakukan dengan meletakkan semua elemen array yang lebih kecil dari pivot ke sebelah kanan pivot dan semua elemen array yang lebih besar dari pivot ke sebelah kiri pivot.

/* Program Pengurutan Metode Quick Sort
  Pengurutan Secara Menaik
  Nama File : Lat_Sorting_02a */
  
#include<iostream.h>
#include<conio.h>
#include<iomanip.h>
void Cetak(int data[], int n)
{
  int i;
  for(i=0; i<n; i++)
    cout<<setw(3)<<data[i];
  cout<<"\n";
}
int Partisi(int data[], int p, int r)
{
  int x, i, j, temp;
  x = data[p];
  i=p;
  j=r;
  while(l)
  {
    while(data[j]>x)
      j--;
    while(data[i]<x)
      i++;
    if(i<j)
    {
      temp = data[i];
      data[i] = data[j];
      data[j] = temp;
    }
    else
      return j;
  }
}
void Quick_Sort(int data[], int p, int r)
{
  int q;
  if(p<r)
  {
    q=Partisi(data, p, r+1);
    Quick_Sort(data, p, 1);
    Quick_Sort(data, q+1, r);
  }
}
void main()
{
  int Nilai[20];
  int i, N;
  cout<<"Masukkan Banyak Bilangan : ";
  cin>>N;
  for(i=0; i<N; i++)
  {
    cout<<"Elemen ke-"<<i<<" : ";
    cin>>Nilai[i];
  }
  cout<<"\nData Sebelum di urut : ";
  Cetak(Nilai, N);
  cout<<endl;
  Quick_Sort(Nilai, 0, N-1);
  cout<<"\nData Setelah di urut : ";
  Cetak(Nilai,N);
  getch();
}