Implementasi Quick Sort Dengan Binary Search di C

Thursday, January 31, 2013

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.

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.

comments | | Read More...

Contoh Sederhana Pengendalian Program Dengan If Else

Friday, January 25, 2013

Pengendalian program yang akan dibahas kali ini sangatlah sederhana, pengendalian program dengan if else. Untuk pengetahuan dasarnya silahkan baca postingan "Penggunaan if, else dan else if" Dibalik kesederhanaannya, pengendalian dengan if else ini oke banget dan sangat berguna dalam keseharian coding. Berikut contoh sederhana dalam penggunaan if else.

/*-----------------------------------------------------*/
/*-----Nama   : Ahmad Ariful Amri ---------------------*/
/*-----Program: Contoh penggunaan Kontrol if else------*/  
/*------------http://go-program.blogspot.com-----------*/
/*-----------------------------------------------------*/

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

int main()
{
 int nilai;
 
 printf("Masukkan nilai : ");
 scanf("%d", &nilai);
 
 if(nilai >=85)
 {
  printf("Nilai An");
 }
 else if(nilai >=75)
 {
  printf("Nilai B+\n");
 }
 else if(nilai >=65)
 {
  printf("Nilai B\n");
 }
 else if(nilai >=55)
 {
  printf("Nilai C+\n"); 
 }
 else if(nilai >=45)
 {
  printf("Nilai C\n"); 
 }
 else if(nilai >=25)
 {
  printf("Nilai D\n"); 
 }
 else
 {
  printf("Nilai En"); 
 }
 
 return EXIT_SUCCESS;
}

Penjelasan

Seperti namanya "if" (bahasa inggris) yang dalam bahasa indonesianya "Jika". Jika sesuatu memenuhi syarat yang ada didalam if(Syarat), maka ia akan masuk kedalamnya dan mengerjakan pernyataan didalamnya. Seperti contoh, kita ambil sampel nilai yang diimputkan oleh user yaitu 50. Compiler memproses coding dari kiri atas ke kanan bawah (Kecuali ada hal lain sperti fungsi). Pertama si akan dicek pada "if" pertama yaitu nilai yang >=85. di cek apakah 50 >= 85? Tidak. Karena tidak memenuhi, lanjut lagi ke if else yang kedua >=75, belum memenuhi juga, selanjutnya apakah 50 >=65? tidak juga. Selnjutnya apakah 50 >= 55? tidak juga. Selanjutnya apakah 50 >= 45? IYA. barulah ia masuk dan melaksanakan pernyataan didalam nya. yaitu mengeprint "Nilai C".

Begitulah contoh sederhana penggunaan pengendalian program dengan "if". Semoga dapat berguna :)

comments | | Read More...

Program Sederhana C Konversi Detik Ke Menit Dan Jam

berhubung sedang kurang bergairah dalam dunia pemrograma, jadi malam ini sharing-sharing hal yang sederhana aja yaw. Kali ini akan saya posting contoh program sederhana untuk mengkonversi detik dari masukan user ke dalam satuan jam dan menit. Kalau dibayangin sepertinya mudah. inilah source code nya :)

/*----------------------------------------------------------------*/
/*-------------Nama   : Ahmad Ariful Amri ------------------------*/
/*-------------Program: Konversi detik ke menit dan jam-----------*/  
/*-----------------visit: go-program.blogspot.com-----------------*/
/*----------------------------------------------------------------*/

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

int main()
{
 int jam, menit, detik, sisa;
 printf("Jumlah detik yang diinginkan : ");
 scanf("%d", &detik);
 jam = detik/3600;
 sisa = detik%3600;
 menit = sisa / 60;
 detik = sisa % 60;
 
 printf("setara dengan %d jam %d menit %d detikn",jam,menit,detik);
 
 return EXIT_SUCCESS;
}

Gampang sekali kan? semoga bisabermanfaat ya...

comments | | Read More...

Pengurutan Data Random Dengan Insertion Sort di C

Wednesday, January 9, 2013

Tepat Pada Postingan Sebelumnya saya membahas tentang Algoritma metode pengurutan menggunakan Metode Insertion Sort. Nah disini akan diberikan contoh program untuk mengurutkan sekumpulan data yang telah dirandom menggunakan fungsi Rand() (KLIK), contoh yang saya berikan disini menggunakan bahasa C. 

