Sorting dan Searching: Algoritma Pengurutan dan Pencarian yang Wajib Dikuasai Programmer

Sorting dan searching adalah dua operasi paling fundamental dalam ilmu komputer. Hampir setiap aplikasi yang kamu bangun — dari e-commerce hingga sistem manajemen — membutuhkan kemampuan mengurutkan dan mencari data secara efisien.

Notasi Big-O: Mengukur Efisiensi Algoritma

Sebelum membahas algoritma, pahami dulu Big-O notation — cara mengukur efisiensi algoritma berdasarkan ukuran input n.

Notasi	Nama	Contoh
O(1)	Constant	Akses array by index
O(log n)	Logarithmic	Binary Search
O(n)	Linear	Linear Search
O(n log n)	Linearithmic	Merge Sort, Quick Sort
O(n²)	Quadratic	Bubble Sort, Selection Sort
O(2ⁿ)	Exponential	Fibonacci rekursif

Algoritma Sorting

1. Bubble Sort

Cara kerja: Bandingkan dua elemen berdekatan, tukar jika tidak urut. Ulangi hingga tidak ada swap.

1
void bubbleSort(int arr[], int n) {
2
    for (int i = 0; i < n - 1; i++) {
3
        int swapped = 0;
4
        for (int j = 0; j < n - i - 1; j++) {
5
            if (arr[j] > arr[j + 1]) {
6
                // Swap
7
                int temp = arr[j];
8
                arr[j] = arr[j + 1];
9
                arr[j + 1] = temp;
10
                swapped = 1;
11
            }
12
        }
13
        // Optimasi: stop jika tidak ada swap
14
        if (!swapped) break;
15
    }
16
}

Visualisasi:

1
[64, 34, 25, 12, 22, 11, 90]
2
Pass 1: [34, 25, 12, 22, 11, 64, 90]  ← 90 naik ke atas
3
Pass 2: [25, 12, 22, 11, 34, 64, 90]  ← 64 ke posisi
4
Pass 3: [12, 22, 11, 25, 34, 64, 90]
5
...
6
Final:  [11, 12, 22, 25, 34, 64, 90]

	Best	Average	Worst	Space
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)

2. Selection Sort

Cara kerja: Cari elemen terkecil, pindahkan ke posisi paling kiri. Ulangi untuk sisa array.

1
void selectionSort(int arr[], int n) {
2
    for (int i = 0; i < n - 1; i++) {
3
        int minIdx = i;
4
        for (int j = i + 1; j < n; j++) {
5
            if (arr[j] < arr[minIdx])
6
                minIdx = j;
7
        }
8
        // Swap elemen terkecil ke posisi i
9
        int temp = arr[minIdx];
10
        arr[minIdx] = arr[i];
11
        arr[i] = temp;
12
    }
13
}

Visualisasi:

1
[64, 25, 12, 22, 11]
2
Pass 1: min=11 → [11, 25, 12, 22, 64]
3
Pass 2: min=12 → [11, 12, 25, 22, 64]
4
Pass 3: min=22 → [11, 12, 22, 25, 64]
5
Pass 4: min=25 → [11, 12, 22, 25, 64] (sudah urut)

	Best	Average	Worst	Space
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)

3. Insertion Sort

Cara kerja: Ambil satu elemen, sisipkan ke posisi yang tepat di bagian kiri yang sudah terurut.

1
void insertionSort(int arr[], int n) {
2
    for (int i = 1; i < n; i++) {
3
        int key = arr[i];
4
        int j = i - 1;
5
        // Geser elemen yang lebih besar ke kanan
6
        while (j >= 0 && arr[j] > key) {
7
            arr[j + 1] = arr[j];
8
            j--;
9
        }
10
        arr[j + 1] = key;
11
    }
12
}

Visualisasi:

1
[12, 11, 13, 5, 6]
2
i=1: key=11 → [11, 12, 13, 5, 6]
3
i=2: key=13 → [11, 12, 13, 5, 6]
4
i=3: key=5  → [5, 11, 12, 13, 6]
5
i=4: key=6  → [5, 6, 11, 12, 13]

	Best	Average	Worst	Space
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)

Keunggulan: Sangat efisien untuk array yang hampir terurut atau data kecil.

4. Merge Sort

Cara kerja: Divide and Conquer — bagi array menjadi dua, sort masing-masing rekursif, lalu merge.

1
void merge(int arr[], int l, int m, int r) {
2
    int n1 = m - l + 1, n2 = r - m;
3
    int L[n1], R[n2];
4

5
    for (int i = 0; i < n1; i++) L[i] = arr[l + i];
6
    for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
7

8
    int i = 0, j = 0, k = l;
9
    while (i < n1 && j < n2) {
10
        if (L[i] <= R[j]) arr[k++] = L[i++];
11
        else arr[k++] = R[j++];
12
    }
13
    while (i < n1) arr[k++] = L[i++];
14
    while (j < n2) arr[k++] = R[j++];
15
}
16

17
void mergeSort(int arr[], int l, int r) {
18
    if (l < r) {
19
        int m = l + (r - l) / 2;
20
        mergeSort(arr, l, m);
21
        mergeSort(arr, m + 1, r);
22
        merge(arr, l, m, r);
23
    }
24
}

