Rosihan Ari`s Blog

Algoritma Membalik String (String Reverse)

December 20th, 2008 | by rosihanari |  Cetak Artikel Ini

Artikel ini didasari pada pertanyaan mas Tedy Winanto (sobat saya di YM). Teman saya ini bingung bagaimana caranya membalik suatu string. Dan.. karena saya telah menjanjikan pada mas Tedy kalau saya sempat, saya akan posting di blog saya ini bagaimana algoritma membalik string ini dan implementasinya ke program/script, maka saat inilah saya akan memenuhi janjinya.

OK… misalkan diberikan suatu string ‘KOMPUTER’, dan kita ingin membalik string tersebut sehingga menjadi ‘RETUPMOK’, bagaimana algoritmanya?

Ya… secara logika untuk membalik suatu string dengan panjang karakter sejumlah n, cukup menukar posisi karakter ke – 1 dengan karakter ke-n, dan karakter ke-2 ditukar posisi dengan karakter ke n-1, dst. Sekarang yang menjadi masalah adalah… sampai berapa kali proses penukaran ini dilakukan, apakah n kali? Coba kita cek proses ini bila diterapkan pada string ‘KOMPUTER’ tsb, dalam hal ini n = 8 (panjang string 8 karakter).

Penukaran ke-1, tukar posisi karakter ke-1 dg ke-8, hasilnya ‘ROMPUTEK‘
Penukaran ke-2, tukar posisi karakter ke-2 dg ke-7, hasilnya ‘REMPUTOK’
Penukaran ke-3, tukar posisi karakter ke-3 dg ke-6, hasilnya ‘RETPUMOK’
Penukaran ke-4, tukar posisi karakter ke-4 dg ke-5, hasilnya ‘RETUPMOK’
Penukaran ke-5, tukar posisi karakter ke-5 dg ke-4, hasilnya ‘RETPUMOK’
Penukaran ke-6, tukar posisi karakter ke-6 dg ke-3, hasilnya ‘REMPUTOK’
Penukaran ke-7, tukar posisi karakter ke-7 dg ke-2, hasilnya ‘ROMPUTEK’
Penukaran ke-8, tukar posisi karakter ke-8 dg ke-1, hasilnya ‘KOMPUTER‘

Bila proses penukaran dilakukan n kali, ternyata hasil akhir string tetap kembali ke string semula. So… salah donk. Dengan demikian, kita tidak bisa menulis algoritmanya sbb:

{ x adalah string yang akan ditukar }
n := length(x); { n = panjang string }
for i = 1 to n do
begin
    // tukar antara karakter ke-i dengan karakter ke- (n+1-i)
    temp := x[i];
    x[i] := x[n+1-i];
    x[n+1-1] := x[i];
end;

Jadi… sampai berapa kali proses penukarannya? Anda perhatikan pada proses penukaran tahap demi tahap di atas. Pada langkah berapakah stringnya menjadi ‘RETUPMOK’? Ya tepat sekali, yaitu pada langkah ke-4.

OK… dari contoh ini bisa kita catat, bahwa untuk n = 8, kita butuh 4 kali langkah penukaran. Sekarang bagaimana bila n = 10? Coba selidiki… dan ternyata butuh 5 kali penukaran. Nah… dari sini bisa kita simpulkan bahwa untuk n genap, proses penukaran yang dibutuhkan ada n/2 kali.

Sekarang bagaimana dengan n ganjil? Kita ambil contoh misal n = 7. Berapakah jumlah proses penukarannya? Coba selidiki… dan ternyata butuh 3 kali. Lho apa tidak 4 kali? Mmmm… untuk yang ke-4 boleh kita tidak lakukan karena karakter ke-4 adalah karakter yang berada di tengah string, so… gak perlu ditukar. Untuk n = 9, akan butuh 4 kali penukaran. dan seterusnya… Dengan demikian untuk n ganjil, proses penukaran yang dilakukan juga sejumlah n/2 kali, tapi n/2 di sini dibulatkan ke bawah.

Untuk n genap pun, jumlah proses penukaran karakter juga dapat diterapkan pembulatan ke bawah dari n/2, karena misal n= 8, dan hasil n/2 kalau dibulatkan ke bawah juga menghasilkan 4.

So… algoritma yang benar untuk membalik string adalah:

{ x adalah string yang akan ditukar }
n := length(x); { n = panjang string }
for i = 1 to floor(n/2) do {maksud floor adalah pembulatan ke bawah}
begin
    // tukar antara karakter ke-i dengan karakter ke- (n+1-i)
    temp := x[i];
    x[i] := x[n+1-i];
    x[n+1-1] := x[i];
end;

Nah… sekarang kita implementasikan algoritma di atas ke PHP. Bagaimana bentuk script untuk membalik string? O… iya… ingat bahwa dalam PHP, karakter pertama dari suatu string itu dimulai dari nomor indeks ke-0, sehingga harap hati-hati. Ini dia scriptnya:

<?php
 
$x = 'KOMPUTER';
$n = strlen($x);
for ($i = 0; $i<=floor(($n-1)/2); $i++)
{
	$temp = $x[$i];
	$x[$i] = $x[$n-1-$i];
	$x[$n-1-$i] = $temp;
}
 
echo $x;
?>

dan ini dia implementasi ke dalam program Pascal

program balikstring;
var x : string; i, n : integer; temp : char;
begin
    x := 'KOMPUTER';
    n := length(x);
    for i:=1 to trunc(n/2) do
    begin
        temp := x[i];
        x[i] := x[n+1-i];
        x[n+1-1] := x[i];
    end;
    write(x);
end.

OK deh…. demikian algoritma untuk membalik string. Mudah-mudahan ada manfaatnya.

Eh… sebelum di tutup artikel ini, cobalah cek apakah algoritma simpel berikut ini juga bisa digunakan untuk membalik string?

{ x adalah string yang akan ditukar }
n := length(x); { n = panjang string }
for i = 1 to n do
begin
    x[i] := x[n+1-i];
end;

Mmmm…. secara sekilas sih ‘kayaknya’ bisa. Tapi kalau Anda yakin jawabannya ‘bisa’, silakan buat ke dalam program algoritma tersebut dan lihatlah hasilnya. Tentu hasilnya di luar dugaan dan Anda akan dibuat tercengang dibuatnya. Kok bisa ya?

Oya, satu lagi, khusus di PHP, Anda tidak perlu repot-repot membuat script untuk membalik string karena telah disediakan function khusus untuk melakukan hal itu. Function yang dimaksud adalah strrev(). Berikut ini contoh penggunaannya:

<?php
echo strrev("Hello world!"); // outputnya "!dlrow olleH"
?>

OK… met membolak-balik string ya.

Beberapa artikel terkait

• Algoritma Mengambil Substring
• Membuat Kalkulator Berbasis String dengan PHP
• Beberapa Function Pengolah String di PHP (Bag. 1)
• Algoritma Sorting dan Implementasinya
• Teknik Untuk Memecah String Menjadi Substring dengan Jumlah Karakter Sama
• Cara Membalik Urutan Postingan di Wordpress
• Algoritma Mencari Statistik Huruf
• Beberapa Function Pengolah String di MySQL (Bag. 1)
• Mengambil Substring dari Suatu String dengan Function substr()
• Beberapa Function Pengolah String di MySQL (Bag. 2)