정렬 이해하기

정렬 알고리즘 이해하기

1. 선택 정렬 (Selection Sort)

개념 설명

선택 정렬은 배열에서 가장 작은 값을 찾아 맨 앞의 값과 교환하는 과정을 반복하는 정렬 알고리즘입니다.

동작 원리:

배열에서 최솟값을 찾습니다.

최솟값을 맨 앞의 값과 교환합니다.

맨 앞을 제외한 나머지 배열에서 위 과정을 반복합니다.

시간 복잡도: O(n²)

공간 복잡도: O(1)

동작 흐름도

graph TD
    A["시작: [5, 3, 8, 4, 2]"] --> B["1회전: 최솟값 2 찾기"]
    B --> C["[2, 3, 8, 4, 5]"]
    C --> D["2회전: 최솟값 3 찾기"]
    D --> E["[2, 3, 8, 4, 5]"]
    E --> F["3회전: 최솟값 4 찾기"]
    F --> G["[2, 3, 4, 8, 5]"]
    G --> H["4회전: 최솟값 5 찾기"]
    H --> I["[2, 3, 4, 5, 8]"]
    I --> J["정렬 완료"]
Mermaid
복사

예시 코드

import java.util.Scanner;

// 선택정렬
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        
        // [1][3][2][5][4]
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n ; j++) {
                if( arr[i] > arr[j] ) {
                    // 교환패턴 (swap)
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        
        for (int i = 0; i < n ; i++) {
            System.out.println(arr[i]);
        }
    }
}
Java
복사

2. 버블 정렬 (Bubble Sort)

개념 설명

버블 정렬은 인접한 두 원소를 비교하여 큰 값을 뒤로 보내는 과정을 반복하는 정렬 알고리즘입니다. 마치 거품이 수면으로 올라오는 것처럼 큰 값이 배열의 끝으로 이동합니다.

동작 원리:

첫 번째 원소부터 인접한 원소끼리 비교합니다.

앞의 원소가 더 크면 두 원소를 교환합니다.

배열의 끝까지 이 과정을 반복하면 가장 큰 값이 맨 뒤로 이동합니다.

정렬된 부분을 제외하고 위 과정을 반복합니다.

시간 복잡도: O(n²)

공간 복잡도: O(1)

동작 흐름도

graph TD
    A["시작: [5, 3, 8, 4, 2]"] --> B["1회전: 인접 원소 비교"]
    B --> C["[3, 5, 4, 2, 8]"]
    C --> D["2회전: 인접 원소 비교"]
    D --> E["[3, 4, 2, 5, 8]"]
    E --> F["3회전: 인접 원소 비교"]
    F --> G["[3, 2, 4, 5, 8]"]
    G --> H["4회전: 인접 원소 비교"]
    H --> I["[2, 3, 4, 5, 8]"]
    I --> J["정렬 완료"]
Mermaid
복사

예시 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] arr = new int[10001];
        
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n-(i+1); j++) {
                if( arr[j] > arr[j+1] ) {
                    int temp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        
        for (int i = 0; i < n; i++) {
            System.out.println(arr[i]);
        }
    }
}
Java
복사

3. 삽입 정렬 (Insertion Sort)

개념 설명

삽입 정렬은 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누고, 정렬되지 않은 부분의 원소를 정렬된 부분의 적절한 위치에 삽입하는 정렬 알고리즘입니다.

동작 원리:

두 번째 원소부터 시작하여 그 앞의 원소들과 비교합니다.

현재 원소(key)보다 큰 원소들을 한 칸씩 뒤로 이동시킵니다.

적절한 위치를 찾으면 key를 삽입합니다.

배열의 끝까지 이 과정을 반복합니다.

시간 복잡도: O(n²) - 최선의 경우 O(n)

공간 복잡도: O(1)

동작 흐름도

graph TD
    A["시작: [5, 3, 8, 4, 2]"] --> B["key=3, 정렬된 부분: [5]"]
    B --> C["[3, 5, 8, 4, 2]"]
    C --> D["key=8, 정렬된 부분: [3, 5]"]
    D --> E["[3, 5, 8, 4, 2]"]
    E --> F["key=4, 정렬된 부분: [3, 5, 8]"]
    F --> G["[3, 4, 5, 8, 2]"]
    G --> H["key=2, 정렬된 부분: [3, 4, 5, 8]"]
    H --> I["[2, 3, 4, 5, 8]"]
    I --> J["정렬 완료"]
Mermaid
복사

예시 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        
        int i, j, key;
        for (i = 1; i < n; i++) {
            key = arr[i];
            for (j = i-1; j >= 0 && arr[j]>key ; j--) {
                arr[j+1] = arr[j];
            }
            arr[j+1] = key;
        }
        
        for (int k = 0; k < n; k++) {
            System.out.println(arr[k]);
        }
    }
}
Java
복사