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;
}

Read more

Algoritma Pengurutan Sisip (Insertion Sort)

Insertion Sort adalah algoritma pengurutan dengan menggeser elemen-elemen pada array ke tempat yang sesuai lalu taruh(sisip) elemen itu ke tempat tersebut

Langkah-langkah pengurutan sisip

// asumsikan elemen pertama sudah terurut

   // pilih elemen yang akan disisip

      // sisipkan elemen tersebut ke tempat yang sesuai dengan cara menggeser(tukar)

Menerjemahkan algoritma tersebut ke bahasa C

void insertion_sort(int data[], int length)
{
    // asumsikan elemen pertama sudah terurut
    for (int i = 1; i < length; i++)
    {
        // pilih elemen yang akan disisip
        for (int j = i; j > 0; j--)
        {
            // sisipkan elemen tersebut ke tempat yang sesuai 
            // dengan cara menggeser(tukar)
            if (data[j] < data[j - 1])
            {
                int temp = data[j];
                data[j] = data[j - 1];
                data[j - 1] = temp;
            }
            else
            {
                break;
            }
        }
    }
}

Program jadi

#include <stdio.h>

void insertion_sort(int data[], int length)
{
    for (int i = 1; i < length; i++)
    {
        for (int j = i; j > 0; j--)
        {
            if (data[j] < data[j - 1])
            {
                int temp = data[j];
                data[j] = data[j - 1];
                data[j - 1] = temp;
            }
            else
            {
                break;
            }
        }
    }
}

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]);
    }

    insertion_sort(data, num);

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

Read more

Algoritma Pengurutan Seleksi (Selection Sort)

 

Selection sort adalah algoritma pengurutan dengan mencari elemen terkecil pada array, lalu elemen tersebut ditaruh ke indeks paling kiri dalam sebuah array. Langkah tersebut dilakukan berulang-ulang sampai array tersebut terurut.

Langkah - langkah pengurutan seleksi

// asumsikan elemen pertama dalam array adalah elemen dengan angka terkecil, 
// simpan nilai dan indeks elemen tersebut ke dalam variabel sementara

// dengan pengulangan
// cek satu per satu elemen pada array apakah ada yang lebih kecil dari elemen pertama

   // jika iya, simpan nilai dan indeks elemen tersebut ke dalam variabel sementara

// tukarkan elemen yang lebih kecil tersebut 
// dengan elemen pertama(paling kiri) dalam pengulangan

// ulangi langkah-langkah tersebut hingga semua elemen terurut 

Menerjemahkan algoritma tersebut ke bahasa C

// asumsikan elemen pertama dalam array adalah elemen dengan angka terkecil, 
// simpan nilai dan indeks elemen tersebut ke dalam variabel sementara
int smallest = data[i];
int smallest_index = i;

// dengan pengulangan
// cek satu per satu elemen pada array apakah ada yang lebih kecil dari elemen pertama
for (int j = i; j < length; j++)
{
   if (data[j] < smallest)
   {
      // jika iya, simpan nilai dan indeks elemen tersebut ke dalam variabel sementara
      smallest = data[j];
      smallest_index = j;
   }
}

 

// tukarkan elemen yang lebih kecil tersebut 
// dengan elemen pertama(paling kiri) dalam pengulangan
int temp = data[i];
data[i] = smallest;
data[smallest_index] = temp;

Fungsi jadi

void selection_sort(int data[], int length)
{
    for (int i = 0; i < length; i++)
    {
        // asumsikan elemen pertama dalam array adalah elemen dengan angka terkecil, 
        // simpan nilai dan indeks elemen tersebut ke dalam variabel sementara
        int smallest = data[i];
        int smallest_index = i;

        // dengan pengulangan
        // cek satu per satu elemen pada array 
apakah ada yang lebih kecil dari elemen pertama
        for (int j = i; j < length; j++)
        {
            if (data[j] < smallest)
            {
                // jika iya, simpan nilai dan indeks elemen tersebut ke 
dalam variabel sementara
                smallest = data[j];
                smallest_index = j;
            }
        }

        // tukarkan elemen yang lebih kecil tersebut 
        // dengan elemen pertama(paling kiri) dalam pengulangan
        int temp = data[i];
        data[i] = smallest;
        data[smallest_index] = temp;
    }
    // ulangi langkah-langkah tersebut hingga semua elemen terurut
}

Program jadi

#include <stdio.h>

void selection_sort(int data[], int length)
{
    for (int i = 0; i < length; i++)
    {
        int smallest = data[i];
        int smallest_index = i;

        for (int j = i; j < length; j++)
        {
            if (data[j] < smallest)
            {
                smallest = data[j];
                smallest_index = j;
            }
        }

        int temp = data[i];
        data[i] = smallest;
        data[smallest_index] = temp;
    }
}

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]);
    }

    selection_sort(data, num);

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

    return 0;
}

