מיון מיזוג

מיון מיזוג (באנגלית: Merge Sort) הוא אלגוריתם מיון רקורסיבי המתבסס על מיזוגם של מערכים ממוינים.

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

תיאור האלגוריתם

המחשה של מיון מיזוג של מערך המספרים {6,5,3,1,8,7,2,4}

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

מימוש מילולי

ברמה העקרונית, עובד מיון-מיזוג בצורה הבאה:

מיין-מזג n איברים

  1. אם n=1 (המערך של איבר אחד ממילא ממוין (באופן ריק)) חזור
  2. מיין-מזג את n/2 האיברים הראשונים
  3. מיין-מזג את n/2 האיברים האחרונים
  4. מזג את 2 תוצאות המיון

בפסאודו קוד, המזכיר את שפת C, יראה האלגוריתם כך:

mergesort(Array m)
{
     if length(m) ≤ 1
         return m
     else
     {
         middle = length(m) / 2
         for each x in m up to middle
             add x to left
         for each x in m after middle
             add x to right
         left = mergesort(left)
         right = mergesort(right)
         result = merge(left, right)
         return result
     }
}

מימוש המיזוג

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

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

בפסאודו קוד יראה המיזוג כך:

merge(left,right)
{
    while length(left) > 0 and length(right) > 0
    {
        if first(left) ≤ first(right)
        {
            append first(left) to result
            left = rest(left)
        }
        else
        {
            append first(right) to result
            right = rest(right)
        }
    }
    if length(left) > 0
        append left to result
    if length(right) > 0 
        append right to result
    return result
}

להמחשה, נמזג את קבוצות המספרים הממוינות: 1,2,4,8,9,10,11 ו-3,7.

  • האיברים הראשונים הם 1 ו-3. 1 קטן מ-3 ולכן נכניס את 1.
  • כעת האיברים הראשונים הם 2 (1 הוכנס) ו-3 (לא טיפלנו בו עדיין). 2 קטן מ-3 ולכן נכניס את 2.
  • כעת האיברים הראשונים הם 4 ו-3. 3 קטן מ-4 ולכן נכניס את 3.
  • כעת האיברים הראשונים הם 4 ו-7. 4 קטן מ-7 ולכן נכניס את 4.
  • כעת האיברים הראשונים הם 8 ו-7. 7 קטן מ-8 ולכן נכניס את 7.
  • שים לב שלא נותרו עוד מספרים בקבוצת המספרים השנייה, נכניס את יתר קבוצת המספרים הראשונה: 8,9,10,11.

נראה כעת מהו המערך שהתקבל: 1,2,3,4,7,8,9,10,11. אלו הם בדיוק כל המספרים כאשר הם ממוינים כפי שציפינו.

דוגמה למימוש בשפת C++

#include <iostream>
#include <time.h>

using namespace std;
const int ARR_LENGTH = 1000;

void merge (int arr [], int temp [], int left, int mid, int right)
{
	int leftPlace = left, rightPlace = mid +1;
	bool leftOver = false,	//all the left data was merged
		 rightOver = false;	//all the right data was merged
	
	
	for  (int place = left; place <= right; place++)
	{
		if (leftPlace > mid) leftOver = true;
		if (rightPlace > right) rightOver = true;
		
		temp [place] = (rightOver || !leftOver && arr [leftPlace] <= arr [rightPlace])?	//the merge
						arr [leftPlace ++] : arr [rightPlace ++];
	}
	for (int i = left; i <= right; i++)	//return the merged data into the array
		arr [i] = temp [i];
}

void mergeSort (int arr [], int temp [], int left, int right)
{
	int mid = (right + left) /2;
	
	if (mid > left)	//more than one cell
		mergeSort (arr, temp, left, mid);
	
	if (right > mid +1)	//more than one cell
		mergeSort (arr, temp, mid +1, right);
	
	merge (arr, temp, left, mid, right);
}
 
void sort (int arr [])
{
	int temp [ARR_LENGTH];	//array aid
	
	mergeSort (arr, temp, 0, ARR_LENGTH -1);
}

int main()
{
	srand ( (unsigned int) (time(NULL)));	//init the rand
	
	int arr [ARR_LENGTH];

	for (int i =0; i < ARR_LENGTH; i++)
		 arr [i] = rand () % 100;	//insert data

	for (int i =0; i < ARR_LENGTH; i++)
		cout << arr [i] << " ";		//print before sorting
	cout << endl << endl;

	sort (arr);	

	for (int i =0; i < ARR_LENGTH; i++)
		cout << arr [i] << " ";		//print after sorting
	cout << endl;
	
	return (EXIT_SUCCESS);
}

