278
0

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

278
זמן קריאה: 2 דקות

הבעיה: מיון מערך בצורה של גלים.

בהינתן מערך של שלמים, המשימה שלנו היא למיין את המערך בצורה של “גלים”, כלומר, שהמערך לאחר מיון יקיים את החוקיות הבאה: a1 >= a2 <= a3 >= a4 <= a5 וכן הלאה..

הערות ודגשים

  1. סביר להניח שיהיו כמה פלטים אפשריים – במצב כזה אנו נדרשים להחזיר את התשובה הלקסיקוגרפית הראשונה.

תחילה, נפענח את הכתוב, הרמזים ואת הנחות העזר (במידה וקיימות) שיש לנו:

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

קלט: מערך שלמים, לדוגמא: [1,2,3]

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

הפתרון

הרעיון: ראשית, נמיין את המערך (מה שיבטיח את הלקסיקוגרפיות בהמשך), ולאחר מכן נרוץ על המערך ונחליף זוגות.

כלומר, בהינתן הקלט [2,1,5,7], ראשית נמיין ונקבל [1,2,5,7]. לאחר שלב החלפת הזוגות נקבל [2,1,7,5] כמצופה.

ובצורה ויזואלית יותר:

המערך לאחר המיון

המערך לאחר החלפת האיברים

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

גרסת Python:

				
					def wave(A):
    A.sort()

    for index in range(0,len(A)-1,2):
        A[index], A[index+1] = A[index+1], A[index]
        
    return A
				
			

גרסת #C:

				
					
using System;

class SortWave {
	
	void swap(int[] arr, int a, int b)
	{
		int temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}

	// This function sorts arr[0..n-1] in wave form, i.e.,
	// arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4]..
	void sortInWave(int[] arr, int n)
	{
		// Sort the input array
		Array.Sort(arr);

		// Swap adjacent elements
		for (int i = 0; i < n - 1; i += 2)
			swap(arr, i, i + 1);
	}

	// Driver method
	public static void Main()
	{
		SortWave ob = new SortWave();
		int[] arr = { 10, 90, 49, 2, 1, 5, 23 };
		int n = arr.Length;
		
		ob.sortInWave(arr, n);
		for (int i = 0; i < n; i++)
		Console.Write(arr[i] + " ");
	}
}

				
			

סיבוכיות:

סיבוכיות זמן ריצה: O(nlogn)
סיבוכיות מקום: O(1)

במקרה זה בחרנו להשתמש במיון מובנה של רשימה (sort) במקום במיון ע”י sorted ובכך חסכנו הקצאת רשימה נוספת.

ענו בעצמכם:

  1. האם קיים פתרון יעיל יותר בהינתן זה שנוכל להחזיר איזשהי פרמוטציה של הפלט ולאו דווקא את הלקסיקוגרפית הראשונה?
  2. בהינתן שהתשובה לשאלה הראשונה היא כן, מה יהיה מספר ההשוואות אותן נצטרך לעשות באלגוריתם?
  3. הפתרון יעבוד במידה וישנם ערכים שווים במערך?
  4. הפתרון יעבוד במידה והמערך באורך אי זוגי?
עומרי נעים
WRITEN BY

עומרי נעים

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

כתיבת תגובה

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