정렬: 병합 정렬 알고리즘

Algorithm : 병합 정렬 알고리즘

: 배열을 앞부분과 뒷부분으로 나누어 각각 정렬한 다음 병합하는 작업을 반복하여 정렬을 수행

 

1. 병합 정렬 알고리즘의 순서

1. 배열의 앞부분을 병합 정렬로 정렬합니다.
2. 배열의 뒷부분을 병합 정렬로 정렬합니다.
3. 배열의 앞부분과 뒷부분을 병합합니다.

 

2. 병합 정렬 알고리즘의 시간복잡도

: O(n log n)

 

3. 병합 정렬 알고리즘 코드

출처 : https://www.acmicpc.net/problem/2822

2822번: 점수 계산

 

import java.util.Scanner;
import java.util.ArrayList;

class Score {
    
    private int index;
    private int score;
    
    public Score(int index, int score) {
        
        this.index = index;
        this.score = score;
        
    }
    
    public int getIndex() {
        
        return this.index;
        
    }
    
    public int getScore() {
        
        return this.score;
        
    }
    
}

class MergeSort {
    
    static int[] buf; // 작업용 배열
    
    // a[left] ~ a[right]까지 재귀적으로 병합 정렬
    static void __mergerSort(int[] a, int left, int right) {
        
        if(left < right) {
            
            int i;
            int center = (left + right) / 2;
            int p = 0;
            int j = 0;
            int k = left;
            
            __mergerSort(a, left, center);
            __mergerSort(a, center+1, right);
            
            for(i = left; i <= center; i++)
                buf[p++] = a[i]; // for문이 끝나면 i는 center와 같음
            
            while(i <= right && j < p)
                a[k++] = (buf[j] >= a[i]) ? buf[j++] : a[i++]; 
            
            while (j < p)
                a[k++] = buf[j++];
                
        }
        
    }
    
    static void mergeSort(int[] a, int n) {
        
        buf = new int[n];
        
        __mergerSort(a, 0, n-1);
        
        buf = null;
        
    }
    
}

public class Main
{
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
		
		int n = 8;
		
		int[] score = new int[n];
		ArrayList<Score> list = new ArrayList<Score>();
		int sum = 0;
		
		for(int i = 0; i < n; i++) {
		    
		    score[i] = stdIn.nextInt();
		    Score scores = new Score(i, score[i]);
		    list.add(scores);
		    
		}
		
		MergeSort Sort = new MergeSort();
        Sort.mergeSort(score, n);
    
        for (int i = 0; i < 5; i++) {
            
            sum += score[i];
            
		}
		
		for(int i = 0; i < n; i++) {
		    for(int j = 0; j < 5; j++) {
		        
		        if(list.get(i).getScore() == score[j]) {
		            
		            sb.append(i + 1).append(" ");
		            
		        }
		    
		    }
		}
        
		System.out.println(sum + "\n" + sb);
        
    }
}

 

4. Arrays.sort로 퀵 정렬과 병합 정렬하기

- java.util.Arrays 클래스가 제공하는 sort 메서드

static void sort(byte[] a)
static void sort(byte[] a, int fromIndex, int toIndex)
static void sort(char[] a)
static void sort(char[] a, int fromIndex, int toIndex)
static void sort(double[] a)
static void sort(double[] a, int fromIndex, int toIndex)
static void sort(int[] a)
static void sort(int[] a, int fromIndex, int toIndex)
static void sort(long[] a)
static void sort(long[] a, int fromIndex, int toIndex)
static void sort(short[] a)
static void sort(short[] a, int fromIndex, int toIndex)
static void sort(Object[] a)
static void sort(Object[] a, int fromIndex, int toIndex)
static <T> void sort(T[] a, Comparator<? super T> c)
static <T> void sort(T[] a, int fromIndex, int toIndex, Comparator<? super T> c)

여기서 자연정렬이 필요하지 않은 배열은 요소의 대소 관계를 비교할 때 comparator c를 사용하여 정렬합니다.

 

- Comparator C를 사용하여 정렬

static final Comparator<Class> SORT_WHAT = new SortWhatComparator();

private static class SortWhatComparator implements Comparator<PhyscData> {
	public int compare(Class c1, Class c2) {
    	return (c1.element > c2.element) ? 1 :
        	(c1.element < c2.element) ? -1 : 0;
    }
}