Kode Program C++: Mengurutkan Angka (Algoritma Quick Sort)

Mengenal Algoritma Quick Sort dalam Bahasa Pemrograman C++ untuk Mengurutkan Angka

Dalam dunia pemrograman, mengurutkan data merupakan salah satu tugas yang sering dilakukan. Berbagai algoritma pengurutan telah dikembangkan untuk menyelesaikan tugas ini secara efisien. Salah satu algoritma pengurutan yang populer dan banyak digunakan adalah Quick Sort. Dalam artikel ini, kita akan membahas mengenai Quick Sort dan cara implementasinya dalam bahasa pemrograman C++.

Memahami Konsep Quicksort

Quick Sort adalah algoritma pengurutan yang bekerja berdasarkan konsep "pecah belah dan taklukkan" (divide and conquer). Algoritma ini bekerja dengan memilih sebuah elemen sebagai pivot, kemudian membagi elemen-elemen lainnya menjadi dua kelompok: elemen yang lebih kecil dari pivot, dan elemen yang lebih besar dari pivot. Proses ini diulang secara rekursif pada kedua kelompok tersebut hingga semua elemen terurut.

Langkah-langkah Algoritma Quicksort

1. Pilih sebuah elemen sebagai pivot.
2. Bagi elemen-elemen lainnya menjadi dua kelompok: elemen yang lebih kecil dari pivot, dan elemen yang lebih besar dari pivot.
3. Ulangi langkah 1 dan 2 secara rekursif pada kedua kelompok tersebut hingga semua elemen terurut.

Berikut adalah contoh bagaimana algoritma Quick Sort bekerja:

Angka-angka yang akan diurutkan: {10, 7, 8, 9, 1, 5}

1. Pilih elemen tengah sebagai pivot (dalam hal ini, angka 8).
2. Bagi elemen-elemen lainnya menjadi dua kelompok: {1, 5, 7} dan {9, 10}.
3. Ulangi langkah 1 dan 2 secara rekursif pada kedua kelompok tersebut.
4. Setelah pengurutan selesai, hasilnya adalah: {1, 5, 7, 8, 9, 10}.

Keuntungan dan Kerugian Menggunakan Quick Sort

Quick Sort memiliki beberapa keuntungan, seperti:

• Efisiensi waktu rata-rata: O(n log n), yang membuatnya lebih cepat dari algoritma pengurutan lainnya seperti Bubble Sort dan Selection Sort.
• Efisiensi ruang: O(log n), yang membuatnya lebih hemat ruang dibandingkan algoritma pengurutan lainnya seperti Merge Sort.
• Mudah diimplementasikan.

Namun, Quick Sort juga memiliki beberapa kerugian, seperti:

• Kinerja terburuk: O(n^2), yang terjadi ketika elemen-elemen yang diurutkan sudah terurut atau hampir terurut.
• Sensitif terhadap pemilihan pivot. Pemilihan pivot yang buruk dapat menyebabkan kinerja terburuk.

Implementasi Quick Sort dalam Bahasa C++

Berikut adalah contoh implementasi Quick Sort dalam bahasa C++:

#include <iostream>
using namespace std;

void quickSort(int arr[], int low, int high) {
  if (low < high) {
    int pivot = arr[(low + high) / 2];
    int i = low - 1;
    int j = high + 1;

    while (true) {
      do {
        i++;
      } while (arr[i] < pivot);

      do {
        j--;
      } while (arr[j] > pivot);

      if (i >= j) {
        break;
      }

      swap(arr[i], arr[j]);
    }

    quickSort(arr, low, j);
    quickSort(arr, j + 1, high);
  }
}

int main() {
  int arr[] = {10, 7, 8, 9, 1, 5};
  int n = sizeof(arr) / sizeof(arr[0]);

  quickSort(arr, 0, n - 1);

  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }

  return 0;
}

Pada contoh kode di atas, fungsi quickSort() menerima tiga parameter: arr (array yang akan diurutkan), low (indeks awal array), dan high (indeks akhir array).

Fungsi quickSort() bekerja dengan memilih elemen tengah sebagai pivot, kemudian membagi elemen-elemen lainnya menjadi dua kelompok: elemen yang lebih kecil dari pivot, dan elemen yang lebih besar dari pivot. Proses ini diulang secara rekursif pada kedua kelompok tersebut hingga semua elemen terurut.

Kesimpulan

Quick Sort adalah salah satu algoritma pengurutan yang populer dan banyak digunakan karena efisiensi waktu rata-rata dan efisiensi ruangnya. Namun, algoritma ini juga sensitif terhadap pemilihan pivot, sehingga pemilihan pivot yang buruk dapat menyebabkan kinerja terburuk. Implementasi Quick Sort dalam bahasa C++ dapat dilakukan dengan menggunakan fungsi quickSort() yang dijelaskan pada contoh kode di atas.