합병 정렬.

정렬 방법론.

ex) 리스트 A = [6, 2, 8, 1, 3, 9, 4, 5, 10 ,7]이 있다고 하자.

1. 리스트 A를 이등분하여 L=[6, 2, 8, 1, 3], R=[9, 4, 5, 10, 7]로 나눈다.

2. L과 R을 각각 정렬하자.

3. 두 리스트 L과 R을 합병하자.

더 참고

http://dntkrl79.blog.me/220733261240

http://blog.naver.com/goldtop0307/80105554620

합병하는 방법.

i, j가 각각 있고 i,j중 작은것부터 k위치에 차례차례 들어간다.

특징.

1. 기억장소가 많이 필요하다.(기본 리스트가 100개면 100개의 새로운 기억장소가 필요하다.)

좋은 예제.

번호 순서대로 진행되며 왼쪽으로 먼저 쭉 간 다음에 더 나눌게 없으면 밑으로 내려가고 합병 후에 서서히 위로 올라온다. 순서 잘 보기.

시간복잡도 : NlogN, 

c언어 소스.

// ConsoleApplication5.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다.
//

#include "stdafx.h"
#include <iostream>
#include <time.h>
#include <stdlib.h>
using namespace std;

const int N=10000;
int b[N+1];

void MergeSort(int a[], int l, int r)
{
	int i,j,k,m;
	if(r>l)
	{
		m = (r+l)/2;
		MergeSort(a,l,m);
		MergeSort(a,m+1,r);
		for(i=m+1;i>l;i--) 
			b[i-1] = a[i-1];
		for(j=m;j<r;j++) 
			b[r+m-j] = a[j+1];
		for(k=l;k<=r;k++)
		{
			if (b[i] < b[j])
			{
			   a[k] = b[i];
			   i += 1;
			}
			else 
			{
			   a[k] = b[j];
			   j -= 1;
			}
		}
	}
}

int main(void) { 

	int i,a[N+1];
	double start_time;

	srand(time(NULL));
	for(i=1;i<=N;i++) a[i] = rand();

	start_time = clock();
	MergeSort(a,1,N);
	cout<<"합병 정렬의 실행 시간 (N = "<<N<<") : "<<clock() - start_time<<endl;
	return 0; 
} 

파이썬

# -*- encoding: utf-8 -*-
import random
import time

N = 10000
def CheckSort(a,n):
    Sorted = True
    for i in range(n):
        if a[i] > a[i+1]:
            Sorted = False
        if not Sorted:
            break
    if Sorted: print u'정렬 완료.'
    else: print u'정렬 오류 발생.'

def QuickSort(a,l,r):
    if r>l:
        v = a[r]
        i = l-1
        j = r
        while True:
            while True:
                i += 1
                if a[i]>=v: break
            while True:
                j -= 1
                if a[j]<=v: break
            if i>=j: break
            swap(a,i,j)
        swap(a,i,r)
        QuickSort(a,l,i-1)
        QuickSort(a,i+1,r)
        
b = [0 for i in xrange(N+1)]
def MergeSort(a,l,r):
    if r>l:
        m = (r+l)/2
        MergeSort(a,l,m)
        MergeSort(a,m+1,r)
        i = m+1
        while i>l:
            b[i-1] = a[i-1]
            i -= 1
        j = m
        while j<r:
            b[r+m-j] = a[j+1]
            j += 1
        k = l
        while k<=r:
            if b[i] < b[j]:
                a[k] = b[i]
                i += 1
            else:
                a[k] = b[j]
                j -= 1
            k += 1

def main():
    a = [random.randint(1,65536) for i in range(0,N+1)] 
    start_time = time.time()
    MergeSort(a,0,N)
    print a[:10]
    print u'(랜덤)선택 정렬의 실행 시간 (N = {} ) : {}'.format(N,time.time()-start_time)
    CheckSort(a,N)
 
    a = [i for i in range(0,N+1)] 
    a[0] = -1
    start_time = time.time()
    MergeSort(a,0,N)
    print u'(최고)선택 정렬의 실행 시간 (N = {} ) : {}'.format(N,time.time()-start_time)
    CheckSort(a,N)
 
    a = [i for i in range(N,-1,-1)] 
    a[0] = -1
    start_time = time.time()
    MergeSort(a,0,N)
    print u'(최악)선택 정렬의 실행 시간 (N = {} ) : {}'.format(N,time.time()-start_time)
    CheckSort(a,N)
 
if __name__=='__main__':
    main()