알고리즘 유형4. 정렬 feat. 유레카

정렬

1. 선택 정렬

: 가장 작은 데이터를 찾아서 순차적으로 앞쪽에 쌓는다

선택 정렬의 특징

• 첫번째 요소부터 나머지 요소들 중 가장 작은 요소와 자리를 교환한다.
  이 과정에서 앞에서부터 자동으로 정렬되게 된다.

ex) 

1회 : 9-1-7-5 -> 1-9-7-5

2회 : 1-9-7-5 -> 1-5-7-9

// 선택 정렬 메소드
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        
        // 배열의 모든 요소를 순차적으로 탐색
        for (int i = 0; i < n - 1; i++) {
            // 가장 작은 요소의 인덱스를 찾음
            int minIdx = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }
            
            // 가장 작은 요소를 현재 위치로 교환
            int temp = arr[minIdx];
            arr[minIdx] = arr[i];
            arr[i] = temp;
        }
    }

선택 정렬의 시간 복잡도

• 최악의 경우: O(n^2) 
• 최선의 경우: O(n^2)
• 평균: O(n^2) just 최악

선택 정렬의 공간 복잡도

• O(1) (상수 공간 사용)

 

2. 삽입정렬

: 특정한 데이터를 적절한 위치에 넣는다

삽입 정렬의 특징

• 두번째요소부터 탐색 시작한다.
• 현재 정렬할 요소의 이전 요소들은 무조건 다 정렬되어 있다.

ex)

1회 : 9-1-7-5-2 -> 1-9-7-5-2

2회 : 1-9-7-5-2 -> 1-7-9-5-2

3회 : 1-7-9-5-2 -> 1-5-7-9-2

4회 : 1-5-7-9-2 -> 1-2-5-7-9

// 삽입정렬 메소드
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;

            // key보다 큰 요소들을 한 칸씩 오른쪽으로 이동
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }

            // key를 적절한 위치에 삽입
            arr[j + 1] = key;
        }
    }

 

삽입 정렬의 시간 복잡도

• 최악의 경우: O(n^2) (역순으로 정렬된 배열)
• 최선의 경우: O(n) (이미 정렬된 배열)
• 평균: O(n^2)

삽입 정렬의 공간 복잡도

• O(1) (상수 공간 사용)

 

3. 퀵정렬

 

4. 계수정렬

 

각 정렬별 정리

	선택 정렬	삽입 정렬	퀵 정렬	계수 정렬
최악	O(n^2)	O(n^2)
최선	O(n^2)	O(n)
평균	O(n^2)	O(n^2)
공간 복잡도	O(1)	O(1)

 

리니어 하거나 공간을 가진거에서 나누고 공간을 다시 합치는 구조

 

추가 문제 : 백준 1992

: 쿼드 트리(Quad Tree)를 이용하여 인접한 영역을 압축

https://www.acmicpc.net/problem/1992

 

[접근 방법]

이진 트리는 자식 노드를 2개씩 갖는 트리라면, 쿼드트리는 자식 노드가 4개인 트리이다. (8개는 옥트리)

 

이런식으로 2차원의 공간을 4개로 쪼개고, 각각 쪼개진 4개의 영역에 대해 하나의 영역으로 압축할 수 있으면 압축한다.

만약 압축하지 못한다면, 하나의 영역을 또 4개의 영역으로 쪼갤 수 있다.

package Sort_ch06;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class BaekJoon_1992 {
	static int[][] img;
	static StringBuilder sb = new StringBuilder();	// 출력값을 한번에 묶어서 출력
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		img = new int[N][N];
		
		for(int i = 0; i < N; i++) {
			String str = br.readLine();
			
			for(int j = 0; j < N; j++) {
				img[i][j] = str.charAt(j) - '0';
			}
		}
		
		QuadTree(0, 0, N);
		System.out.println(sb);
	}
	
	public static void QuadTree(int x, int y, int size) {
		
		// 압축이 가능할 경우 압축
		if(isPossible(x, y, size)) {
			sb.append(img[x][y]);
			return;
		}
		
		int newSize = size / 2;	// 압축이 불가능 할 경우 한 변의 길이를 반으로 나눈다.
		
		sb.append('(');	// 각 레벨(depth)에서 여는괄호로 시작해야한다. 
		
		QuadTree(x, y, newSize);						// 왼쪽 위
		QuadTree(x, y + newSize, newSize);				// 오른쪽 위
		QuadTree(x + newSize, y, newSize);				// 왼쪽 아래
		QuadTree(x + newSize, y + newSize, newSize);	// 오른쪽 아래
		
		sb.append(')');	// 해당 레벨이 끝나면 닫는괄호도 닫아준다.
	}
	
	// 압축이 가능한지 해당 공간을 체크해주는 함수
	static boolean isPossible(int x, int y, int size) {
		int value = img[x][y];
		
		for(int i = x; i < x + size; i++) {
			for(int j = y; j < y + size; j++) {
				if(value != img[i][j]) {
					return false;
				}
			}
		}
		return true;
	}
}