Youth-tory 유스토리

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));
    }
​
​
}
​

배열

순차적 접근속도 가장 빠름.

비순차적 삽입/삭제

크기 변경 불가

List

순서가 있으므로, 데이터의 중복 허용.

ArrayList

내부적으로 배열로 구현

배열크기 변경 가능. --> 크기를 미리 모를때 사용

순차적

LinkedList

Node로 구현

비순차적 삽입/삭제에 최적

접근성이 떨어진다. (인덱스가 없으므로 처음부터 하나씩 방문해야 함)

Set

순서가 없다.

주머니에 구슬을 넣는 모양. (중복된 데이터를 넣으면 구분이 불가능하므로 허용하지 않는다.)

중복불가. 중복된 데이터가 삽입 시도 -> 원래 데이터만 살아남고 중복된 데이터 삽입 불허.

HashSet

hasing기법을 사용해 중복 체크 O(1)

데이터가 많을떄 빠르게 검색할수 있는 가장 좋은 자료구조

TreeSet

Binary Search Tree로 중복 체크 O(logN)

정렬을 자주 실행해야 하는 경우.

Map

키 : 값

"바나나" : 5000

"사과" : 5000

key로 값을 구분할 수 있기 때문에 중복허용

단, key는 중복될 수 없다.

만약 중복 키가 들어오면 --> 덮어쓰기. (기존데이터 지우고) <Set과 비교>

왜? 키는 중복되더라도 새로운 데이터가 있을수 있기 때문.

HashMap

데이터가 많을떄 빠르게 검색할수 있는 가장 좋은 자료구조

TreeMap

정렬을 자주 실행해야 하는 경우.