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

מיון מהיר

כבר השתכנענו בעבר שמיון הוא משימה חשובה. ראינו שכאשר הנתונים ממוינים, אפשר למצוא את הנתון שמחפשים הרבה יותר בקלות. למדנו גם אלגוריתם למיון אבל הוא היה די נאיבי ולא יעיל. היעילות שלו היתה $O(n^{2})$.

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

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

תיאור כללי

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

מימוש רקורסיבי

נתרגם את התיאור המילולי לקוד:

int array[1000]; 
...

void quickSort(int from,int to) {
  if(from >= to) 
    return; 
  int pivot = pickAPivot(from,to); 
  pivot = split(pivot,from,to);
  quickSort(from,pivot-1);
  quickSort(pivot+1,to); 
}

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

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

לאחר הפיצול, יש למיין את האברים הקטנים המצאים בקטע from..pivot-1 ואת המספרים הגדולים (או שווים) בקטע pivot+1..to. כאשר סיימנו את שני המיונים האלה, המערך ממויין כולו.

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

הפונקציה split

החלק העדין ביותר באלגוריתם הוא הפונקציה split. הנה הקוד שלה:

 
void swap(int i1, int i2) {
  int tmp = array[i1]; 
  array[i1] = array[i2]; 
  array[i2] = tmp; 
}
 
int split(int pivot, int from, int to) {
  swap(pivot,to); 
  int smallIdx = from; 
  int i; 
  for(i=from; i<to; ++i) {
    if(array[i] < array[to]) {
      swap(smallIdx,i);
      ++smallIdx;
    }
  }
  swap(smallIdx,to);
  return smallIdx;
}

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

בכל שלב במהלך ריצת split, האברים הנמצאים לפני smallIdx הם איברים קטנים מאיבר הציר, האיברים בין smallIdx ל i (לא כולל) הם איברים גדולים מאיבר הציר וכל האיברים מ i ואליך, עדיין לא נבדקו.

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

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

בחירת איבר הציר

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

int pickAPivot(int from, int to) {
    return to; 
}

בבחירה כזו, דווקא אם המערך ממויין מראש (או שניתן בסדר הפוך), כל הפעלה של split תפצל את המערך לקטע ריק וקטע המכיל את שאר המספרים. הסיבוכיות של האלגוריתם במקרה זה תהיה <m>O(n^2)</m> (השיקולים דומים לאלה שהפעלנו בניתוח האלגוריתם הנאיבי). כדי שהאלגוריתם יהיה יעיל במקרה של קלט ממוין, אפשר לבחור את האיבר הנמצא באמצע הקטע:

int pickAPivot(int from, int to) {
  return (from+to)/2;
}

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

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

קוד מלא

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

#include <stdio.h>
#include <stdlib.h> 

int SIZE; 
int MAX = 1000000; 
int array[1000000]; 

int count; 

void swap(int i1, int i2) {
  int tmp = array[i1]; 
  array[i1] = array[i2]; 
  array[i2] = tmp; 
}

int pickAPivot(int from, int to) {
  return (from+to)/2;
  //  return to; 
}

int split(int pivot, int from, int to) {
  swap(pivot,to); 
  int smallIdx = from; 
  int i; 
  for(i=from; i<to; ++i) {
    ++count; 
    if(array[i] < array[to]) {
      swap(smallIdx,i);
      ++smallIdx;
    }
  }
  swap(smallIdx,to);
  return smallIdx;
}

void quickSort(int from,int to) {
  if(from >= to) 
    return; 
  int pivot = pickAPivot(from,to); 
  pivot = split(pivot,from,to);
  quickSort(from,pivot-1);
  quickSort(pivot+1,to); 
}

void init() {
  int i; 
  for(i=0; i<SIZE; ++i)
    array[i] = random()%SIZE+1; 
}

void printArray() {
  int i; 
  for(i=0; i<SIZE; ++i)
    printf("%d, ",array[i]);
  printf("\n"); 
}

void sort() {
  count = 0; 
  quickSort(0,SIZE-1);
}

void statistics(int n) {
  int i;
  double avarage=0; 
  for(i=0; i<n; ++i) {
    init();
    sort();
    avarage += (float)count/n;  
  }

  printf("== Statistics over %d sortings ==\n", n); 
  printf("Avarage number of comparisons: %lf\n",avarage); 
  printf("Size: %d \n",SIZE);
  printf("Ratio(comparisons/size): %lf\n",avarage/SIZE); 
} 

void getSizeFromUser() {
  while(1) {
    printf("Size: "); 
    scanf("%d",&SIZE); 
    if(SIZE >= 1 && SIZE <= MAX)
      return; 
    printf("Valid range is 1..%d, please try again.\n",MAX); 
  }
}

void test1() {
  init();
  sort(); 
  printArray(); 
}

void test2() {
  int i; 
  for(i=0; i<SIZE; ++i)
    array[i] = SIZE-i; 
  sort();
  printf("Reverse order\n"); 
  printf("Ratio(comparisons/size): %f\n",(float)count/SIZE); 
}

void test3() {
  int i; 
  for(i=0; i<SIZE; ++i)
    array[i] = i+1; 
  sort();
  printf("Already ordered\n"); 
  printf("Ratio(comparisons/size): %f\n",(float)count/SIZE); 
}

int main() {
  //  getSizeFromUser();
  SIZE = 1000; 
  test1(); 
  test2();
  test3(); 

  statistics(10); 
  return 0; 
}

אנימציה שממחישה את פעולת האלגוריתם:

מתוך ויקיפדיה

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