מבוא לתכנות ולמדעי המחשב בשפת C/רקורסיה (מיון מהיר): הבדלים בין גרסאות בדף

תוכן שנמחק תוכן שנוסף
שורה 38:
=== הפונקציה split ===
החלק העדין ביותר באלגוריתם הוא הפונקציה split. הנה הקוד שלה:
<source lang=cpp>
<syntaxhighlight>
שורה 61 ⟵ 62:
</syntaxhighlight>
<source/>
 
כפי שאפשר לראות, הפונקציה משתמשת בפונקציית עזר בשם swap שמקבלת שני אינדקסים ומחליפה את ערכי המערך שנמצאים בהם. בשלב הראשון, הפונקציה מחליפה את איבר הציר עם האיבר האחרון בקטע. בשלב הבא, הפונקציה עוברת על כל האיברים מהראשון ועד אחד לפני האחרון ומשווה אותם לאיבר הציר, שהוא כרגע האיבר האחרון. המשתנה smallIdx משמש כסמן. כל האיברים שנמצאים לפני אינדקס זה הם קטנים מאיבר הציר. בהתחלה, smallIdx נמצא בתחילת הקטע ולא ידועים איברים הקטנים מאיבר הציר. בכל שלב בלולאה מושווה המונה שלה, i, מול איבר הציר. אם נמצא שהאיבר קטן מאיבר הציר הוא מחולף עם האיבר במקום ה smallIdx ו smallIdx מקודם להצביע על האיבר הבא.