9.30.2014

Algoritma Swapping Tanpa Variabel Tambahan, Manakah yang Lebih Efisien?

Beberapa hari yang lalu, teman saya Novida memposting algoritma swapping di status facebooknya. Menurut saya algoritma ini sangat menarik, karena tidak memerlukan variabel tambahan, dimana pada umumnya algoritma swapping ini membutuhkan variabel tambahan sebagai penampung sementara.

Algoritma swapping biasanya kurang lebih seperti ini:
// initial state
a = 3;
b = 5;

// swapping
c = a;
a = b;
b = c;

// final state is a = 5, b = 3
Namun dengan menerapkan ilmu matematika sederhana, kita bisa menghemat penggunaan variabel. Berikut adalah algoritma swapping tanpa variabel tambahan:

// initial state
a = 3;
b = 5;

// swapping
a = a + b; // a = 8
b = a - b; // b = 3
a = a - b; // a = 5

// final state is a = 5, b = 3

Manakah yang lebih efisien?

Algoritma Pertama

Jika kita lihat algoritma pertama, disana terdapat 3 variabel yaitu a, b, dan c, dan dalam proses swapping nya terdapat 3 assignment. Secara penggunaan variabel, memang algoritma ini lebih banyak dibandingkan algoritma kedua. Namun, pada proses pengerjaannya, algoritma ini lebih simple karena hanya ada 3 assignment untuk melakukan proses swapping. Bagaimana dengan algoritma kedua? kita lihat selanjutnya.

Algoritma Kedua

Pada algoritma kedua, variabel yang digunakan ada 2 yaitu a dan b. Namun dalam proses swappingnya, algoritma ini memakan lebih banyak proses. Mengapa bisa demikian? Karena setiap assignment pada suatu variabel terdapat proses matematis, dimana proses tersebut merupakan proses terpisah dari proses assignment.

Kita ambil contoh a = a + b. Proses ini dalam pengerjaannya terbagi menjadi 2 proses. Pertama, program akan melakukan penjumlahan a dan b terlebih dahulu. Kemudian kedua, hasilnya akan dimasukan ke variabel a. Berbeda dengan algoritma pertama (c = a), dimana proses tersebut hanya melakukan proses pemindahan nilai variabel.

Bila dihitung, algoritma kedua ini memiliki 6 proses pengerjaan yang dilakukan untuk melakukan swapping variabel.

Kesimpulan

Proses itu memakan waktu, sedangkan variabel itu memakan tempat (dalam hal ini memori). Masing-masing algoritma memiliki kekurangan dan kelebihan, hanya tinggal menyesuaikan dengan kebutuhan kita masing-masing.

4 comments:

  1. Mantap! setuju sama setiap narasinya ka :)))

    ReplyDelete
  2. wah makasih nov (Y) , mulai blogging lagi nih udah lama haha

    ReplyDelete
  3. Kalo saya akan selalu memilih untuk mengorbankan tempat (dalam hal ini memory) , karena tempat sekarang ini relative tidak menjadi issue. Sedangkan waktu kita akan selalu mencoba untuk mempersingkat. Well that's just an opinion, nice explanation btw. :)

    ReplyDelete
  4. @kang faridzi: setuju kang! haha nuhun :D

    ReplyDelete