Sorting kata menggunakan Quick Sort


Setelah lama vakum ngeblog karena diterpa badai skripsi, akhirnya bisa kembali berbagi sedikit code yang mungkin bergunašŸ™‚ .

Langsung saja, bagi yang sering ngoding atau ngutek-ngutek algoritma sorting pasti sudah paham yang namanya quicksort yang sangat cepat dalam proses sorting. Namun sebagian besar dari kita hanya mengetahui penggunaannya untuk sorting angka, bagaimana jika untuk sorting kata? Berikut langkah-langkahnya:

    1. Jika terdapat kata-kata misalnya “akar” dan “akan” mak untuk melakukan sorting kita perlu membandingkan satu persatu hurufnya mulai dari paling kiri. Tetapi terdapat 3 huruf yang sama dan hanya huruf yang terkhir yang bisa untuk membandingkan. Hasilnya jika disorting secaraĀ ascending maka diperoleh “akan” kemudian “akar.
    2. Jika terdapat code quicksort seperti dibawah ini:
static int partition(ref intp[] arr, int left, int right)
{
      int i = left, j = right;
      int tmp;
      int pivot = arr[(left + right) / 2];
      while (i <= j) {
            while (arr[i] < pivot)
                  i++;
            while (arr[j] > pivot)
                  j--;
            if (i <= j) {
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
            }
      };
      return i;
} 

static void quickSort(ref int arr[], int left, int right) {
      int index = partition(ref arr, left, right);
      if (left < index - 1)
            quickSort(ref arr, left, index - 1);
      if (index < right)
            quickSort(ref arr, index, right);
}
  1. Maka diperlukan sedikit perubahan pada kode diatas dan dengan sedikit menambahkan fungsi getVal(String input) sebagai pemberi nilai pada kata agar bisa dibandingkan dengan cepat, berikut codenya:
            static double getVal(String input)
            {
                double hasil = 0;
                double value = 1000;
                foreach(char ch in input){
                    hasil += (int)ch * value;
                    value /= 8;
                }
                return hasil;
            }

    Ide dasarnya yaitu memberi nilai pengali yang besar pada huruf terdepan dan pengalinya dibagi secara konstan jika menuju ke kanan(index dari array char bertambah). Dengan demikian tidak perlu membandingkan satu persatu hurufnya tetapi dibandingkan secara keseluruhan. Ā Kemudian pada code quicksort dilakukan perubahan sebagai berikut:

    static int partitionS(ref String[] arr, int left, int right)
            {
                int i = left, j = right;
                String tmp;
                double pivot = getVal(arr[(left + right) / 2]);
                while (i <= j)
                {
                    while (getVal(arr[i]) < pivot)
                           i++;
                    while (getVal(arr[j]) > pivot)
                          j--;
                    if (i <= j)
                    {
                        tmp = arr[i];
                        arr[i] = arr[j];
                        arr[j] = tmp;
                        i++;
                        j--;
                    }
                }
                return i;
            }
    
    static void quickSort(ref String[] arr, int left, int right)
            {
                int index = partitionS(ref arr, left, right);
                if (left < index - 1)
                    quickSort(ref arr, left, index - 1);
                if (index < right)
                    quickSort(ref arr, index, right);
            }
  2. Mudah kan??šŸ˜€
  3. Berikut adalah contoh hasil running program :

Untitled

Code lengkapnya sebagai berikut:

using System;
public class Sorting{
	static int partitionS(ref String[] arr, int left, int right)
        {
            int i = left, j = right;
            String tmp;
            double pivot = getVal(arr[(left + right) / 2]);
            while (i <= j)
            {
                while (getVal(arr[i]) < pivot)
                       i++;
                while (getVal(arr[j]) > pivot)
                      j--;
                if (i <= j)
                {
                    tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;
                    i++;
                    j--;
                }
            }
            return i;
        }

	static void quickSort(ref String[] arr, int left, int right)
        {
            int index = partitionS(ref arr, left, right);
            if (left < index - 1)
                quickSort(ref arr, left, index - 1);
            if (index < right)
                quickSort(ref arr, index, right);
        }
		
	static double getVal(String input)
	{
		double hasil = 0;
		double value = 1000;
		foreach(char ch in input){
			hasil += (int)ch * value;
			value /= 8;
		}
		return hasil;
	}
	
	static void print(String[] str, bool withValue )
	{
		for(int i=0; i < str.Length; i++)
			Console.WriteLine(String.Format("Data ke-{0} = {1} {2:0}", 
				i+1, str[i], withValue?getVal(str[i])+"":""));
	}
	
	public static void Main(String [] args)
	{
		String[] data = {"sesal","akan", "akar", "asal", "asam"};
		print(data, false);
		quickSort(ref data, 0, data.Length-1);
		Console.WriteLine("------------------------------------");
		print(data, true);
	}
}

4 thoughts on “Sorting kata menggunakan Quick Sort

    1. maksudnya foreach nya dari mana?, maap itu pake C# soalnya klo di java kan syntaxnya cuma for(int x : arrayOfIntX)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s