[알고리즘] 정렬 (Sorting)

📍정의

정렬 : 특정한 기준에 맞게 순서대로 나열하는 방법

 

 

📍주요 정렬 알고리즘 ( 로직 & 예시 코드 )

 

1. 버블 정렬

 

⚙️ 로직

1. 인접한 두 요소를 비교하여 크기 순서가 잘못되어 있을 경우, 위치를 바꾼다
2. 한 번의 패스가 끝나면 가장 큰 값이 마지막에 위치하여, 남은 요소들에 대해 반복한다.

• 시간 복잡도 : O(n^2)
• 단순, 비효율적 → 작은 데이터셋에 적합하다.

 

📄 유형 이해 코드

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // 위치 바꾸기
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

 

 

2. 선택 정렬

 

⚙️ 로직

1. 리스트에서 가장 큰/작은 요소를 찾아 첫 번째 요소와 교환한다.
2. 이후, 그 다음 요소부터 다시 리스트에서 가장 큰/작은 값을 찾아 다음 요소와 교환한다.
3. 위 과정을 반복하며 정렬 

• 시간 복잡도 : O(n^2)
• 버블 정렬보다 비교 횟수는 적지만, 효율성 ↓
• 제자리 정렬으로, 추가적인 메모리 사용이 적다.

📄 유형 이해 코드

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // 위치 바꾸기
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

 

 

3. 삽입 정렬

 

⚙️ 로직

1. 리스트의 첫 번째 요소는 이미 정렬된 것으로 간주하고 두 번째 요소부터 정렬을 시작한다.
2. 두 번째 요소를 정렬된 부분에 삽입할 위치를 찾아 배치한다
3. 위 과정을 반복하여 정렬된 부분을 확장한다. 

• 시간 복잡도  : O(n^2)
• 작은 데이터셋, 대부분 정렬된 리스트에 적합하다. 

📄 유형 이해 코드

public class InsertionSort {
    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;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }
}

 

 

4. 병합 정렬 

 

⚙️ 로직

1. 리스트를 반으로 나누어 두 개의 하위 리스트로 분할
2. 각 하위 리스트를 재귀적으로 다시 분할한 뒤, 정렬하여 병합
3. 병합 과정에서 두 리스트의 첫 요소를 비교해가며 작은 값부터 차례대로 병합한다.

• 분할정복 기법을 사용하여 리스트 분할
• 시간 복잡도 : O(n log n)
• 안정 정렬로, 데이터의 크기에 상관없이 일정한 성능을 보인다.

📄 유형 이해 코드

public class MergeSort {
	// 배열을 분할하고 병합하는 메서드
    // left : 왼쪽 경계, mid : 배열의 중간점, right : 오른쪽 경계
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;

            // 두 개의 하위 리스트에 대해 재귀적으로 mergeSort를 호출하여 정렬
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);

            // 정렬 후, merge메서드를 이용하여 두 부분 병합
            merge(arr, left, mid, right);
        }
    }

	// 두 개의 정렬된 하위 배열을 하나의 정렬된 배열로 병합하는 작업
    public static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
		
        // 두 개의 배열을 만들어 왼쪽과 오른쪽 부분 배열 저장
        int[] L = new int[n1];
        int[] R = new int[n2];
		
        for (int i = 0; i < n1; i++)
            L[i] = arr[left + i];
        for (int j = 0; j < n2; j++)
            R[j] = arr[mid + 1 + j];
		
        int i = 0, j = 0;
        int k = left;
        // L[i]와 R[i]를 비교하여 더 작은 값을 arr[k]에 저장
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }
		
        // 어느 한 쪽 배열이 모두 처리되면, 나머지 배열에 남아있는 값들을 그대로 arr에 복사한다.
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }
}

 

 

5. 퀵 정렬

 

⚙️ 로직

1. 리스트에서 하나의 피벗(pivot)을 선택
2. 피벗보다 작은 값들을 피벗의 왼쪽, 큰 요소들을 오른쪽으로 위치 시킨다
3. 위 과정을 재귀적으로 반복 

• 분할 정복 기법 사용
• 시간 복잡도 : O(n^2)
• 최악의 경우 시간 복잡도는 높지만, 이를 위한 여러 최적화 기법이 존재하여 시간을 단축시킬 수 있다. 

📄 유형 이해 코드

public class QuickSort {
	// 배열의 부분들을 재귀적으로 정렬하는 메서드
    // low : 배열의 시작 인덱스(왼쪽 경계), high : 배열의 끝 인덱스(오른쪽 경계)
    public static void quickSort(int[] arr, int low, int high) {
    	// low와 high가 만나지 않은 동안 배열을 피벗 기준으로 분할
        if (low < high) {
            int pi = partition(arr, low, high);

            // 피벗을 기준으로 왼쪽 부분 배열과 오른쪽 부분 배열에 대해 각각 재귀적으로 quickSort를 호출하여 정렬
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }
    
	// 피벗을 기준으로 배열을 두 부분으로 나누고, 그 인덱스를 반환하는 메서드
    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = (low - 1);
        // arr[j]와 피벗을 비교하여 arr[j]가 피벗보다 작으면, i를 증가시키고 arr[i]와 arr[j]를 교환한다.
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                // Swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        // arr[i + 1]와 피벗(arr[high])을 교환하여 피벗을 올바른 위치에 놓는다
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }
}

 

 

📍정렬 알고리즘 선택 기준

: 문제의 특성에 맞는 최적의 방법을 선택해야한다.

• 데이터의 크기
• 데이터 구조 및 상태 : 정렬 정도 / 정렬 구조 등
• 공간 효율성 : 추가 메모리의 크기
• 안정성 : 중복된 값의 순서 유지가 중요한 경우
• 속도