הצגת המקור של הדף "אלגוריתם תוך-מקומי"

{{מקורות|רמה=אין|נושא=מחשוב}}
ב[[מדעי המחשב]], '''אלגוריתם תוך-מקומי''' הוא [[אלגוריתם]] המתמיר [[מבנה נתונים]] תוך שימוש בכמות קטנה וקבועה של שטח אחסון נוסף. בדרך כלל, [[פלט]] האלגוריתם נכתב על-גבי שטח ה[[קלט]], ללא שימוש במבנים זמניים משמעותיים. אלגוריתם שאינו תוך-מקומי נקרא לעיתים '''לא-תוך-מקומי''' או '''חוץ-מקומי'''.

דוגמאות: [[מיון ערימה]], [[מיון בועות]].

== דוגמאות ==
נגדיר [[מערך (מבנה נתונים)|מערך]] 'a' באורך 'n' .

עכשיו, נגדיר [[שגרה (תכנות)|פונקציה]] בשם reverse שתחזיר את ה[[מערך (מבנה נתונים)|מערך]] בצורה ההפוכה.

למשל:

אם הפונקציה תקבל את ה[[מערך (מבנה נתונים)|מערך]] [1,2,3] היא תחזיר [3,2,1]

עכשיו נציג שתי דרכים לעשות זאת:

שיטת [[אלגוריתם חוץ-מקומי]]:

<syntaxhighlight lang="text">
function reverse(a[0..n - 1])
 allocate b[0..n - 1]
 for i from 0 to n - 1
 b[n − 1 − i] := a[i]
 return b
</syntaxhighlight>

שיטה זו פחות יעילה, מכיוון שהיא צורכת כמות זיכרון גבוהה יותר בשביל המערך 'b'.
עכשיו נראה איך נוכל להפוך את הקוד ליותר יעיל, וגם לכתוב את הקוד במקום (אלגוריתם תוך-מקומי).

שיטת אלגוריתם תוך-מקומי:

<syntaxhighlight lang="text">
 function reverse_in_place(a[0..n])
 for i from 0 to floor(n/2)
 tmp := a[i]
 a[i] := a[n − 1 − i]
 a[n − 1 − i] := tmp
</syntaxhighlight>
כפי שניתן לראות ה[[אלגוריתם]] השני (אלגוריתם תוך-מקומי) יעיל בהרבה, מבחינת ניצול הזיכרון. מבחינת [[סיבוכיות]] ריצה ללא הפיכה ל<math>O(n)</math> ניתן לראות שהפונקציה הראשונה תהיה <math>O(2n)</math> והשנייה <math>O\begin{pmatrix}{n\over 2}\end{pmatrix}</math>. כך שיוצא שהפונקציה השנייה יעילה במקצת בסיבוכיות.

{{אלגוריתמי מיון}}

{{קצרמר|מדעי המחשב}}
[[קטגוריה:אלגוריתמים]]