מיון

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

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

אלגוריתמי מיון עוזרים לתפעל נתונים, וכן לפתור בעיות מתמטיות ובעיות תכנות רבות.

*כדי להשתמש בשיטות, עלינו לכלול את קובץ הכותרת algorithm בראש קובץ ה-C++ שלנו באמצעות #include <algorithm>.

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

• sort()
• is_sorted()
• partial_sort()

השיטה sort

השיטה sort() של STL ממיינת את התוכן של הטווח הנתון. השיטה זקוקה לאיטרטור התחלה ולאיטרטור סיום, והיא תמיין את האיברים בטווח הזה בסדר עולה.

אפשר להשתמש בה בשתי גרסאות:

• sort(starting_iterator, ending_iterator) - ממיינת את הטווח שמוגדר על ידי האיטרטורים בסדר עולה
• sort(starting_iterator, ending_iterator, comparing_function) - ממיינת את הטווח שמוגדר על ידי האיטרטורים, אך בהתאם לפונקציה שניתנה כפרמטר השלישי

vector<int> numbers = {3, 5, 1, 2, 4};

sort(numbers.begin(), numbers.end());

for(auto i = numbers.begin(); i != numbers.end(); i++)
	cout << *i << " ";

Output:
1 2 3 4 5

כפי שאפשר לראות בקוד שלמעלה, השיטה sort() מיינה את הווקטור בסדר עולה.

bool compare(int a, int b)
{
	return a > b; // החזר 1 אם a גדול מ-b
}

int main()
{
	vector<int> numbers = {3, 5, 1, 2, 4};
	
	sort(numbers.begin(), numbers.end(), compare);
	
	for(auto i = numbers.begin(); i != numbers.end(); i++)
		cout << *i << " ";

Output:
5 4 3 2 1

כך אפשר לראות כיצד השתמשנו בגרסה השנייה של השיטה sort. יצרנו את הפונקציה compare() כך שהיא מחזירה true אם a גדול מ-b. כך אפשר למיין את הווקטור בסדר יורד.

השיטה is_sorted

השיטה is_sorted() היא פונקציה של STL שמחזירה true או false אם הטווח הנתון ממוין או לא. 

יש גם שתי גרסאות של השיטה is_sorted(), בדיוק כמו בשיטה sort():

• is_sorted(starting_iterator, ending_iterator) - בודקת אם הטווח שמוגדר על ידי שני האיטרטורים ממוין בסדר עולה; מחזירה true אם כן, ובמקרה אחר מחזירה false
• is_sorted(starting_iterator, ending_iterator, comparing_function) - בודקת אם הטווח שמוגדר על ידי שני האיטרטורים ממוין, אך בהתאם לפונקציית ההשוואה.

vector<int> numbers = {3, 5, 1, 2, 4};

cout << is_sorted(numbers.begin(), numbers.end()) << endl;

sort(numbers.begin(), numbers.end());

cout << is_sorted(numbers.begin(), numbers.end());

Output:
0
1

bool compare(int a, int b)
{
	return a > b; // החזר 1 אם a גדול מ-b
}

int main()
{
	vector<int> numbers = {3, 5, 1, 2, 4};
	
	cout << is_sorted(numbers.begin(), numbers.end(), compare) << endl;
	
	sort(numbers.begin(), numbers.end(), compare);
	
	cout << is_sorted(numbers.begin(), numbers.end(), compare);

Output:
0
1

השיטה partial_sort

השיטה parital_sort() ממיינת את החצי הראשון של האיברים בטווח הנתון ומשאירה את החצי השני של האיברים כפי שהיו בתחילה. 
יש לה גם שתי גרסאות:

• partial_sort(start, middle, end) - ממיינת את הטווח מ-start עד end כך שהאיברים מאיטרטור ההתחלה ועד איטרטור האמצע ממוינים בסדר עולה, והאיברים מאיטרטור האמצע ועד איטרטור הסיום נשארים כפי שהיו בתחילה
• partial_sort(start, middle, end, compare) - ממיינת את הטווח מ-start עד end כך שהאיברים מ-start עד middle ממוינים בהתאם לפונקציית ההשוואה, והאיברים מ-middle עד end נשארים כפי שהיו בתחילה

vector<int> numbers = {3, 5, 1, 2, 4, 10, 7};

partial_sort(numbers.begin(), numbers.begin() + 4, numbers.end());

for(auto i = numbers.begin(); i != numbers.end(); i++)
		cout << *i << " ";

Output:
1 2 3 4 5 10 7

bool compare(int a, int b)
{
	return a > b; // החזר 1 אם a גדול מ-b
}

int main()
{
	vector<int> numbers = {3, 5, 1, 2, 4, 10, 7};
	
	partial_sort(numbers.begin(), numbers.begin() + 3, numbers.end(), compare);
	
	for(auto i = numbers.begin(); i != numbers.end(); i++)
		cout << *i << " ";

Output:
10 7 5 1 2 3 4

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

לעת עתה, זכרו מהו מיון, למדו היטב את השיטות sort() ו-is_sorted(), ותרגלו את השימוש בהן.