패스트캠퍼스 챌린지 11일차

병합 정렬 (Merge Sort)

 - 재귀용법을 활용한 정렬 알고리즘

   1. 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.

   2. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.

   3. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

 

 

병합정렬 예시

 

 단계별 이해

  1단계 : 정렬되지 않은 배열을 끝까지 분리하는 단계

  2단계 : 분리한 데이터를 단계별로 합치는 단계

import java.util.ArrayList;
import java.util.Collections;

public class MergeSort {
    public ArrayList<Integer> mergeFunc(ArrayList<Integer> leftList, ArrayList<Integer> rightList) {
        ArrayList<Integer> mergedList = new ArrayList<Integer>();
        int leftPoint = 0;
        int rightPoint = 0;

         // CASE1: left/right 둘 다 있을 때
        while (leftList.size() > leftPoint && rightList.size() > rightPoint) {
            if (leftList.get(leftPoint) > rightList.get(rightPoint)) {
                mergedList.add(rightList.get(rightPoint));
                rightPoint += 1;
            } else {
                mergedList.add(leftList.get(leftPoint));
                leftPoint += 1;
            }
        }

        // CASE2: right 데이터가 없을 때
        while (leftList.size() > leftPoint) {
            mergedList.add(leftList.get(leftPoint));
            leftPoint += 1;
        }

        // CASE3: left 데이터가 없을 때
        while (rightList.size() > rightPoint) {
            mergedList.add(rightList.get(rightPoint));
            rightPoint += 1;
        }

        return mergedList;
    }
    
    public ArrayList<Integer> mergeSplitFunc(ArrayList<Integer> dataList) {
        if (dataList.size() <= 1) {
            return dataList;
        }
        int medium = dataList.size() / 2;  

        ArrayList<Integer> leftArr = new ArrayList<Integer>();
        ArrayList<Integer> rightArr = new ArrayList<Integer>();

        leftArr = this.mergeSplitFunc(new ArrayList<Integer>(dataList.subList(0, medium))); 
        rightArr = this.mergeSplitFunc(new ArrayList<Integer>(dataList.subList(medium, dataList.size()))); 

        return this.mergeFunc(leftArr, rightArr);
    }
    
}

 시간 복잡도 O(nlogn)

 

퀵 정렬 (Quick Sort)

 - 기준점(pivot)을 정해서, 기준점 보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 함수를 작성

 - 각 왼쪽,오른쪽은 재귀용법을 사용해서 다시 동일 함수를 호출하여 위 작업을 반복함

 - 함수는 왼쪽 + 기준점 + 오른쪽을 리턴

 

퀵정렬 예시

 

import java.util.ArrayList;
import java.util.Arrays;

public class QuickSort {

    // 정렬이 안된 파라미터 dataList를 정렬된 dataList로 반환
    public ArrayList<Integer> sort(ArrayList<Integer> dataList) {
        if (dataList.size() <= 1) {
            return dataList;
        }
        int pivot = dataList.get(0);
        
        ArrayList<Integer> leftArr = new ArrayList<Integer>();
        ArrayList<Integer> rightArr = new ArrayList<Integer>();        
        
        for (int index = 1; index < dataList.size(); index++) {
            if (dataList.get(index) > pivot) {
                rightArr.add(dataList.get(index));
            } else {
                leftArr.add(dataList.get(index));
            }
        }
        
        ArrayList<Integer> mergedArr = new ArrayList<Integer>();
        
        mergedArr.addAll(this.sort(leftArr));
        mergedArr.addAll(Arrays.asList(pivot));
        mergedArr.addAll(this.sort(rightArr));
        // left + pivot + right;
        return mergedArr;        
    }
}

시간 복잡도 O(nlogn)

 - pivot이 제일 마지막에 있을 최악의 경우 O(n^2)

 

11일차 인증

 

 

 

 

 

 

 

 

 

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.
https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]