Read more

Materi Pemrograman Bahasa C

Materi bahasa pemrograman C yang sudah saya susun sedemikian rupa, silahkan dipelajari dan dipahami. Susunan materi ini akan terus di-update dengan materi baru di waktu yang akan datang.
Semoga bermanfaat^^
 
I/O

Input/Output Penjumlahan Dua Variabel

Control Flow

Perkondisian dengan If - Else If - Else
Perkondisian dengan Switch - Case
Pengulangan dengan For
Pengulangan dengan While
Pengulangan dengan Do - While

Function & Procedure and Scope

Fungsi dan Prosedur 1
Fungsi dan Prosedur 2
Scope
Recursive

Array & Pointers

Array
Matrix

Linux C Programming

Compiling
Debugging
Command-line Arguments

Sorting

Bubble Sort
Selection Sort
Insertion Sort
Shellsort
Quicksort 

Struktur Data

Stacks
Queues 
Linked List

Read more

Debugging Program C dengan GDB di Linux

GDB(GNU Project Debugger) merupakan tool yang dipakai untuk mengecek lebih dalam kode-kode program yang kita buat.
Biasanya kita mengecek error program dengan cara mengira-ngira dan menebak-nebak. Cara seperti itu sangat memakan energi dan waktu, apa lagi kalau program yang terdiri dari beberapa ribu bahkan diatas puluhan ribu baris kode. Nah, disinilah GDB akan membantu kita mempermudah proses men-debug sebuah program.

Kita akan memakai tool ini untuk debugging program binary search di bawah ini.

#include <stdio.h>

void binary_search(int data[], int length, int key)
{
    int start = 0;
    int end = length - 1;
    
    while (end >= start)
    {
        int current = (end + start) / 2;
        if (data[current] == key)
        {
            printf("%d ditemukan pada indeks ke-%d\n", key, current);
            return;
        }
        else if (data[current] > key)
        {
            end = current - 1;
        }
        else
        {
            start = current + 1;
        }
    }
    
    printf("Angka tidak ditemukan!\n");
    return;
}
 
int main()
{
    int num;
    printf("Masukkan banyaknya data: ");
    scanf("%d", &num);
    
    int data[num];
    for (int i = 0; i < num; i++)
    {
        printf("Angka ke-%d: ", i);
        scanf("%d", &data[i]);
    }
    
    int key;
    printf("Ketik angka yang ingin dicari: ");
    scanf("%d", &key);
    
    binary_search(data, num, key);
    
    return 0;
}

Simpan kode program tersebut dengan nama binary_search.c lalu di-compile dengan command make. Sebelum di-compile, edit dahulu pada file make yang telah dibuat terdahulu dengan menambahkan flag -ggdb3 sehingga makefile nya menjadi seperti ini.(Baca: Pemrograman C di Linux)

CC=clang

CFLAGS= -ggdb3 -std=c99 -Wall -Werror

Kemudian compile program tersebut dengan command make binary_search.

Kita mulai proses debugging program.
1. Pada terminal, ketik.

gdb ./binary_search

Sehingga akan muncul tampilan seperti ini.

2. Ketik break main agar gdb memulai mengecek program dari main()

Bisa dilihat pada tulisan line 33, karena main() dimulai pada baris ke-33, berarti gdb akan start pada baris ke-33.

3. Ketik run untuk menjalankan program, bisa juga dengan hanya mengetik r.

 GDB akan menampilkan kode program tersebut baris per baris, pada gambar terlihat kode program pada baris ke-33.

4. Ketik next untuk lanjut ke baris selanjutnya, bisa juga dengan hanya mengetik n.

GDB sampai pada baris ke-34 dimana terdapat scanf yang berfungsi menerima input dari user, sehingga muncul tampilan seperti di atas. Masukkan saja data sebanyak 5 data.

5. Karena kita sudah memasukkan nilai 5 pada variabel num, kita bisa mengecek nilai pada variabel tersebut dengan command.

print nama_variabel

Karena variabel tersebut bernama num, maka kita mengetik command print num sehingga akan muncul tampilan seperti ini.

6. Ketik next atau n sampai menyentuh baris yang terdapat fungsi binary_search(), ketik n untuk lanjut ke baris berikutnya, atau ketik step atau s untuk "memasukki" fungsi tersebut dan melihat kode-kode di dalamnya.

Bisa dilihat, gdb langsung "lompat" ke baris ke-5 dimana fungsi binary_search() dimulai, dan juga ditampilkan nilai-nilai yang dimasukkan ke dalam parameter-parameter pada fungsi tersebut. Parameter data berupa array sehingga yang tampil adalah alamat memory dari variabel array data tersebut, sedangkan parameter length bernilai 5 karena kita memasukkan variabel num di dalamnya, dan juga parameter key benilai 7 karena kita memasukkan variabel key di dalamnya.

