מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/מיון הכנסה ומיזוג/תרגילים/מיון בחירה/תשובה

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי

פסוודו-קוד[עריכה]

להלן הפסוודו-קוד לאלגוריתם:

ּSelection-Sort(Values)
1	for i in [1, ..., n - 1]
2		min = i
3		for j in [i + 1, ..., n]
4			if Values[j] < A[min]
5				min = j

		# Exchange Values[i] and Values[min]
6		Values[i] <-> Values[min]

הוכחת נכונות[עריכה]

הנכונות מתבססת על המשפט הבא:



משפט:

בסוף האיטרציה ה של 1-6, Values[1, ..., i] הוא מערך ממויין המכיל את האיברים הקטנים ביותר במערך המקורי.


קל להוכיח את המשפט באינדוקציה דומה לזו של מיון הכנסה.

הוכחת נכונות[עריכה]

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