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 :

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