7. Kita juga bisa melihat nilai-nilai variabel pada scope tertentu dengan command info locals. Misalnya ketika kita berada pada scope fungsi binary_search(), ketika kita mengetik info locals maka akan diperlihatkan nilai-nilai variabel yang ada pada scope fungsi tersebut. (Baca: Konsep Scope dalam Pemrograman C)

Nilai-nilai yang tampil adalah nilai variabel pada scope lokal di binary_search(), tetapi bukan pada scope while yang terdapat di dalamnya.


Nah, dari percobaan diatas kita sudah mengetahui fungsi-fungsi command ini.

run             Menjalankan program
next            Ke baris kode selanjutnya
print           Menampilkan nilai pada sebuah variabel
step            Melangkah masuk ke dalam sebuah fungsi/sub-program
info locals     Menampilkan nilai-nilai variabel pada scope tertentu

Sekian, semoga bermanfaat.

Read more

Command-line Arguments

Biasanya kita memberi nilai dari main() pada sebuah sub-program melalui parameter, tapi bisakah kita memberi nilai pada fungsi main() itu sendiri?
Disinilah gunanya Command-line Arguments, ialah argumen(nilai) yang kita beri melalui sistem operasi seperti Linux ke sebuah program.
Pertama-tama kita harus mengetahui dulu deklarasi parameter pada fungsi main(). Biasanya kita menulis seperti ini.

int main()
{

}

Untuk dapat menggunakan command-line arguments, kita mendeklarasikan fungsi main() seperti ini.

int main(int argc, char* argv[])
{

}

Contoh program sederhana.

#include <stdio.h>

int main(int argc, char* argv[])
{
   for (int i = 0; i < argc; i++)
   {
    printf("argv[%d]: %s\n", i, argv[i]);
   }

   return 0;
}

Program tersebut kita compile melalui terminal(ingat? Pemrograman C di Linux), lalu kemudian di-eksekusi seperti biasa dengan command ini.

./nama_program

Misalnya saya menamai file program tersebut cmdline.c, maka di-eksekusi seperti ini.

./cmdline

Dan outputnya akan seperti ini.

Misal saya beri nilai pada saat eksekusi melalui terminal seperti ini.

./cmdline azhary arliansyah

Maka outputnya akan seperti ini.

Bisa kita analisis, nilai variabel argc adalah jumlah kata yang kita ketik pada terminal(dalam hal ini 3, yaitu ./cmdline, azhary, arliansyah). Lalu kata(string) tersebut disimpan pada variabel array argv.

Sekian, semoga bermanfaat !

Read more

Ternary Operator dan Konsep Rekursifitas pada Bahasa C

Pertama-tama, kita ingat kembali tentang kerangka if-else

if (/* condition */)
{
   // TODO
}
else
{
   // TODO
}

Kita bisa menulisnya dengan kerangka sintaks yang lain seperti ini

(/* condition */) ? /* TODO */ : /* TODO */;

Perhatikan baik-baik, tanda ? sama artinya dengan if dan tanda : sama artinya dengan else.
Contoh.

if (*value == value[0])
{
   printf("Sama\n");
}
else
{
   printf("Tidak sama\n");
}

Dikonversikan memakai ternary operator menjadi seperti ini

(*value == value[0]) ? printf("Sama\n") : printf("Tidak sama\n");

Kita lanjut ke konsep rekursifitas, apa itu fungsi rekursif ?
Fungsi rekursif adalah fungsi yang "memanggil" dirinya sendiri, bingung ?
Lihat contoh kerangka fungsinya di bawah ini

int fungsi()
{
   fungsi();
}

Tetapi kalo dipikir-pikir, fungsi itu seakan-akan memanggil dirinya sendiri terus-menerus tanpa ada ujungnya. Nah, agar fungsi tersebut dapat berhenti, kita membuat suatu Base Case atau kondisi dimana fungsi rekursif tersebut berhenti berjalan. Seperti pada contoh fungsi faktorial berikut ini.

int faktorial(int n)
{
   if (n == 0) // BASE CASE
   {
      return 1;
   }

   return n * faktorial(n - 1);
}

Sekarang, mari kita coba skill baru kita untuk membuat kode yang sangat sederhana tapi powerful.
Lihat contoh fungsi linear search ini.

int linear_search(int data[], int length, int key)
{
   for (int i = 0; i < length; i++)
   {
      if (data[i] == key)
      {
         return i;
      }
   }

   return -1;
}

Kita bisa membuat fungsi linear search di atas hanya dengan menulis kode seperti ini.

int linear_search(int data[], int length, int key)
{
   return (data[length - 1] == key) ? length - 1 : 
   ((length < 0) ? -1 : linear_search(data, length - 1, key));
}

Sekarang kita bisa membuat fungsi linear search hanya dengan sedikit baris kode, cool kan ? :D

Read more