מיזוג מערכים ממויינים

Published on
Authors
  • avatar
    Name
    Yonatan Snir

ישנן כמה דרכים לכתוב את האלגוריתם הזה אך במדריך זה אכתוב בצורה הפשוטה ביותר כך שתתאים גם לחבר'ה שכותבים ב-C. מי שכותב ב-JavaScript בלבד יכול כמובן לשנות את הקוד ולהשתמש בפונקציות המובנות של השפה (push). נתחיל...

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

function mergeSortedArr(arr1, arr2){
  let length = arr1.length + arr2.length;
  const sortedArr = new Array(length);

  return sortedArr;
}

אנחנו כותבים משתנה length מחזיק לנו את האורך של שני המערכים, ואז יוצרים מערך חדש sortedArr באורך של המשתנה שלנו. כתיבה כזאת ב-JavaScript שוות ערך לכתיבת sortedArr[length] ב-C.

עכשיו אחרי שיש לנו את המערך בגודל הדרוש, אנחנו יכולים להתחיל לרוץ על שני המערכים ולחבר בניהם. אנחנו כבר יודעים שהלולאה שלנו צריכה לרוץ length פעמים, פעם אחת על כל מיקום במערך החדש.

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

let p1 = 0, p2 = 0; // the indexes of the arrays

  for (let i = 0; i < length; i++){
    if (arr1[p1] < arr2[p2]){ // Which one is bigger?
      sortedArr[i] = arr1[p1];
      p1++;
    } else {
      sortedArr[i] = arr2[p2];
      p2++
    }
  }

והפונקציה במלואה:

function mergeSortedArr(arr1, arr2){
  let length = arr1.length + arr2.length;
  const sortedArr = new Array(length);
  let p1 = 0, p2 = 0; // the indexes of the arrays

  for (let i = 0; i < length; i++){
    if (arr1[p1] < arr2[p2]){ // Which one is bigger?
      sortedArr[i] = arr1[p1];
      p1++;
    } else {
      sortedArr[i] = arr2[p2];
      p2++
    }
  }

  return sortedArr;
}

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