אדפטיביות
שיעור 6 מתוך 11 בקורס מיון בועות של Coddy.
דנו בסיבוכיות הזמן של אלגוריתם מיון הבועות שלנו, שהיא O(n2) . אבל מה אם המערך שלנו כבר ממוין? גם אז זמן הריצה יהיה O(n2).
מהי הסתגלותיות?
אלגוריתם מסתגל הוא אלגוריתם שמשנה את התנהגותו בהתאם לרצף הקלט הנתון.
אז, האם מיון בועות הוא מסתגל?
כן, אפשר להפוך את אלגוריתם מיון הבועות שלנו למסתגל. עלינו לכתוב את אלגוריתם מיון הבועות כך שזמן הריצה שלו במקרה הגרוע ביותר יהיה O(n2), ובמקרה הטוב ביותר יהיה O(n), כדי שיהיה מסתגל. כאן, המקרה הטוב ביותר מתייחס למצב שבו המערך כבר ממוין.
נשתמש במשתנה דגל בוליאני כדי לשלוט בלולאת while, כך שהאלגוריתם ייעצר מוקדם אם המערך כבר היה ממוין.
while(flag)
{
//code
}
עלינו לחזור על המעבר עד שהמערך יהיה ממוין. כבר למדנו כיצד לספור את מספר ההחלפות, ולכן נוכל לממש דגל ולבדוק אם אין צורך בהחלפה במהלך המעבר, ואז נוכל לצאת מהלולאה.
אתגר
בינוניצור פונקציה בשם ad_bubblesort שמקבלת מערך ואת גודל המערך. בצע את אלגוריתם מיון הבועות האדפטיבי. זכור להשתמש במשתנה בשם flag כדי לבדוק אם בוצעו החלפות.
נסו בעצמכם
#include <stdio.h>
#include <stdlib.h>
int* ad_bubblesort(int* arr, int arr_size, int n, int* returnSize) {
// כתבו כאן את הקוד
*returnSize = n;
return arr;
}
כל השיעורים ביחידה מיון בועות
תרגלו בעצמכם: קומפיילר C אונליין