konsep dasar algoritma pengurutan dalam bahasa C
1. bubble sort
Bubble Sort adalah salah satu algoritma pengurutan sederhana yang bekerja dengan cara secara berulang membandingkan dan menukar elemen-elemen adjacent (bersebelahan) yang tidak terurut dalam suatu array. Proses ini berulang sampai seluruh array terurut secara ascending (menaik). Nama "Bubble Sort" diambil dari cara elemen-elemen yang lebih besar "muncul" (seperti gelembung) ke arah akhir array selama proses pengurutan
contoh kode program dalam bubble short seperti berikut :
// Fungsi untuk melakukan Bubble Sort
void bubbleSort(int arr[], int n) {
int i, j;
for (i = 0; i < n-1; i++) {
for (j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
// Tukar nilai jika elemen saat ini lebih besar dari elemen berikutnya
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
// Fungsi untuk menampilkan elemen-elemen array
void displayArray(int arr[], int size) {
for (int i=0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr)/sizeof(arr[0]);
printf("Array sebelum diurutkan: \n");
displayArray(arr, n);
// Panggil fungsi Bubble Sort
bubbleSort(arr, n);
printf("Array setelah diurutkan: \n");
displayArray(arr, n);
return 0;
}
output dari kode diatas:
2. Selection Sort
Selection Sort adalah algoritma pengurutan sederhana yang bekerja dengan cara secara berulang memilih elemen dengan nilai minimum dari bagian yang belum diurutkan dari array dan menukarnya dengan elemen pertama yang belum diurutkan. Proses ini diulang sampai seluruh array terurut
contoh kode program diatas :
// Fungsi untuk melakukan Selection Sort
void selectionSort(int arr[], int n) {
int i, j, minIndex;
for (i = 0; i < n-1; i++) {
// Temukan indeks elemen minimum di bagian yang belum diurutkan
minIndex = i;
for (j = i+1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Tukar elemen minimum dengan elemen pertama yang belum diurutkan
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
// Fungsi untuk menampilkan elemen-elemen array
void displayArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr)/sizeof(arr[0]);
printf("Array sebelum diurutkan: \n");
displayArray(arr, n);
// Panggil fungsi Selection Sort
selectionSort(arr, n);
printf("Array setelah diurutkan: \n");
displayArray(arr, n);
return 0;
}
output dari kode diatas :
3. Insertion Sort
Insertion Sort adalah algoritma pengurutan sederhana yang bekerja dengan cara secara iteratif membangun urutan terurut satu elemen pada satu waktu dengan membandingkan dan memindahkan elemen-elemen dari bagian yang belum diurutkan ke bagian yang sudah diurutkan dari array. Proses ini diulang sampai seluruh array terurut.
kode dari Insertion Sort :
void insertionSort(int arr[], int n) {
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
// Geser elemen-elemen yang lebih besar dari key ke posisi yang lebih tinggi
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
// Tempatkan key ke posisi yang tepat
arr[j + 1] = key;
}
}
void displayArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Array sebelum diurutkan: \n");
displayArray(arr, n);
insertionSort(arr, n);
printf("Array setelah diurutkan: \n");
displayArray(arr, n);
return 0;
}
output dari kode diatas :
Merge Sort adalah algoritma pengurutan yang menggunakan konsep pemisahan (divide) dan penggabungan (conquer). Algoritma ini bekerja dengan membagi array menjadi dua bagian, mengurutkan kedua bagian tersebut secara rekursif, dan kemudian menggabungkan hasilnya. Metode ini umumnya dikenal sebagai "divide and conquer."
contoh kode perogram Merge Sort :
// Fungsi untuk menggabungkan dua bagian yang telah diurutkan
void merge(int arr[], int left, int mid, int right) {
int i, j, k;
int n1 = mid - left + 1;
int n2 = right - mid;
// Buat array temporari untuk menyimpan bagian kiri dan kanan
int L[n1], R[n2];
// Salin data ke array temporari L[] dan R[]
for (i = 0; i < n1; i++)
L[i] = arr[left + i];
for (j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
// Gabungkan array temporari ke dalam arr[left..right]
i = 0;
j = 0;
k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// Salin sisa elemen-elemen jika ada
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// Fungsi untuk melakukan Merge Sort
void mergeSort(int arr[], int left, int right) {
if (left < right) {
// Temukan titik tengah
int mid = left + (right - left) / 2;
// Panggil rekursif untuk dua bagian yang terbagi
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// Gabungkan dua bagian yang terurut
merge(arr, left, mid, right);
}
}
// Fungsi untuk menampilkan elemen-elemen array
void displayArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Array sebelum diurutkan: \n");
displayArray(arr, n);
// Panggil fungsi Merge Sort
mergeSort(arr, 0, n - 1);
printf("Array setelah diurutkan: \n");
displayArray(arr, n);
return 0;
}
output dari kode diatas :
out
5. Quick Sort
Quick Sort adalah algoritma pengurutan yang juga menggunakan pendekatan "divide and conquer". Algoritma ini berfungsi dengan cara memilih elemen yang disebut "pivot" dari array dan mempartisi array menjadi dua bagian: elemen-elemen yang lebih kecil dari pivot dan elemen-elemen yang lebih besar dari pivot. Kemudian, algoritma ini secara rekursif diterapkan pada kedua bagian tersebut.
contoh kode program :
// Fungsi untuk melakukan partisi array dan mengembalikan indeks pivot
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // Pilih elemen terakhir sebagai pivot
int i = (low - 1); // Indeks elemen yang lebih kecil dari pivot
for (int j = low; j <= high - 1; j++) {
// Jika elemen saat ini lebih kecil dari atau sama dengan pivot
if (arr[j] <= pivot) {
i++;
// Tukar arr[i] dan arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Tukar arr[i+1] dan arr[high] (pivot)
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
// Fungsi untuk melakukan Quick Sort
void quickSort(int arr[], int low, int high) {
if (low < high) {
// Temukan indeks pivot yang benar
int pi = partition(arr, low, high);
// Terapkan Quick Sort rekursif pada kedua bagian sebelum dan setelah pivot
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// Fungsi untuk menampilkan elemen-elemen array
void displayArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Array sebelum diurutkan: \n");
displayArray(arr, n);
// Panggil fungsi Quick Sort
quickSort(arr, 0, n - 1);
printf("Array setelah diurutkan: \n");
displayArray(arr, n);
return 0;
}
output :
Comments
Post a Comment