נתון מערך חד-ממדי arr באורך n ובתוכו מספרים שלמים שונים זה מזה.
נגדיר: חציון (median) של המערך arr, הוא המספר במערך ש-n/2 מהאיברים במערך קטנים ממנו ו-n/2 מהאיברים במערך גדולים ממנו. אם מספר התאים במערך הוא זוגי, אנחנו נגדיר שהחציון הוא המספר במערך ש-n/2-1 מהאיברים במערך קטנים ממנו ו-n/2-1 מהאיברים במערך גדולים ממנו.
לדוגמה, במערך להלן המספר 1 הוא החציון. שכן האיברים, 5-, 3-, 0 קטנים ממנו והמספרים 2, 7, 4 גדולים ממנו.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 4 | -5 | -3 | 1 | 2 | 7 | 0 |
נגדיר את arr מערך-זיגזגי (wiggly-array) אם מתקיים:
arr[0] > arr[1] < arr[2] > arr[3] < arr[4] > ... > arr[n-2] < arr[n-1]
כאשר המערך באורך זוגי (ואז האיבר הלפני-אחרון קטן מהאחרון):
arr[0] > arr[1] < arr[2] > arr[3] < arr[4] > ... < arr[n-1]
כלומר, כל האיברים באינדקסים זוגיים הם נקודות מקסימום מקומיות, וכל האיברים באינדקסים זוגיים הם נקודות מינימום מקומיות.
אין דרישה לסדר בין איברים שאינם שכנים.
בהינתן מערך חד-ממדי מלא במספרים שלמים, שאיבריו שונים זה מזה, ומספר שלם med שהוא החציון של המערך. יש לסדר את המערך כך שהוא יהיה מערך-זיגזגי. אין חשיבות לסדר מסוים בין איברים שאינם שכנים.
השיטה צריכה להיות יעילה ככל הניתן, גם מבחינת סיבוכיות הזמן וגם מבחינת סיבוכיות המקום.
arr = [4, -5, -3, 1, 2, 7, 0], med = 1
[4, -5, 1, -3, 7, 0, 2]
הסבר: סידור אפשרי שמקיים את תנאי הזיגזג
arr = [1, 2, 3, 4], med = 2
[2, 1, 4, 3]
הסבר: סידור אפשרי למערך באורך זוגי
arr = [5, 1, 3], med = 3
[5, 1, 3]
הסבר: המערך כבר מסודר בצורת זיגזג
arr = [1, 3, 2, 4, 5], med = 3
[3, 1, 4, 2, 5]
הסבר: סידור אפשרי שמקיים את תנאי הזיגזג
arr = [2], med = 2
[2]
הסבר: מערך באורך 1 תמיד מקיים את התנאי
arr = [7, -3, 1, -5, 4, 0, 2], med = 1
[7, -3, 1, -5, 4, 0, 2]
הסבר: סידור אפשרי שמקיים את תנאי הזיגזג
arr = [9, -7, 0, 4, 1, 2, -5], med = 1
[9, -7, 4, 0, 2, -5, 1]
הסבר: סידור אפשרי שמקיים את תנאי הזיגזג
arr = [1, 2], med = 1
[2, 1]
הסבר: סידור אפשרי למערך באורך 2
קלט:
arr = [4, -5, -3, 1, 2, 7, 0], med = 1
הפלט המבוקש:
[4, -5, 1, -3, 7, 0, 2]