מיון בחירה

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

מיון בחירה (selection sort בלעז) הוא אלגוריתם מיון השוואתי פשוט אך לא יעיל.

זמן הריצה הממוצע של האלגוריתם הוא $\Omega\left(n^2\right)$ פעולות (כמו, למשל, מיון בועות). מבחינת צריכת זיכרון האלגוריתם חסכוני, והוא דורש $\Omega\left(1\right)$ .

[עריכה] פרטי האלגוריתם

מצא את הערך בעל הערך הנמוך ביותר במערך
החלף אותו עם האיבר הראשון במערך
המשך באותה שיטה על שאר המערך (ללא האיבר הראשון)

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

[עריכה] ניתוח זמן הריצה

בהינתן מערך בגודל n, זמן הריצה של האלגוריתם הוא קבוע, כלומר אין מקרה טוב ומקרה רע. בכל מקרה לפי צעד 3, סורקים את שארית המערך n פעמים. זה מביא אותנו לסיבוכיות של $\Omega\left(n^2\right)$ .

מקור: http://he.wikipedia.org../../../%D7%9E/%D7%99/%D7%95/%D7%9E%D7%99%D7%95%D7%9F_%D7%91%D7%97%D7%99%D7%A8%D7%94.html

קטגוריה: אלגוריתמי מיון

We provide Linux to the World

מיון בחירה

מתוך ויקיפדיה, האנציקלופדיה החופשית

[עריכה] פרטי האלגוריתם

[עריכה] ניתוח זמן הריצה

Views

ניווט

קהילה

חיפוש

שפות אחרות