מבוא לתכנות ולמדעי המחשב בשפת C/מיון וחציון

מיון

אנו נמצאים כעת בשלב בו אנחנו יכולים לכתוב אלגוריתם שמבצע משימה שימושית ולא טריוויאלית: מיון של מערך מספרים לפי סדר עולה.

#include <stdio.h>
 
int main() {
	int N=7; 
	int a[N],i,j; 
	for(i=0; i<N; ++i) {
		printf("Please enter a number:\n"); 
		scanf("%d",& a[i] ); 
	}
 
	for(i=0; i<N-1; ++i) // a[i] will be the smallest of i..N-1 
		for(j=i+1; j<N; ++j)
			if(a[i] > a[j]) {
				int t = a[i]; 
				a[i] = a[j]; 
				a[j] = t; 
			}
 
	printf("The numbers you have entered (by increasing order): "); 
	for(i=0; i<N; ++i)
		printf("%d, ",a[i]); 
	printf("\n"); 
 
	return 0; 
}

אלגורתים המיון מורכב משתי לולאות מקוננות. הלולאה החיצונית, שהמונה שלה i, דואגת שבסוף כל איטרציה שלה יהיה ב [a[i הערך הקטן ביותר מתוך הערכים:

a[i], a[i+1],a[i+2],..,a[N-1]

הלולאה הפנימית רצה על הערכים האלה (החל מ i+1 ) ואם היא מגלה שהאבר בתא a[i] גדול מאחד מהם, היא דואגת להחליף ביניהם.

האיור הבא מדגים שלב טיפוסי בריצת האלגוריתם:

באיור, המספרים שמתחת למערך מייצגים את האינדקסים והמספרים שבתוך התאים מייצגים את הערכים של תאי המערך. המצב המתואר הוא מצב במהלך האיטרציה השניה של הלולאה החיצונית. לאחר סיום האיטרציה הראשונה, בתא הראשון כבר נמצא הערך הקטן ביותר של המערך (1). במהלך האיטרציה השניה, מחפש האלגוריתם את האיבר השני-הכי-קטן. עד עכשיו המועמד היה 4 אבל כרגע התגלה מועמד קטן ממנו - 3 ולכן יש להחליף בינהם. בהמשך יתגלה מועמד יותר טוב מ 3 - המספר 2 וגם שני אלה יוחלפו ביניהם.

ניתוח זמן ריצה (סיבוכיות)

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

ובכן, באיטרציה הראשונה של הלולאה החיצונית, הבלוק יתבצע N-1 פעמים. בשניה, N-2 פעמים וכך הלאה עד שבאיטרציה החיצונית האחרונה, יתבצע פעם בודדת. לכן סך הפעמים שיתבצע יהיה: $(N-1)+(N-2)+..+1={\frac {(N-1)N}{2}}={\frac {N^{2}}{2}}-{\frac {N}{2}}\in O(N^{2})$

החישוב השתמש בנוסחת הסכום של סדרה אלגברית. הסימון האחרון

$\in O(N^{2})$

משמעו שבאופן עקרוני, הביטוי אינו גדל מהר יותר מפונקציה ריבועית. את המשמעות המדוייקת של "באופן עקרוני" נלמד בהמשך אך בשלב זה נסביר רק את המוטיבציה. במדעי המחשב, כאשר אומרים שאלגוריתם אחד יעיל מאחר, הכוונה שבהנתן קלט מספיק גדול, הוא יעיל ממנו ללא תלות במהירות המחשב שמריץ אותו. מחשב אחד יכל להיות מהיר פי 100 ממחשב אחר או מהיר פי מספר קבוע אחר, כלשהו. אם אלגוריתם אחד דורש מספר חישובים שתלוי לינארית בגודל הפלט ($a\cdot N+b$) ואלגוריתם אחר יהיה פונקציה ריבועית של גודל הפלט (נניח $c\cdot N^{2}$) אז לא משנה כמה המחשב שיריץ את האלגוריתם הראשון יהיה איטי, בהנתן קלט מספיק גדול, הוא ישיג את המחשב המריץ את האלגוריתם השני, אפילו אם יהיה מהיר מאוד.

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

קצב הגידול של מספר הפעולות של אלגוריתם המיון שלמדנו הוא של פונקציה ריבועית ולכן הוא נקרא אלגוריתם בעל סיבוכיות ריבועית. האלגוריתם שראינו להיפוך איבריו של מערך דורש רק מעבר אחד על חצי מאברי המערך. קצב הגידול שלו הוא כמו של פונקציה לינארית ולכן הוא נקרא אלגוריתם בעל סיבוכיות לינארית.

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

חישוב חציון

מדוע מיון הוא דבר חשוב ומועיל? אם לדוגמה אנו מעוניינים למצוא את החציון (הערך שמספר הערכים שקטנים ממנו שווה למספר הערכים שגדולים ממנו) של קבוצת הערכים שהכנסנו, מיון מאפשר לנו לעשות זאת בצורה קלה:

#include <stdio.h>
 
int main() {
	int N=5; 
	int a[N],i,j; 
	for(i=0; i<N; ++i) {
		printf("Please enter a number:\n"); 
		scanf("%d",& a[i] ); 
	}
 
	for(i=0; i<N-1; ++i) // a[i] will be the smallest of i..N-1 
		for(j=i+1; j<N; ++j)
			if(a[i] > a[j]) {
				int t = a[i]; 
				a[i] = a[j]; 
				a[j] = t; 
			}
 
 	if (N%2 == 1)
		printf("The median of your numbers is %d \n",a[N/2]); 
	else {
		printf("There is no median because the number of values is an even number.\n");  
		printf("However, the two middle values are: %d %d \n",a[N/2-1],a[N/2]);
	} 

	return 0; 
}

תבנית:ניווט מבוא