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

פסוודו-קוד

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

ּ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]

הוכחת נכונות

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

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

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

הוכחת נכונות

קל להראות שהסיבוכיות היא $\displaystyle O(n^{2})$, ושיש קלט שעבורו הסיבוכיות היא $\displaystyle \Omega (n^{2})$, וגם זאת בצורה דומה למה שראינו בזו של מיון הכנסה.