Pengurutan Array

dari referensi diketahui bahwa algoritma pengurutan ada banyak, namun dari pengurutan tersebut ada yang membutuhkan pemahaman yang lebih dari yang diketahui saat ini (array). misalnya tree sort yang membutuhkan pemahaman terhadap konsep pohon. untuk array, terdapat 4 model yang sering digunakan, dan biasanya memiliki varian-variannya, seperti :
1. Bubble Sort
2. Selection Sort
3. Insertion Sort
4. Shell Sort

contoh programnya :

#include
#define SIZE 10

void bubbleSort (int a[], int size);

int main()
{
  int a[SIZE] = {4, 3, 8, 10, 7, 11, 51, 92, 43, 74};
  int i;

  printf ("= BubbleSort =\n\n");
  printf ("Data sebelum diurutkan :\n");
  for (i = 0; i < SIZE; i++)
    {
      printf ("%d\t", a[i]);
    }

  printf ("\n");
  bubbleSort (a, SIZE);

  printf ("\nData setelah diurutkan :\n");
  for (i = 0; i < SIZE; i++)
    {
      printf ("%d\t", a[i]);
    }

  printf ("\n");
  return 0;
}

void bubbleSort (int a[], int size)
{
  int i;
  int elemen;
  int swap;

  // loop untuk mengendalikan elemen array
  for (elemen = 0; elemen < size; elemen++)
    {
      // loop untuk kendalikan angka sebagai perbandingan per elemen
      for (i = 0; i < size - 1; i++) 	{ 	  // bandingkan elemen berdekatan dengan swap jika elemen pertama lebih besar dari elemen dua 	  if (a[i] > a[i + 1])
	    {
	      swap = a[i];
	      a[i] = a[i + 1];
	      a[i + 1] = swap;
	    }
	}
    }
}

1. Bubble Sort
pada prinsipnya melakukan proses pertukaran dengan nilai yang ada disebelahnya sampai array tersebut terurut.

void bubbleSort (int a[], int size)
{
  int i;
  int elemen;
  int swap;

  // loop untuk mengendalikan elemen array
  for (elemen = 0; elemen < size; elemen++)
    {
      // loop untuk kendalikan angka sebagai perbandingan per elemen
      for (i = 0; i < size - 1; i++) 	{ 	  // bandingkan elemen berdekatan dengan swap jika elemen pertama lebih besar dari elemen dua 	  if (a[i] > a[i + 1])
	    {
	      swap = a[i];
	      a[i] = a[i + 1];
	      a[i + 1] = swap;
	    }
	}
    }
}

untuk elemen ke-0, perulangan akan dilanjutkan langsung pada elemen ke-1 dengan indeks ke-0, karena elemen ke-0 tidak bernilai. elemen ke-1 yaitu a[0] akan dibandingkan dengan a[1] dari elemen ke-2. ternyata elemen ke-1 yang bernilai 4 lebih besar dari elemen ke-2 yang bernilai 3. maka proses pertukaran terjadi antara elemen ke-1 dengan elemen ke-2 menjadi a[0] = 3 dan a[1] = 4. setelah itu, elemen ke-1 akan dibandingkan dengan elemen ke-3 sampai dengan ke-10. ternyata, elemen ke-1 bernilai lebih kecil dari elemen setelahnya, maka proses pertukaran tidak terjadi lagi. pada elemen ke-2 yaitu a[1]. nilainya saat ini telah berubah menjadi 4. maka perbandingan nilai akan diulang lagi dari elemen ke-0 sampai ke 10. jika lebih besar maka nilainya akan ditukarkan, begitu seterusnya.

2. Selection Sort
algoritma ini memiliki prinsip yaitu memilih elemen bernilai maksimum dari array dan menempatkannya pada elemen terujung.

void selectionSort (int a[], int size)
// a[0] sampai a[n-1] adalah array untuk diurutkan terurut
{
  int elemen;
  int i;
  int maks;
  int swap;

  // lakukan pengulangan untuk tiap elemen array
  for (elemen = 0; elemen < size; elemen++)
    {
      // atur kondisi maksimum pada elemen tiap elemen, dimulai dari maks = elemen 0
      maks = elemen;
      // cari indeks dari elemen maksimum di dalam array a[i..size]
      for (i = elemen + 1; i < size; i++)
	{
	  if (a[i] > a[maks]) // jika i lebih besar dari elemen sebelahnya maka tukar
	    {
	      maks = i;
	    }
	}
      // setelah kondisi maksimum didapat, maka lakukan proses pertukaran
      if (maks != elemen)
	{
	  swap = a[maks];
	  a[maks] = a[elemen];
	  a[elemen] = swap;
	}
    }
}

3. Insertion Sort
merupakan metode pengurutan dengan cara menyisipkan elemen array pada posisi yang tepat. pencarian posisi ini dilakukan dengan cara menyisir array. selama proses penyisiran dilakukan pergeseran elemen array. insertion sort cocok untuk persoalan menyisipkan elemen baru kedalam sekumpulan array yang sudah terurut.

void insertionSort (int a[], int size)
{
  int elemen;
  int index;
  int nilai;
  typedef enum {true = 1, false = 0} boolean;
  boolean selesai;

  for (elemen = 0; elemen <= size-1; elemen++)
    {
      nilai = a[elemen];
      index = elemen - 1;
      selesai = false;

      // repeat
      while (index >= 0 && (!selesai))
	{
	  if (a[index] > nilai)
	    {
	      a[index + 1] = a[index];
	      index--;
	    }
	  else
	    selesai = true;
	}
      a[index + 1] = nilai; // sisipkan nilai pada tempat yang tepat
    }
}

4. Shell Sort
shell sort merupakan perbaikan dari insertion sort, dimana penyisipan array dikurangi oleh pembagian pada pola tertentu. lebih jelas, lihat video aja ya.

void shellSort (int a[], int size)
{
  int step;
  int start;

  step = size;
  while (step > 1)
    {
      step = step / 3 + 1;
      for (start - 1; start <= step; start++)
	insertionSort(a, size, start, step);
    }
}

void insertionSort (int a[], int size, int start, int step)
{
  int elemen;
  int index;
  int nilai;
  typedef enum {true = 1, false = 0} boolean;
  boolean selesai;

  while (elemen <= size)
    {
      nilai = a[elemen]; // sisipkan a[elemen] kedalam bagian yang sudah terurut

      // cari posisi yang tepat untuk nilai didalam a[start..i-1] sambil menggeser
      index = elemen - step;
      selesai = false;
      while (index >= 0 && (!selesai))
	{
	  if (a[index] > nilai)
	    {
	      a[index + step] = a[index];
	      index = index - step;
	    }
	  else
	    selesai = true;
	}
      // i < 1 atau selesai
      a[index + step] = nilai; // sisipkan nilai pada tempat yang tepat
      elemen = elemen + step;
    }
}