/*------------------------------------------------------------------*/
/*-----------Nama   : Ahmad Ariful Amri ----------------------------*/
/*-----------Program: Pengurutan data random dengan insertion sort--*/
/*---------------------------www.go-program.blogspot.com------------*/
/*------------------------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>
 
int main()
{
  int n, data[1000], i, j, t;
 
  printf("Masukkan Jumlah data : ");
  scanf("%d", &n);
 
   for (i = 0; i < n; i++)
   {
  data[i]=rand() % 100000 + 1;
   }
 
  for (i = 1 ; i <= n - 1; i++) {
    j = i;
 
    while ( j > 0 && data[j] < data[j-1]) {
      t          = data[j];
      data[j]   = data[j-1];
      data[j-1] = t;
 
      j--;
    }
  }
 
  printf("Data setelah diurutkan:n");
 
  for (i = 0; i <= n - 1; i++) {
    printf("%dt", data[i]);
  }
 
  return 0;
}

Konsep dari program diatas, pengguna akan diminta memasukkan jumlah data yang ingin dirandom sebanyak n buah bilangan. Kebetulan ceritanya diatas saya memasukan nilai 27, yang berarti akan dirandom data sebanyak 27 angka dari angka 1 - dengan n. setelah dirandom, data/angka tersebut disimpan dalam sebuah array. pada contoh diatas, bilangan yang sudah dirandom disimpan pada array data[i]. Selanjutnya angka.bilangan yang terdapat dalam itulah yang di urutkan menggunakan meode insertion sort.

Sekian Ahmad Ariful Amri ~ Selesai

comments | | Read More...

Belajar Perulangan (looping) dan Contoh If else

Thursday, December 6, 2012

Perintah if digunakan untuk mewujudkan percabangan beryarat. Didalam bahasa C, instruksi if memiliki beberapa bentuk, yaitu:

1. Perulangan if tunggal

if (expresi) pernyataan;

Pengujian ekspresi selalu diapit dengan tanda kurung. Ekspresi dengan menggunakan operator perbandingan akan dites nilai kebenarannya apakah benar atau salah. Pernyataan berupa perintah mencetak output, proses, atau gabungan keduanya.

2. perulangan if dengan else

if(ekspresi 1) pernyataan;

else pernyataan2;

Operator lain yang sering digunakan adalah ternary (?) yang mempunyai bentuk

(ekspresi) ? pernyataan 1 : pernyataan 2;

Perintah diatas mempunyai nilai yang sama denga perintah berikut:

if(ekspresi) pernyatan 1 else pernyataan 2

3. Perulangan if dengan pilihan if lainnya

if(ekspresi 1) pernyataan 1;

else if(ekspresi 2) pernyataan 2;

else pernyataan 3;

4. Perulangan if di dalam if

if(ekspresi 1) pernyataan 1;

      if(ekspresi 2) pernyataan 2;

Contoh penggunaan perintah perulangan if adalah sebagai berikut:

/*------------------------------------------------------------*/
/*-----------Nama   : Ahmad Ariful Amri ----------------------*/
/*-----------Program: Contoh Perulangan If else dengan C------*/ 
/*---------------visit: go-program.blogspot.com---------------*/
/*------------------------------------------------------------*/

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

int main()
{
 int nilai;
 printf("Berapa nilai Kamu : ");
 scanf("%d", &nilai);
 
 if(nilai >=85)
 {
  printf("Bagus Sekali, nilai anda A\n");
 }
 else if(nilai >= 75)
 {
  printf("Mantap bro, Nilai kamu B+\n");
 }
 else if(nilai >= 65)
 {
  printf("oke bro, bagus.. nilai kamu B\n");
 }
 else if(nilai >=55)
 {
  printf("Hmm, nilai lo C+ :Dn");
 }
 else if(nilai >= 35)
 {
  printf(":{ dapet nilai D, jangan senang dulu ya\n");
 }
 else
 {
  printf("Jangan bunuh diri ya, kamu dapat E, selamatt :D\n");
 }
 
 return EXIT_SUCCESS;
}

Nah, mudah bukan? silahkan berkreasi sendiri, masih banyak perulangan lainnya yang Insya Allah akan kita bahas pada kesempatan mendatang :D

comments | | Read More...