דוגמה למימוש בשפת C

#include<stdio.h>
#define MAX 100

void mergeSort(int arr[], int low, int mid, int high);
void partition(int arr[], int low, int high);

int main()
{

	int merge[MAX] = { 0 };
	int i = 0;
	int n = 0;

	printf("Enter the number of elements in the array to sort (maximum %d elements): ", MAX);
	scanf("%u", &n);

	printf("Enter the value of the elements sort (type ENTER after each value): ");
	for (i = 0; i < n; i++)
	{
		scanf("%d", &merge[i]);
	}

	partition(merge, 0, n - 1);

	printf("After merge sorting elements are: ");
	for (i = 0; i < n; i++)
	{
		printf("%d ", merge[i]);
	}
	
	return 0;
}

void partition(int arr[], int low, int high)
{
	int mid = 0;

	if (low < high)
	{
		mid = (low + high) / 2;
		partition(arr, low, mid);
		partition(arr, mid + 1, high);
		mergeSort(arr, low, mid, high);
	}
}

void mergeSort(int arr[], int low, int mid, int high)
{
	int i = 0;
	int m = 0;
	int k = 0;
	int l = 0;
	int temp[MAX];

	l = low;
	i = low;
	m = mid + 1;

	while ((l <= mid) && (m <= high))
	{
		if (arr[l] <= arr[m])
		{
			temp[i] = arr[l];
			l++;
		}
		else
		{
			temp[i] = arr[m];
			m++;
		}
		i++;
	}

	if (l > mid)
	{
		for (k = m; k <= high; k++)
		{
			temp[i] = arr[k];
			i++;
		}
	}
	else
	{
		for (k = l; k <= mid; k++)
		{
			temp[i] = arr[k];
			i++;
		}
	}

	for (k = low; k <= high; k++)
	{
		arr[k] = temp[k];
	}
}

דוגמה למימוש בשפת python 3

def mergeSort(alist):
    print("Splitting ",alist)
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i=0
        j=0
        k=0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] <= righthalf[j]:
                alist[k]=lefthalf[i]
                i=i+1
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1

        while i < len(lefthalf):
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j < len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1
    print("Merging ",alist)

alist = [54,26,93,17,77,31,44,55,20]
mergeSort(alist)
print(alist)

דוגמת הרצה

השרטוט הבא מדגים כיצד ממיין האלגוריתם מערך בגודל 7 המכיל את הערכים: 38,27,43,3,9,82,10.

הדמיית הרצה של אלגוריתם מיון מיזוג על מערך של שבעה מספרים.
הדמיית הרצה של אלגוריתם מיון מיזוג על מערך של שבעה מספרים.

ניתוח סיבוכיות מיון-מיזוג

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

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

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

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

קבלנו שמתרחשות פעולות מיזוג שסיבוכיות זמן הריצה של כל אחת מהן היא .

סה"כ סיבוכיות זמן הריצה של האלגוריתם היא, אם כן, .

קיימת גם גרסה מקבילית של האלגוריתם המשתמשת ב מעבדים ופועלת בסיבוכיות של .

קישורים חיצוניים

ויקישיתוף מדיה וקבצים בנושא מיון מיזוג בוויקישיתוף

Read other articles:

Aureolus dari Promptuarii Iconum Insigniorum Manius Acilius Aureolus (meninggal 268) adalah komandan militer Romawi dan kemudian menjadi pemberontak. Dia adalah satu dari Tiga Puluh Tiran yang muncul pada masa kekuasaan kaisar Gallienus. Dia berasal dari etnis Thrakia-Romawi dan dibesarkan oleh kaisar Gallienus. Dia terbukti menjadi salah satu prajurit paling brilian dan inovatif pada masanya. Akan tetapi dia malah beralih melawan kaisar yang telah membesarkannya. Pada akhirnya dia terbunuh d...

 

August Wilhelm IfflandNama dalam bahasa asli(de) August Wilhelm Iffland BiografiKelahiran19 April 1759 Hannover Kematian22 September 1814 (55 tahun)Berlin Tempat pemakamanFriedhof IV der Gemeinde Jerusalems- und Neue Kirche (en) KegiatanPekerjaanPenulis drama, penulis, aktor panggung dan otobiografer Bekerja diNational Theatre Mannheim (en) MuridKaroline Jagemann (en) KeluargaPasangan nikahLuise Iffland (en) SaudaraChristian Philipp Iffland (en) dan Louise Eisendecher (en) August Wilhelm Iffl...

 

