TUGAZ SORTING/Quick sort

Sorting

Sorting atau Algoritma pengurutan adalah algoritma yang meletakkan elemen-elemen suatu kumpulan data dalam urutan tertentu. Ada 2 jenis sorting : Ascending (naik) & Descending (turun).

Klasifikasi AlgoritmaPengurutan (sorting)

QUICK SORT

Quick sort banyak digunakan utk proses sorting,karena:

�� merupakan proses sorting yang umum digunakan

�� mudah untuk diimplementasikan

�� Prosesnya sangat cepat

QUICK SORT Membandingkan suatu elemen (disebut pivot) dengan elemen yang lain dan menyusunnya sedemikian rupa sehingga elemen- elemen lain yang lebih kecil daripada tersebut terletak di sebelah kirinya dan elemen-elemen lain yang lebih besar daripada pivot tersebut terletak di sebelah kanannya. Sehingga dengan demikian telah terbntuk dua sublist, yang terletak di sebelah kiri dan kanan dari pivot. Lalu pada sublist kiri dan sublist kanan kita anggap sebuah list baru dan kita kerjakan proses yang sama seperti sebelumnya.

Ilustrasinya :

Proses : Bilangan yang di dalam kurung merupakan pivot Persegi panjang yang digambarkan dengan garis terputus-putus menunjukkan sublist. i bergerak dari sudut kiri ke kanan sampai mendapatkan nilai yang >= pivot. j bergerak dari sudut kanan ke kiri.

Quick1

i berhenti pada index ke-1 karena langsung mendapatkan nilai yang > dari pivot (15). j Berhenti pada index ke-6 karena juga langsung mendapatkan nilai yang < dari pivot (15).

quick2


i berhenti pada index ke-3 (pivot) karena tidak menemukan bilangan yang > dari pivot. j berhenti pada index k-5 menunjuk pada nilai yang < pivot.

Quick3Quick4

Programnya :

#include <iostream.h>

#include <conio.h>

int data[100],data2[100];

int n;

void tukar(int a,int b)

{

int t;

t = data[b];

data[b] = data[a];

data[a] = t;

}

void QuickSort(int L, int R)

{

int i, j;

int mid;

i = L;

j = R;

mid = data[(L+R) / 2];

do

{

while (data[i] < mid) i++;

while (data[j] > mid) j–;

if (i <= j)

{

tukar(i,j);

i++;

j–;

};

} while (i < j);

if (L < j) QuickSort(L, j);

if (i < R) QuickSort(i, R);

}

void Input()

{

cout<<“Masukkan jumlah data = “; cin>>n;

for(int i=0;i<n;i++)

{

cout<<“Masukkan data ke-“<<(i+1)<<” = “; cin>>data[i];

data2[i] = data[i];

}

}

void Tampil()

{

cout<<“Data : “<<endl;

for(int i=0;i<n;i++)

{

cout<<data[i]<<” “;

}

cout<<endl;

}

void AcakLagi()

{

for(int i=0;i<n;i++)

{

data[i] = data2[i];

}

cout<<“Data sudah teracak!”<<endl;

}

void main()

{

int pil;

clrscr();

do

{

clrscr();

cout<<“Program Sorting !!!”<<endl;

cout<<“*********************************************”<<endl;

cout<<” 1. Input Data”<<endl;

cout<<” 2. Quick Sort”<<endl;

cout<<” 3. Tampilkan Data”<<endl;

cout<<” 4. Acak Data”<<endl;

cout<<” 5. Exit”<<endl;

cout<<” Pilihan Anda = “; cin>>pil;

switch(pil)

{

case 1:Input(); break;

case 2:QuickSort(0,n-1);

cout<<“quick sort selesai!”<<endl;

break;

case 3:Tampil(); break;

case 4:AcakLagi(); break;

}

getch();

}while(pil!=5);

}

~ by rusdia on July 1, 2009.

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: