데일리썽

1. 병합 정렬 (merge sort)

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

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

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

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

2. 구현

import lombok.extern.slf4j.Slf4j;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

@Slf4j
public class MergeSort {
    public static void split(List<Integer> dataList) {
        int medium = (int)(dataList.size() / 2);
        List<Integer> leftList = dataList.subList(0, medium);
        List<Integer> rightList = dataList.subList(medium, dataList.size());
        log.error("________________ = {}", medium);
        log.error("________________ = {}", leftList);
        log.error("________________ = {}", rightList);
    }

    public static List<Integer> mergeSplit(List<Integer> dataList) {
        if (dataList.size() <= 1) {
            return dataList;
        }

        int medium = (int)(dataList.size() / 2);
        List<Integer> leftList = mergeSplit(dataList.subList(0, medium));
        List<Integer> rightList = mergeSplit(dataList.subList(medium, dataList.size()));

        return merge(leftList, rightList);
    }
    public static List<Integer> merge(List<Integer> leftList, List<Integer> rightList) {
        int leftIndex = 0;
        int rightIndex = 0;

        List<Integer> mergedList = new ArrayList<>();

        // leftList, rightList 남아 있을 때
        while (leftList.size() > leftIndex && rightList.size() > rightIndex) {
            if (leftList.get(leftIndex) > rightList.get(rightIndex)) {
                mergedList.add(rightList.get(rightIndex));
                rightIndex++;
            } else {
                mergedList.add(leftList.get(leftIndex));
                leftIndex++;
            }
        }

        // leftList만 남아 있을 때
        while (leftList.size() > leftIndex) {
            mergedList.add(leftList.get(leftIndex));
            leftIndex++;
        }

        // rightList만 남아 있을 때
        while (rightList.size() > rightIndex) {
            mergedList.add(rightList.get(rightIndex));
            rightIndex++;
        }


        return mergedList;
    }

    public static void main(String[] args) throws Exception {
        Random rand = new Random();
        List<Integer> dataList = new ArrayList<>();
        for (int i = 0; i < 11; i++) {
            dataList.add(rand.nextInt(11));
        }

        log.error("________________ = {}", dataList);

        dataList = mergeSplit(dataList);

        log.error("________________ = {}", dataList);
    }
}

3. 분석

시간복잡도는 O(nlogn)

1. 퀵정렬 (quick sort)

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

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

함수는 왼쪽 + 기준점(pivot) + 오른쪽을 리턴함

2. 구현

import lombok.extern.slf4j.Slf4j;

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

@Slf4j
public class QuickSort {

    public static List<Integer> quickSort(List<Integer> dataList) {
        if (dataList.size() <= 1) {
            return dataList;
        }

        List<Integer> leftList = new ArrayList<>();
        List<Integer> rightList = new ArrayList<>();
        List<Integer> pivotList = new ArrayList<>();

        Integer pivot = dataList.get(0);

        for (int i = 0; i < dataList.size(); i++) {
            if (pivot > dataList.get(i)) {
                leftList.add(dataList.get(i));
            } else if (pivot < dataList.get(i)) {
                rightList.add(dataList.get(i));
            } else {
                pivotList.add(dataList.get(i));
            }
        }
        return Stream.of(quickSort(leftList), pivotList, quickSort(rightList)).flatMap(Collection::stream).collect(Collectors.toList());
    }

    public static void main(String[] args) throws Exception {
        Random rand = new Random();
        List<Integer> dataList = new ArrayList<>();
        for (int i = 0; i < 11; i++) {
            dataList.add(rand.nextInt(11));
        }

        log.error("________________ = {}", dataList);


        dataList = quickSort(dataList);

        log.error("________________ = {}", dataList);


    }
}

3. 분석

병합정렬과 유사

시간복잡도는 O(nlogn)

최악의 경우(pivot이 가장 크거나 가장 작으면 모든 데이터를 비교해야함) O(n^2)

1. 선택 정렬 (selection sort)

아래 순서를 반복하며 정렬하는 알고리즘

• 주어진 데이터 중 최소값을 찾음
• 해당 최소값을 데이터 맨 앞에 위치한 값과 교체함
• 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함

import java.util.*;

public class SelectionSort {
    public static void selectionSort() {
        int[] arr = new int[5];
        int size = arr.length;

        Scanner sc = new Scanner(System.in);

        for (int i = 0; i < 5; i++) {
            arr[i] = sc.nextInt();
        }

        System.out.println("정렬 전 : " + arr);

        for (int i = 0; i < size - 1; i++) {
       	    int minIndex = i;
       	    for (int j = i + 1; j < size; j++) {
                if (arr[minIndex] > arr[j]) {
                    minIndex = j;
                }
            }
            
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }

        System.out.println("정렬 후 : " + arr);
    }
}

2. 알고리즘 분석

반복문이 두개 : O(n^2)

1. 삽입 정렬 (insertion sort)

삽입 정렬은 두 번쨰 인덱스부터 시작

해당 인덱스(key 값) 앞에 있는 데이터부터 비교해서 key 값이 더 작으면 데이터 값을 뒤 인덱스로 복사

이용 Key 값이 더 큰 데이터를 만날떄까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동

• [5, 3]
  -> [3, 5]
• [5, 3, 2]
  -> [3, 5, 2]
  -> [3, 2, 5] -> [2, 3, 5]
• [5, 3, 2, 4]
  -> [3, 5, 2, 4]
  -> [3, 2, 5, 4] -> [2, 3, 5, 4]
  -> [2, 3, 4, 5] -> [2, 3, 4, 5]

import java.util.*;

public class InsertionSort {
    public static void insertionSort() {
    	int[] arr = new int[5];
        int size = arr.length;

        Scanner sc = new Scanner(System.in);

        for (int i = 0; i < 5; i++) {
            arr[i] = sc.nextInt();
        }

        System.out.println("정렬 전 : " + arr);

        for (int i = 0; i < size - 1; i++) {
            for (int j = i + 1; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                } else {
                    break;
                }
            }
        }

        System.out.println("정렬 후 : " + arr);
	}
}

2. 알고리즘 분석

반복문이 두개 : O(n^2)

완전 정렬이 되어 있는 경우 : O(n)

1. 정렬 (sorting) 이란?

정렬 (sorting) : 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것

정렬은 프로그램 작성시 빈번하게 필요로 함

2. 버블 정렬 (bubble sort)

두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면 자리를 바꾸는 정렬 알고리즘

• [5, 2] -> [2, 5]
• [5, 4, 2] -> [4, 5, 2] -> [4, 2, 5]
  -> [2, 4, 5]
• [5, 2, 3, 1] -> [2, 5, 3, 1] -> [2, 3, 5, 1] -> [2, 3, 1, 5]
  -> [2, 3, 1, 5] -> [2, 1, 3, 5]
  -> [1, 2, 3, 5]

import java.util.*;

public class BubbleSort {
    public static void bubbleSort() {
        int[] arr = new int[5];
        int size = arr.length;

        Scanner sc = new Scanner(System.in);

        for (int i = 0; i < 5; i++) {
            arr[i] = sc.nextInt();
        }

        System.out.println("정렬 전 : " + arr);

        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }

        System.out.println("정렬 후 : " + arr);
    }
}

3. 알고리즘 분석

반복문이 두개 : O(n^2)

완전 정렬이 되어 있는 경우 : O(n)