ניתוח סיבוכיות

שיעור 5 מתוך 11 בקורס מיון בועות של Coddy.

ניתוח הסיבוכיות של מיון בועות.

סיבוכיות הזמן תלויה במספר ההשוואות וההחלפות שמתבצעות.

עלינו לבצע n מעברים, ובכל מעבר יש לנו (n-1) השוואות. כאשר n הוא מספר האיברים ברשימה.

סך כל ההשוואות=(n-1)+(n-1)+(n-1)....n פעמים

=n*(n-1)

=n²-n

סיבוכיות הזמן של אלגוריתם מיון בועות היא O(n²).

אם נדבר על סיבוכיות המקום, האלגוריתם אינו משתמש במקום נוסף; מתבצע מיון במקום, והאיברים מסודרים ברשימה המקורית עצמה.

סיבוכיות המקום של אלגוריתם מיון בועות היא O(1) (קבועה).

אתגר

קל

צרו פונקציה בשם count_swaps שמקבלת מערך ואת גודל המערך. בצעו את אלגוריתם מיון הבועות על המערך וספרו כמה פעמים מתבצעת החלפה.

נסו בעצמכם

#include <stdio.h>
#include <stdlib.h>

int count_swaps(int* arr, int arr_size, int n) {
    // כתבו כאן את הקוד
    return 0;
}

כל השיעורים ביחידה מיון בועות

1יסודות מיון בועות

2ניתוח

3אתגרי תרגול