[24/11/30] 머지소트

 

 

Arrays.sort하면 끝나긴 하지만 머지소트로 구현해봤다.

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      String n = st.nextToken();
      char[] arr = n.toCharArray();
      int[] numArr = new int[arr.length];
      for(int i=0; i<numArr.length; i++){
        numArr[i]= arr[i]-'0';
      }
      mergeSort(numArr,0,numArr.length-1);
      for(int i=0; i<numArr.length; i++){
        System.out.printf("%d",numArr[i]);
      }   
  }
  
  public static void mergeSort(int[] arr,int startIndex , int endIndex){
    int[] temp = new int[endIndex-startIndex+1];
    if(startIndex>=endIndex){
      return;
    }
    int s1=startIndex;
    int mid = (endIndex+startIndex)/2;
    int s2=mid+1;
    int index=0;
    
    mergeSort(arr,startIndex,mid);
    mergeSort(arr,s2,endIndex);
    
    while(s1<=mid && s2<=endIndex){
      if(arr[s1]>arr[s2]){
        temp[index++]=arr[s1++];
      }
      else{
        temp[index++]=arr[s2++];
      }
    }
    if(s1>mid){
      for(int i=index; i<temp.length; i++){
        temp[i]=arr[s2++];
      }
    }
    else if(s2>endIndex){
      for(int i=index; i<temp.length; i++){
        temp[i]=arr[s1++];
      }
    }
    int j=startIndex;
    for(int i=0; i<temp.length; i++){
      arr[j++]=temp[i];
    }
    
    
    return;
    
  }
  
}

 

병합과정에 포인트가 있다.

1) 병합하면서 투포인를 쓴다. 합칠려는 배열 2개에 각각 시작 포인터 잡고 비교해가면서 임시 배열에 넣으면 된다. (O(2N))

2) 하나의 포인터를 다 떙겼을때는 남은 한 배열을 그대로 넣으면 된다.