A.C.E에이스Informasi latar belakangAsalSeoul, Korea SelatanGenreK-popHardstyleDubstepTahun aktif2017 (2017)–sekarangLabelBeat InteractiveSitus webwww.beatkor.comAnggota Jun Donghun Wow Byeongkwan Chan A.C.E (Hangul: 에이스; akronim untuk Adventure Calling Emotions) adalah boyband Korea Selatan yang dibentuk oleh Beat Interactive. Grup ini terdiri dari lima anggota: Jun, Donghun, Wow, Byeongkwan, dan Chan. Grup ini mendapat perhatian dari kegiatan busking [1] mereka. A.C.E...

Peta menunjukkan lokasi Carmen. Untuk kegunaan lain, lihat Carmen. Carmen adalah munisipalitas yang terletak di provinsi Agusan del Norte, Filipina. Pada tahun 2011, munisipalitas ini memiliki penduduk sebesar 18.690 jiwa atau 4.063 rumah tangga.[1] Pembagian wilayah Carmen terbagi menjadi 8 barangay, yaitu: Barangay Luas wilayah(km2) BarangayCaptain Cahayagan 6.23 Baltazar, Jimlan Gosoon 6.89 Pepito, Danilo Manoligao 67.12 Cabatingan, Alfreda Poblacion 92.97 Samaco, Gilda Rojales 14....

 

Pembangunan nasional Indonesia adalah paradigma Pembangunan yang terbangun atas pengamalan Pancasila yaitu pembangunan manusia Indonesia seutuhnya dan pembangunan masyarakat Indonesia seluruhnya, dengan Pancasila sebagai dasar, tujuan, dan pedomannya.[1] Dari amanat tersebut disadari bahwa pembangunan ekonomi bukan semata-mata proses ekonomi, tetapi suatu penjelmaan pula dari proses perubahan politik, sosial, dan budaya yang meliputi bangsa, di dalam kebulatannya.[1] Pembangu...

 

Waktu Standar Filipina atau UTC+08:00 adalah zona waktu standar yang dipakai di zona waktu yang dipakai di Filipina. Zona waktu ini sama dengan yang dipakai di Indonesia bagian tengah (WITA) dan Singapura-Malaysia. Referensi Pranala luar http://www.worldtimezone.com/wtz-names/wtz-pht.html http://www.timeanddate.com/worldclock/timezone.html?n=145 http://cpan.uwinnipeg.ca/htdocs/DateTime-TimeZone/DateTime/TimeZone/Asia/Manila.pm.html Diarsipkan 2006-01-19 di Wayback Machine. Artikel bertopik Fi...

Federasi Sepak Bola Guinea KhatulistiwaCAFDidirikan1975[1]Kantor pusatMalaboBergabung dengan FIFA1986Bergabung dengan CAF1986PresidenAndrés Jorge Mbomio Nsem AbuaWebsitefeguifut.org Federasi Sepak Bola Guinea Khatulistiwa (bahasa Spanyol: Federación Ecuatoguineana de Fútbol, FEGUIFUT) adalah badan pengendali sepak bola di Guinea Khatulistiwa. Kompetisi Badan ini menyelenggarakan beberapa kompetisi di Guinea Khatulistiwa, termasuk Divisi Utama Guinea Khatulistiwa yang merupakan ...

 

Halaman pertama dan terakhir dari konstitusi 1871, dengan tanda tangan Wilhelm, Kaisar Jerman dan Raja Prusia Skema sederhana konstitusi Jerman 1871 Konstitusi Kekaisaran Jerman (Jerman: Verfassung des Deutschen Reichescode: de is deprecated ) adalah hukum dasar dari Kekaisaran Jerman pada 1871-1919, yang dibuat pada 16 April 1871.[1] Para sejarawan Jerman sering menyebutnya sebagai konstitusi kekaisaran Bismarck, yang dalam bahasa Jerman disebut Bismarcksche Reichsverfassung. Konstit...

 

Sceaux 行政国 フランス地域圏 (Région) イル=ド=フランス地域圏県 (département) オー=ド=セーヌ県郡 (arrondissement) アントニー郡小郡 (canton) 小郡庁所在地INSEEコード 92071郵便番号 92330市長(任期) フィリップ・ローラン(2008年-2014年)自治体間連合 (fr) メトロポール・デュ・グラン・パリ人口動態人口 19,679人(2007年)人口密度 5466人/km2住民の呼称 Scéens地理座標 北緯48度4...

Miguel Hidalgo y Costilla International AirportAeropuerto Internacional Miguel Hidalgo y CostillaIATA: GDLICAO: MMGL GDLLocation of airport in MexicoInformasiJenisPublicPengelolaGrupo Aeroportuario del PacificoMelayaniGuadalajara, JaliscoLokasiTlajomulco de Zuñiga, JaliscoMaskapai penghubung Aeroméxico Connect Volaris VivaAerobus Ketinggian dpl1,529 mdplKoordinat20°31′18″N 103°18′40″W / 20.52167°N 103.31111°W / 20.52167; -103.31111Koordinat: 20�...

 

