Mau Dapat Uang Silahkan Daftar

News Update :
Home » , » Implementasi Quick Sort Dengan Binary Search di C

Implementasi Quick Sort Dengan Binary Search di C

Penulis : Unknown on Thursday, January 31, 2013 | 6:29 AM

berikut ini salah satu tugas yang lumayan sangat gamapang dari tugas-tugas pemrograman lainnya. permasalahan disini yaitu mencari sebuah angka yang diinput user dari sejumlah data yang telah dirandom kemudian diurutkan menggunakan quicksort. Jadi bisa dikatakan ini gabungan dari quick sort dengan binary search. Kira kira berikut ini penampakan hasil yang diinginkan.

http://go-program.blogspot.com/2013/01/implementasi-quick-sort-dengan-binary-di-c.html


Tugas ini saya katakan sangat mudah karena source code yang diperlukan sudah ada semuanya, namun sebenarnya akan susah jika dipahami source code baris-perbarisnya. apalagi adanya fungsi rekusif dalam quicksort dan binary search Lumayan memusingkan. Berikut ini source code implementasi dari quick sort dengan binary search seperti gambar diatas.

/*--------------------------------------------------------------------*/
/*-------------Nama : Ahmad Ariful Amri ----------------------------*/
/*-------------Program: Quick sort dan implementasi Binary Search-----*/
/*--------------------------------------------------------------------*/

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

/*Prototype dari metode sorting quick sort*/
void quickSort( int[], int, int);
int partition( int[], int, int);

int main()
{
int data[100000], i, n, menu, item, mid, top, bottom;
time_t start, stop;//sebagai penghitung waktu
printf("Masukkan Jumlah Bilangan (n): ");
scanf("%d", &n);

for (i = 0; i < n; i++)
{
data[i]=rand() % n + 1;
}
printf("Random data dalam array selesain");

time(&start);//Mulai menghitung waktu
quickSort( data, 0, n);
//Untuk menampilkan data yang telah diurutkan (Jika diperlukan)
//printf("Data setelah diurutkan dengan QUICK SORT :n");
//for(i = 0; i < n; ++i)
//{
// printf("%dt", data[i]);
//}
time(&stop);//Berhenti menghitung waktu
printf("Data sudah diurutkan menggunakan metode QUICK SORT :n");
printf("nnWaktu yang dibutuhkan untuk mengurutkan: %.0f detik. nnn", difftime(stop, start));/*Menampilkan total waktu yang dibutuhkan*/

do
{
printf("|==============================================================|n");
printf("|---Mencari data yang telah diurutkan menggunakan Quick Sort---|n");
printf("|==============================================================|n");
printf("|Pilihan: |n");
printf("|1) Mencari data dengan BINARY SEARCH dan menampilkan hasilnya |n");
printf("|2) Random ulang data dalam array |n");
printf("|3) Selesai (EXIT) |n");
printf("|--------------------------------------------------------------|n");
printf("|Pilihan anda: ");
scanf("%d", &menu);
printf("nn");
switch(menu)
{
/***************************INSERTION SORT*************************/
case 1:
printf("Masukkan data yang ingin dicari :");
scanf("%d",&item);
bottom = 1;
top = n;

do
{
mid = (bottom + top) / 2;
if (item < data[mid])
{
top = mid - 1;
}
else if (item > data[mid])
{
bottom = mid + 1;
}
}
while (item != data[mid] && bottom <= top);

if (item == data[mid])
{
printf("nNilai %d Ditemukan pada indeks ke: %dnnn", item, mid + 1);
}
else
{
printf("nPencarian gagal, %d Tidak ditemukannn", item);
}
break;
/********************************Akhir dari Binary Search ***********************/
case 2:
printf("Masukkan jumlah bilangan (n) :");
scanf("%d", &n);
/*Memasukkan jumlah data(bilangan) kemudian akan dirandom*/
for(i=0; i<n; i++)
{
data[i]=rand() % n + 1; //merandom data dari 1 - n dan disimpan ke array
}
printf("Random data dalam array selesainn");

time(&start);//Mulai menghitung waktu
quickSort( data, 0, n);
//Untuk menampilkan data yang telah diurutkan (Jika diperlukan)
//printf("Data setelah diurutkan dengan QUICK SORT :n");
//for(i = 0; i < n; ++i)
//{
// printf("%dt", data[i]);
//}
time(&stop);//Berhenti menghitung waktu
printf("Data sudah diurutkan menggunakan metode QUICK SORT :n");
printf("nnWaktu yang dibutuhkan untuk mengurutkan: %.0f detik. nnn", difftime(stop, start));/*Menampilkan total waktu yang dibutuhkan*/

break;
case 3:break;
}
/*Jika memasukkan menu yang tidak sesuai dengan pilihan*/
if(menu!=1 && menu!=2 && menu!=3)
{
printf("Maaf..Anda Salah Memasukkan Pilihan!!!nPilihan anda nomor %d TIDAK ada pada menu", menu);
printf("nSilahkan pilih menu dibawah dari 1 - 3, Terima Kasih :)nn");
}
}while(menu != 3);

return EXIT_SUCCESS;
}

void quickSort( int data[], int l, int r)
{
int j;
if( l < r )
{
// divide and conquer
j = partition( data, l, r);
quickSort( data, l, j-1);
quickSort( data, j+1, r);
}
}

/*Pembagian partisi*/
int partition( int data[], int l, int r)
{
int pivot, i, j, t;
pivot = data[l];
i = l; j = r+1;

while( 1)
{
do ++i; while( data[i] <= pivot && i <= r );
do --j; while( data[j] > pivot );
if( i >= j ) break;
t = data[i]; data[i] = data[j]; data[j] = t;
}
t = data[l]; data[l] = data[j]; data[j] = t;
return j;
}

Agar lebih mudah untuk di trace. silahkan copas source code diatas ke notepad++ atau pengolah kata kesayangan anda lainnya.
Share this article :

Post a Comment

 
Company Info | Contact Us | Privacy policy | Term of use | Widget | Advertise with Us | Site map
Copyright © 2011. Jendela Dunia . All Rights Reserved.
Design Template by panjz-online | Support by creating website | Powered by Blogger