알고리즘: 분할 합병 정렬

알고리즘 이해하기

분할합병 정렬이란 선택정렬이나 삽입정렬을 할때보다 수행시간이 짧게 걸린다는 장점이 있는 정렬방법으로서 lonN의 수행시간을 가진다.
선택,삽입정렬의 경우 for문이 중첩되어 돌아가기때문에 N^2의 수행시간을 가지는 것에 비해 상당히 빠른축에 속한다.

분할합병정렬은 기본적으로 정렬할 객체를 2개씩 나눠서 각각 정렬하는 것을 기본으로 한다. 이렇게 2개씩 나누는 과정은 제작자에 따라 최소단위까지 나눠질때까지 하는 경우도 있고 적당한 수에서 멈추는 경우도 존재한다.

static void mergesort(int arr[],int from, int to){
	
    if(from == to) return;
    int c = (from+to)/2;
    
    //각각 선택정렬
    selectsort(arr, from, c);
    selectsort(arr,c+1,to);
    //각 부분을 가지고 다시 재조립
    int i = from;
    int j = c+1;
    int k =from;
    
    int t[] = new int[n+1]
    while (i <= c && j <= to) {
		if(arr[i] < arr[j]) 
        	t[k++] = arr[i++];
        // t배열에 첫수는 arr[i]       
    }
    // 이미 c까지의 배열은 정렬된상태이기에 t에다가 그대로 넣으면됨
    while(i <=c) {
		t[k++] = arr[i++];
        }
        
    // c+1부터의 배열도 마찬가지 이미 정렬된 상태이다
    while(j<=to) {
    	
        t[k++] = arr[j++];
        
    }
    
    //t 배열을 arr로 복사
    for(int m= from;m <=to; m ++){
    	arr[m] =t[m];
    }
    

  
   

이게 분할정렬의 총 알고리즘이다.

selectsort(int arr[]; int from; int to){
	int min =o;
    //최소값을 가지는 자리수를 찾는 알고리즘
    for(int i=from; i<=to ; i++){

		min = i;
        for(int j =i; j<=to; j++){
        	if(arr[j] <arr[min]) 
            	min = j;
            }
     	
        int last = arr[min];
        arr[min] = arr[i];
        arr[i] = last;
        
        }
       }
        
        

선택정렬 알고리즘이다