Analisis Kompleksitas
Pelajaran 5 dari 11 dalam kursus Bubble Sort di Coddy.
Analisis kompleksitas bubble sort.
Kompleksitas waktu bergantung pada jumlah perbandingan & pertukaran yang dilakukan.
Kita harus melakukan n lintasan dan di setiap lintasan kita melakukan (n-1) perbandingan. dengan n adalah jumlah elemen dalam list.
Total perbandingan=(n-1)+(n-1)+(n-1)....n kali
=n*(n-1)
=n2-n
Kompleksitas waktu algoritma bubble sort adalah O(n2).
Jika kita membahas kompleksitas ruang, algoritma ini tidak menggunakan ruang tambahan, pengurutan in-place dilakukan dan elemen-elemen disusun di dalam list aslinya.
Kompleksitas ruang algoritma bubble sort adalah O(1) (Konstan).
Tantangan
MudahBuat fungsi bernama count_swaps yang menerima sebuah array dan ukuran array tersebut. Lakukan algoritma bubble sort pada array dan hitung berapa kali pertukaran dilakukan.
Coba sendiri
#include <stdio.h>
#include <stdlib.h>
int count_swaps(int* arr, int arr_size, int n) {
// Tulis kodemu di sini
return 0;
}
Semua pelajaran di Bubble Sort
1Dasar-Dasar Bubble Sort
PengenalanCara Kerja Bubble SortTukar Elemen yang BerdekatanAlgoritma Bubble SortLatihan sendiri: Compiler C online