Merge Sort 병합정렬

MergeSort

 

• 시간 복잡도 O(n lon n)

 

• list를 이용해 구현하기

x
/**
 * 
 * 병합정렬 - 리스트활용
 *
 */
​
import java.util.ArrayList;
import java.util.Arrays;
​
​
public class Z_MergeSort_List { //쪼개기
    public static ArrayList<Integer> MergeSort(ArrayList<Integer> m) {
        if(m.size()<=1) return m; //종료조건
        
        //반복조건
        ArrayList<Integer> left = new ArrayList<>();
        ArrayList<Integer> right= new ArrayList<>();
        int mid = m.size()/2;  //중간인덱스 찾기
        
        for(int i=0;i<mid;i++) {
            left.add(m.get(i));
        }
        
        for(int i=mid;i<m.size();i++) {
            right.add(m.get(i));
        }
        
//      m.subList(0, mid); 왼쪽 리스트
//      m.subList(mid, m.size()); 오른쪽리스트
        
        left = MergeSort(left);
        right = MergeSort(right);
        
        return merge(left,right);
    }
    
    public static ArrayList<Integer> merge(ArrayList<Integer>left, ArrayList<Integer>right){
        ArrayList<Integer> rst=new ArrayList<Integer>(left.size()+right.size()); //두개를 합친 큰 리스트
        int l=0, r=0;
        
        while(l<left.size() && r<right.size()) { //둘다 원소가 있는 경우
            if(left.get(l) < right.get(r)) {
                rst.add(left.get(l++));
            } else {
                rst.add(right.get(r++));
            }   
        }
        
        while(l<left.size()) { //왼쪽만 남아있는 경우
            rst.add(left.get(l++));
        }
        
        while(r<right.size()) { //오른쪽만 남아있는 경우
            rst.add(right.get(r++));
        }
        
//      while(left.size() > 0 || right.size()>0) {
//          if(left.size()>0 && right.size()>0) {
//              if(left.get(0)<=right.get(0)) {
//                  rst.add(left.get(0));
//                  left.remove(0);
//              } else {
//                  rst.add(right.get(0));
//                  right.remove(0);
//              }
//          } else if(left.size()>0) {
//              rst.add(left.get(0));
//              left.remove(0);
//          } else if(right.size()>0) {
//              rst.add(right.get(0));
//              right.remove(0);
//          } 
//      }
        return rst;
    }
    public static void main(String[] llgs) {
        Integer[] arr = {6,4,8,5,7,2,9,3,0,1};
        ArrayList ll= new ArrayList(Arrays.asList(arr)); //배열을 리스트로 바꾸기
​
        System.out.println(ll); //정렬 전
        
        System.out.println(MergeSort(ll)); //정렬 후
    }
}
​

 

• 배열을 이용해 구현하기

xxxxxxxxxx
/**
 * 
 * 병합정렬 - 배열활용
 *
 */
​
import java.util.Arrays;
​
public class Z22_MergeSort_Array {
    
    public static void mergeSort(int[] arr, int left, int right) { //쪼개기
        if(right-left <= 1) { //종료파트 : 배열을 실제로 쪼개지 않고, index를 활용해 쪼갠 효과를 준다.
            return;
        } else { //재귀파트
            int mid = (left+right)/2; //중간 index
            mergeSort(arr,left,mid );
            mergeSort(arr,mid,right );
            
            merge(arr,left,mid,right); //mid를 중심으로 영역을 반 나눔
            
            return ;
        }
        
    }
    
    public static void merge(int[] arr, int left, int mid, int right) { //합쳐서 하나의 정렬된 덩어리로 만들기
        int[] tmp = new int[right-left]; //두 영역을 하나로 합칠 큰 배열
        
        int l = left; //왼쪽 배열의 index
        int r = mid; //오른쪽 배열의 index
        int idx = 0; //병합할 배열의 index
        
        while(l<mid && r<right) { //왼쪽 오른쪽 모두 남아있는 경우
            if(arr[l]<arr[r]) {
                tmp[idx++]=arr[l++];
            } else {
                tmp[idx++]=arr[r++];
            }
        }
        
        System.arraycopy(arr, l, tmp, idx, mid-l); // 왼쪽만 남은경우
        System.arraycopy(arr, r, tmp, idx, right-r); // 오른쪽만 남은경우
        
//      while(l<mid) { //왼쪽만 남은 경우
//          tmp[idx++]=arr[l++];
//      }
//      
//      while(r<right) { //오른쪽만 남은 경우
//          tmp[idx++]=arr[r++];
//      }
        
        //합쳐진 temp를 arr에 덮어쓰기.
        //swap이 많이 일어나 arr에 직접하지 않음.
        System.arraycopy(tmp, 0, arr, left, tmp.length);
        
    }
​
    public static void main(String[] args) {
        int[] arr= { 6,4,8,5,7,2,9,3,0,1};
        mergeSort(arr,0,arr.length);//원본 배열을 직접 변경
        
        System.out.println(Arrays.toString(arr));
    }
​
​
}
​