Algoritma Pengurutan (Sorting)

Algoritma pengurutan atau Sorting Algorithm dipakai untuk mengurutkan elemen-elemen array atau list. Sebagai contoh, sebuah list yang berisi karakter diurutkan secara ascending (naik) berdasarkan kode ASCII :

B A C A =====> A A B C

Sorting Algorithm ada banyak macam teknik, beberapa diantaranya :

1. Selection Sort

Mencari elemen minimum diantara array[m…n], dan menaruhnya di array[m]. Misalkan elemen-elemen yang akan diurutkan : 64, 25, 12, 22, 11

- Elemen minimum diantara array[0…4]

11, 25, 12, 22, 64

- Elemen minimum diantara array[1…4]

11, 12, 25, 22, 64

- Elemen minimum diantara array[2…4]

11, 12, 22 ,25, 64

- Elemen minimum diantara array[3…4]

11, 12, 22, 25, 64

Contoh program sorting dengan metode Selection sort dengan array pada program :

#include<iostream>
using namespace std;
void selectionSort(int a[], int n) {
  int i, j, min, temp;
  for (i = 0; i < n - 1; i++) {
     min = i;
     for (j = i + 1; j < n; j++)
        if (a[j] < a[min])
           min = j;
           temp = a[i];
           a[i] = a[min];
           a[min] = temp;
  }
   
}
int main() {
  int a[] = { 22, 91, 35, 78, 10, 8, 75, 99, 1, 67 };
  int n = sizeof(a)/ sizeof(a[0]);
  int i;
  cout<<"Given array is:"<<endl;
  for (i = 0; i < n; i++)
  cout<< a[i] <<" ";
  cout<<endl;
  selectionSort(a, n);
  printf("\nSorted array is: \n");
  for (i = 0; i < n; i++)
  cout<< a[i] <<" ";
  return 0;
}

Output :

Gambar Output Selection Sort

2. Bubble Sort

Membandingkan 2 elemen dan menukarnya jika syarat terpenuhi. Misalkan elemen-elemen yang akan diurutkan : 5, 1, 4, 2, 8

- Percobaan pertama:

5, 1, 4, 2, 8 => 1, 5, 4, 2, 8

1, 5, 4, 2, 8 => 1, 4, 5, 2, 8

1, 4, 5, 2, 8 => 1, 4, 2, 5, 8

1, 4, 2, 5, 8 => 1, 4, 2, 5, 8

- Percobaan kedua:

1, 4, 2, 5, 8 => 1, 4, 2, 5, 8

1, 4, 2, 5, 8 => 1, 2, 4, 5, 8

1, 2, 4, 5, 8 => 1, 2, 4, 5, 8

- Percobaan ketiga dibutuhkan untuk memastikan bahwa elemen-elemen sudah terurut :

1, 2, 4, 5, 8 => 1, 2, 4, 5, 8

3. Insertion Sort

Menempatkan elemen minimum ke awal array setelah dibandingkan dengan elemen-elemen sebelumnya. Misalkan elemen-elemen array yang akan diurutkan : 12, 11, 13, 5, 6

- Elemen 2 dibandingkan dengan elemen 1

12, 11, 13, 5, 6 => 11, 12, 13, 5, 6

- Elemen 3 dibandingkan dengan elemen 1 dan 2

11, 12, 13, 5, 6 => 11, 12, 13, 5, 6

- Elemen 4 dibandingkan dengan elemen 1, 2 dan 3

11, 12, 13, 5, 6 => 5, 11, 12, 13, 6

- Elemen 5 dibandingkan dengan elemen 1, 2, 3 dan 4

5, 11, 12, 13, 6 => 5, 6, 11, 12, 13

Algoritma Pengurutan (Sorting)