莎拉·阿什頓-西里洛2023年8月,阿什頓-西里洛穿著軍服出生 (1977-07-09) 1977年7月9日(46歲) 美國佛羅里達州国籍 美國别名莎拉·阿什頓(Sarah Ashton)莎拉·西里洛(Sarah Cirillo)金髮女郎(Blonde)职业記者、活動家、政治活動家和候選人、軍醫活跃时期2020年—雇主內華達州共和黨候選人(2020年)《Political.tips》(2020年—)《LGBTQ國度》(2022年3月—2022年10月)烏克蘭媒�...

 

التاريخ الاقتصادي للحرب العالمية الأولىمعلومات عامةوصفها المصدر الموسوعة السوفيتية الكبرى التأثيراتفرع من الحرب العالمية الأولى تعديل - تعديل مصدري - تعديل ويكي بيانات ملصق بريطاني يشجع على الاستثمار في أذون الحرب. يغطي التاريخ الاقتصادي للحرب العالمية الأولى الأساليب ...

Vladimir Vasilyevich KovalyonokAntariksawan Vladimir Kovalyonok di VologdaLahir3 Maret 1942 (umur 82)Beloye, Oblast Minsk, RSS Belarusia Uni SovietKebangsaanSoviet / RusiaPekerjaanPilotPenghargaanPahlawan Uni Soviet (dua kali)Karier luar angkasaAntariksawanPangkatKolonel Jenderal, Angkatan Udara SovietMisiSoyuz 25, Soyuz 29/Soyuz 31, Soyuz T-4 Vladimir Vasiliyevich Kovalyonok (bahasa Belarus: Уладзі́мір Васі́льевіч Кавалёнак; bahasa Rusia: Влад�...

 

Uezd in Caucasus, Russian EmpireKazakh uezd Казахскій уѣздъUezd Coat of armsLocation in the Elizavetpol GovernorateCountryRussian EmpireViceroyaltyCaucasusGovernorateElizavetpolEstablished1868Abolished1929CapitalKazakh(present day Qazax)Area • Total5,800.16 km2 (2,239.45 sq mi)Population (1916) • Total137,049 • Density24/km2 (61/sq mi) • Rural100.00% The Kazakh uezd[a] was a county (uezd) of the Eli...

 

artikel ini perlu dirapikan agar memenuhi standar Wikipedia. Tidak ada alasan yang diberikan. Silakan kembangkan artikel ini semampu Anda. Merapikan artikel dapat dilakukan dengan wikifikasi atau membagi artikel ke paragraf-paragraf. Jika sudah dirapikan, silakan hapus templat ini. (Pelajari cara dan kapan saatnya untuk menghapus pesan templat ini) The Fast and The Furious: Tokyo DriftPoster BioskopSutradaraJustin LinProduserNeal H. MoritzDitulis olehChris MorganBerdasarkanKarakter:Gary Scott...

Disambiguazione – Se stai cercando altri significati, vedi Menelao (disambigua). Questa voce o sezione sull'argomento mitologia non cita le fonti necessarie o quelle presenti sono insufficienti. Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Segui i suggerimenti del progetto di riferimento. Menelao SagaCiclo Troiano Nome orig.Μενέλαος (Menélaos) Lingua orig.greco antico AutoreOmero 1ª app. inI...

 

本條目存在以下問題,請協助改善本條目或在討論頁針對議題發表看法。 此條目需要补充更多来源。 (2019年6月29日)请协助補充多方面可靠来源以改善这篇条目,无法查证的内容可能會因為异议提出而被移除。致使用者:请搜索一下条目的标题(来源搜索:盾之勇者成名錄角色列表 — 网页、新闻、书籍、学术、图像),以检查网络上是否存在该主题的更多可靠来源(判定...

 

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article is missing information about the film's production. Please expand the article to include this information. Further details may exist on the talk page. (December 2017) This article's lead section may be too short to adequately summarize the key points. Please consider expanding the lead to provide an accessible overview of all im...

Объявления проституток в телефонной будке: такая реклама не является законной, но широко практикуется[1] Проституция в Великобритании является легальной деятельностью[2], но с 2009 года контакт с проституткой, которую принудили заниматься торговлей телом, уголо...

 

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。(このテンプレートの使い方)出典検索?: バードランド – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2020年7月) 44丁目にあるバードランド(2008年、撮影 バー...