Implementasi Quick Sort Dengan Binary Search di C

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.

Baca Selanjutnya

Contoh Sederhana Pengendalian Program Dengan If Else

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 :)

Baca Selanjutnya

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...

Baca Selanjutnya

Pengurutan Data Random Dengan Insertion Sort di C

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

Baca Selanjutnya

Belajar Perulangan (looping) dan Contoh If else

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

Baca Selanjutnya

Program C Untuk Mengurutkan Data Dengan Selection Sort

Pada postingan sebelumnya sudah dibahas mengenai algoritma dan contoh program mengurutkan data menggunakan metode Bubble Sort. Nah postingan kali ini membahas pengurutan data secara ascending menggunakan metode sorting selection Sort. Jika masih belum mengerti algoritma Selection Sort, dapat membaca kembali artikel Algortima Sorting Metode Selection Sort. Disini hanya membahas cara implementasinya aja, berikut conth implementasi mengurutkan data menggunakan meode selection Sort.

/*--------------------------------------------------------------*/
/*-----------Nama   : Ahmad Ariful Amri ------------------------*/
/*-----------Program: Pengurutan data dengan Selection Sort ----*/
/*---------------visit: go-program.blogspot.com-----------------*/
/*--------------------------------------------------------------*/

#include <stdio.h>
 
int main()
{
   int data[100], n, i, j, position, swap;
 
   printf("Masukkan Jumlah data : ");
   scanf("%d", &n);
 
   printf("nMasukkan %d datan", n);
 
   for ( i=0 ; i<n ; i++ )
   {
   	  printf("Data ke %d : ", i+1);
      scanf("%d", &data[i]);
   }
 
   for ( i=0 ; i<(n-1) ; i++ )
   {
      position=i;
 
      for (j=i+1; j<n ; j++)
      {
         if ( data[position] > data[j] )
            position=j;
      }
      if ( position != i )
      {
         swap = data[i];
         data[i] = data[position];
         data[position] = swap;
      }
   }
 
   printf("Data setelah diurutkan:n");
 
   for ( i=0 ; i<n ; i++ )
   {
      printf("%dt", data[i]);
   }
 
   return 0;
}

Go-Program | A3

Baca Selanjutnya

Mengurutkan Data Random Dengan Bubble Sort C

Sesuai janji pada postingan sebelumnya, yaitu Algoritma dan Contoh Pengurutan dengan metode Bubble Sort. Saya akan menyajikan program sederhana C untuk mengurutkan data random secara ascending menggunakan metode bubble sort. Sangat sederhana dan hanya perlu sedikit memodifikasi dar code postingan sebelumnya, untuk mengacak data atau merandom data, dapat menggunakan fungsi rand() yang terdapat pada <stdlib.h>. Untuk mengetahui lebih lanjut mengenai random data, dapat membaca pembahasan Fungsi Rand() untuk merandom data dalam C. 

Berikut ini contoh implementasi sederhana mengurutkan data yang telah dirandom menggunakan metode Bubble Sort.

/*--------------------------------------------------------------*/
/*-----------Nama   : Ahmad Ariful Amri ------------------------*/
/*-----------Program: Mengurutkan Data Random Bubble Sort C ----*/
/*---------------visit: go-program.blogspot.com-----------------*/
/*--------------------------------------------------------------*/

#include <stdio.h>
 
int main()
{
  int array[1000], n, i, j, swap;
 
  printf("Berapa Data Yang Diinginkan? ");
  scanf("%d", &n);
  
  for (i = 0; i < n; i++)
  {
	array[i]=rand() % 1000 + 1; //data dirandom antar 1 - 1000
  }
  for (i = 0 ; i < ( n - 1 ); i++)
  {
    for (j = 0 ; j < n - i - 1; j++)
    {
      if (array[j] > array[j+1]) 
      {
        swap       = array[j];
        array[j]   = array[j+1];
        array[j+1] = swap;
      }
    }
  }
 
  printf("Data Setelah diurutkan:n");
 
  for ( i = 0 ; i < n ; i++ )
  {
     printf("%d\t", array[i]);
  }
 
  return 0;
}

Go-Program | A3

Baca Selanjutnya