Let's learn C

מיון מהיר (quick sort)

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

pivot

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

מיון זה עובד בצורה הבאה:

תחילה אנו נשתמש בשני אינדקסים i ו j כאשר:
j – מצביע על התא הראשון במערך.
i – מצביע על תא אחד לפני j.
pivot – בתור הגדרה אנו לוקחים את האיבר האחרון (כלומר, pivot = arr[right_position] כאשר right_position שווה לגודל המערך פחות אחד).

לאחר שבחרנו pivot אנו מתחילים לבצע השוואות בצורה באה:
ראשית, נשווה את pivot לערכים מתחילת המערך (במקום ה-j).

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

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

דוגמה לביצוע המיון:

ראשית, ניקח את הערך בתא האחרון של המערך (8) להיות ה-pivot.
שנית, i יהיה שווה ל 1-.
j יהיה שווה ל-0.

כעת אנו משווים בין הערך בתא j שהוא (114) ל-pivot שערכו הוא (8)

בגלל ש114 גדול מ8 לא מבצעים החלפה ומגדילים את j ב-1.

כעת אנו משווים בין הערך בתא j שהוא (97) ל-pivot שערכו הוא (8)

בגלל ש97 גדול מ8 לא מבצעים החלפה ומגדילים את j ב-1.

כעת אנו משווים בין הערך בתא j שהוא (14) ל-pivot שערכו הוא (8).

בגלל ש14 גדול מ8 לא מבצעים החלפה ומגדילים את j ב-1

כעת אנו משווים בין הערך בתא j שהוא (1) ל-pivot שערכו הוא (8).

בגלל ש1 קטן מ8 מבצעים החלפה, מגדילים את j ו i ב-1 והמערך יראה כך:

אנו ביצענו החלפה בין הערכים בתא i ובתא j.

כעת אינדקס j נמצא על התא של ה-pivot.
לכן, עוצרים כאן את הבדיקה מגדילים את i ב-1 ומבצעים החלפה בין התא האחרון של המערך לתא i וכך ה-pivot נכנס לתא בו הוא צריך להיות.
(בסיום הסבב הראשון i היה שווה ל-0 ולאחר ההגדלה ב-1 i עכשיו שווה ל-1. לכן, נבצע החלפת ערכים בין תא 4 לתא 1).
לאחר ביצוע הפעולה, המערך יראה כך:

נמשיך בביצוע ההשוואות, לאחר ביצוע סבב שני המערך יראה כך:

דוגמה לקוד של מיון מהיר:

זמן ריצה של מיון מהיר במקרה הטוב הינו O(log(n)).
במקרה הגרוע O(n²).
בקוד זה ה-pivot יהיה תמיד הערך בתא האחרון, עם ריצת הקוד ה-pivot ישתנה.

CODE:


#include <stdio.h>

void swap(int *num1, int *num2)
{
  int temp = *num1;
  *num1 = *num2;
  *num2 = temp;
}

int partition(int *array ,int left_position, int right_position)
{
  int pivot = array[right_position] , j = left_position, i = left_position - 1;

  while(j < right_position)
  {
    if(array[j] < pivot)
    {
      i = i + 1;
      swap(array + i, array + j);
    }
    j = j + 1;
  }
  i = i + 1;
  swap(array + i, array + right_position);
  return i;
}       

void quick_sort(int *array, int left_position, int right_position)
{
  int middle;
  if(left_position < right_position)
  {
    middle = partition(array, left_position, right_position);
    quick_sort(array, left_position, middle -1);
    quick_sort(array, middle +1, right_position);
  }
}