Adaptivitas
Pelajaran 6 dari 11 dalam kursus Bubble Sort di Coddy.
Kita telah membahas kompleksitas waktu algoritma bubble sort kita, yaitu O(n2) . Namun, bagaimana jika array kita sudah terurut? Saat itu pun, waktu eksekusinya akan tetap O(n2).
Apa itu Adaptivitas?
Algoritma adaptif adalah algoritma yang mengubah perilakunya berdasarkan urutan input yang diberikan.
Jadi, apakah bubble sort adaptif?
Ya, kita bisa membuat algoritma bubble sort kita adaptif. Kita harus menulis algoritma Bubble Sort dengan waktu eksekusi kasus terburuk sebesar O(n2) dan kasus terbaik sebesar O(n) agar algoritma ini adaptif. Di sini, kasus terbaik mengacu pada kondisi ketika array sudah terurut.
Kita akan menggunakan variabel boolean sebagai penanda untuk mengontrol while loop agar algoritma berhenti lebih awal jika array sudah terurut sebelumnya.
while(flag)
{
//code
}
Kita harus mengulangi proses sampai array terurut. Kita sudah belajar cara menghitung jumlah pertukaran, jadi kita bisa menggunakan penanda dan memeriksa apakah tidak ada pertukaran yang diperlukan dalam proses tersebut, lalu kita bisa menghentikan perulangan.
Tantangan
SedangBuat fungsi bernama ad_bubblesort yang menerima sebuah array dan ukuran array tersebut. Lakukan algoritma bubble sort adaptif. Ingat untuk menggunakan variabel bernama flag untuk memeriksa pertukaran.
Coba sendiri
#include <stdio.h>
#include <stdlib.h>
int* ad_bubblesort(int* arr, int arr_size, int n, int* returnSize) {
// Tulis kodemu di sini
*returnSize = n;
return arr;
}
Semua pelajaran di Bubble Sort
1Dasar-Dasar Bubble Sort
PengenalanCara Kerja Bubble SortTukar Elemen yang BerdekatanAlgoritma Bubble SortLatihan sendiri: Compiler C online