Visualisasi:

1
[38, 27, 43, 3, 9, 82, 10]
2
     ↓ Divide
3
[38, 27, 43]    [3, 9, 82, 10]
4
[38] [27,43]  [3,9] [82,10]
5
     ↓ Merge
6
[27,38,43]    [3,9,10,82]
7
     ↓ Final merge
8
[3, 9, 10, 27, 38, 43, 82]

	Best	Average	Worst	Space
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)

5. Quick Sort

Cara kerja: Pilih pivot, partisi array (kiri < pivot < kanan), sort rekursif.

1
int partition(int arr[], int low, int high) {
2
    int pivot = arr[high];
3
    int i = low - 1;
4

5
    for (int j = low; j < high; j++) {
6
        if (arr[j] <= pivot) {
7
            i++;
8
            int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
9
        }
10
    }
11
    int temp = arr[i+1]; arr[i+1] = arr[high]; arr[high] = temp;
12
    return i + 1;
13
}
14

15
void quickSort(int arr[], int low, int high) {
16
    if (low < high) {
17
        int pi = partition(arr, low, high);
18
        quickSort(arr, low, pi - 1);
19
        quickSort(arr, pi + 1, high);
20
    }
21
}

	Best	Average	Worst	Space
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)

Worst case terjadi saat pivot selalu elemen terkecil/terbesar (array sudah terurut). Diatasi dengan random pivot atau median-of-three.

Algoritma Searching

1. Linear Search

Cara kerja: Periksa setiap elemen satu per satu dari awal hingga akhir.

1
int linearSearch(int arr[], int n, int target) {
2
    for (int i = 0; i < n; i++) {
3
        if (arr[i] == target)
4
            return i;  // kembalikan index
5
    }
6
    return -1;  // tidak ditemukan
7
}

	Best	Average	Worst
Linear Search	O(1)	O(n)	O(n)

Cocok untuk: Array kecil atau tidak terurut.

2. Binary Search

Cara kerja: Pada array terurut, bandingkan target dengan elemen tengah. Jika lebih kecil, cari di kiri; jika lebih besar, cari di kanan.

1
// Iteratif
2
int binarySearch(int arr[], int n, int target) {
3
    int low = 0, high = n - 1;
4

5
    while (low <= high) {
6
        int mid = low + (high - low) / 2;
7

8
        if (arr[mid] == target) return mid;
9
        else if (arr[mid] < target) low = mid + 1;
10
        else high = mid - 1;
11
    }
12
    return -1;
13
}
14

15
// Rekursif
16
int binarySearchRec(int arr[], int low, int high, int target) {
17
    if (low > high) return -1;
18
    int mid = low + (high - low) / 2;
19
    if (arr[mid] == target) return mid;
20
    if (arr[mid] < target) return binarySearchRec(arr, mid+1, high, target);
21
    return binarySearchRec(arr, low, mid-1, target);
22
}

Visualisasi (cari 23 dalam [1,3,5,7,9,11,13,15,17,19,21,23]):

1
low=0, high=11, mid=5 → arr[5]=11 < 23 → cari kanan
2
low=6, high=11, mid=8 → arr[8]=17 < 23 → cari kanan
3
low=9, high=11, mid=10 → arr[10]=21 < 23 → cari kanan
4
low=11, high=11, mid=11 → arr[11]=23 ✓ DITEMUKAN!

	Best	Average	Worst
Binary Search	O(1)	O(log n)	O(log n)

Perbandingan Semua Algoritma

Algoritma	Best	Average	Worst	Space	Stable
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	✅
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	❌
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	✅
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	✅
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	❌
Linear Search	O(1)	O(n)	O(n)	O(1)	—
Binary Search	O(1)	O(log n)	O(log n)	O(1)	—

Stable sort = elemen dengan nilai sama mempertahankan urutan aslinya.

Panduan Memilih Algoritma

Kondisi	Algoritma Terbaik
Data kecil (n < 50)	Insertion Sort
Data hampir terurut	Insertion Sort
Data besar, butuh garanteed O(n log n)	Merge Sort
Data besar, average case terbaik	Quick Sort
Butuh stable sort	Merge Sort
Array tidak terurut, cari sekali	Linear Search
Array terurut, cari berulang	Binary Search

Kesimpulan

Sorting dan searching adalah fondasi algoritma. Tidak ada satu algoritma yang terbaik untuk semua situasi — pilihan tergantung ukuran data, ketersediaan memori, dan apakah data sudah terurut.

Dengan menguasai Big-O notation dan memahami trade-off setiap algoritma, kamu bisa membuat keputusan yang tepat dalam merancang sistem yang efisien.

Referensi: Data Structure and Algorithm — Sorting Algorithms, Searching, Complexity Analysis.

Thanks for reading!

Sorting dan Searching: Algoritma Pengurutan dan Pencarian yang Wajib Dikuasai Programmer

Mon Jun 29 2026

1118 words · 9 minutes

Teknologi StrukturData Sorting Searching Algorithm BigO BubbleSort QuickSort BinarySearch C