Quicksort (Recursive Version)

Quicksort adalah algoritma pengurutan dengan mengurutkan data-data pada sub-array yang dibatasi oleh sebuah elemen yang bisa kita sebut sebagai pivot.

http://en.wikipedia.org/wiki/Quicksort

Langkah-langkah pengurutan dengan metode Quick Sort

// cek jika ukuran array kurang atau sama dengan 0 (BASE CASE!!)

// pilih data pertama dalam sebuah pengurutan sebagai pivot

// simpan indeks data pertama tersebut ke variabel sementara

// lakukan pengurutan data pada sebuah array dari start ke end

   // jika data yang diurut lebih kecil dari pivot

      // tambahkan 1 ke indeks sementara

      // tukar data pada indeks sementara
      // dengan data yang ingin diurutkan

// tukar data pertama dengan data pada indeks sementara

// lakukan langkah-langkah diatas secara rekursif

Menerjemahkan algoritma tersebut ke bahasa C

// cek jika ukuran array kurang atau sama dengan 0 (BASE CASE!!)
if (start >= end)
{
 return;
}

// pilih data pertama pada ukuran sebuah array sebagai pivot
int pivot = data[start];
 
// simpan indeks data pertama tersebut ke variabel sementara
int store_index = start;

// lakukan pengurutan data pada sebuah array dari start ke end
for (int i = start; i <= end; i++)
{
 // jika data yang diurut lebih kecil dari pivot
 if (data[i] < pivot)
 {
  // tambahkan 1 ke indeks sementara
  store_index = store_index + 1;
  
  // tukar data pada indeks sementara tersebut dengan data yang ingin diurutkan
  tukar(&data[store_index], &data[i]);
 }
}

// tukar data pertama dengan data pada indeks sementara dalam sebuah pengurutan
tukar(&data[store_index], &data[start]);

// lakukan langkah-langkah diatas secara rekursif
quick_sort(data, start, store_index - 1);
quick_sort(data, store_index + 1, end);

Fungsi jadi

void quick_sort(int data[], int start, int end)
{
 // cek jika ukuran array kurang atau sama dengan 0 (BASE CASE!!)
 if (start >= end)
 {
  return;
 }

 // pilih data pertama pada ukuran sebuah array sebagai pivot
 int pivot = data[start];
 
 // simpan indeks data pertama tersebut ke variabel sementara
 int store_index = start;

 // lakukan pengurutan data pada sebuah array dari start ke end
 for (int i = start; i <= end; i++)
 {
  // jika data yang diurut lebih kecil dari pivot
  if (data[i] < pivot)
  {
   // tambahkan 1 ke indeks sementara
   store_index = store_index + 1;
   
   // tukar data pada indeks sementara tersebut dengan data yang 
                           ingin diurutkan
   tukar(&data[store_index], &data[i]);
  }
 }

 // tukar data pertama dengan data pada indeks sementara dalam sebuah pengurutan
 tukar(&data[store_index], &data[start]);

 // lakukan langkah-langkah diatas secara rekursif
 quick_sort(data, start, store_index - 1);
 quick_sort(data, store_index + 1, end);
}

Program jadi

#include <stdio.h>

void tukar(int* x, int* y)
{
 int temp = *x;
 *x = *y;
 *y = temp;
}

void quick_sort(int data[], int start, int end)
{
 // cek jika ukuran array kurang atau sama dengan 0 (BASE CASE!!)
 if (start >= end)
 {
  return;
 }

 // pilih data pertama pada ukuran sebuah array sebagai pivot
 int pivot = data[start];
 
 // simpan indeks data pertama tersebut ke variabel sementara
 int store_index = start;

 // lakukan pengurutan data pada sebuah array dari start ke end
 for (int i = start; i <= end; i++)
 {
  // jika data yang diurut lebih kecil dari pivot
  if (data[i] < pivot)
  {
   // tambahkan 1 ke indeks sementara
   store_index = store_index + 1;
   
   // tukar data pada indeks sementara tersebut dengan data yang 
                           ingin diurutkan
   tukar(&data[store_index], &data[i]);
  }
 }

 // tukar data pertama dengan data pada indeks sementara dalam sebuah pengurutan
 tukar(&data[store_index], &data[start]);

 // lakukan langkah-langkah diatas secara rekursif
 quick_sort(data, start, store_index - 1);
 quick_sort(data, store_index + 1, end);
}

int main()
{
 int num;
 printf("Masukkan banyaknya data: ");
 scanf("%d", &num);

 int data[num];
 for (int i = 0; i < num; i++)
 {
  printf("Data ke-%d: ", i);
  scanf("%d", &data[i]);
 }

 quick_sort(data, 0, num - 1);

 for (int i = 0; i < num; i++)
 {
  printf("%d ", data[i]);
 }
 return 0;
}

autodika

Autodika.com menyediakan jawaban serta materi seputar tugas kuliah Manajemen Informatika, Sistem Informasi, Teknik Informatika dan berbagai macam tugas kuliah yang berkaitan tentang teknologi.

Share this post