[알고리즘] 제자리 정렬 In-Place Sorting

출처

ChatGPT

---

제자리 정렬이란 추가적인 메모리 공간을 거의 사용하지 않고(상수 공간만 사용) 원래 주어진 배열 또는 리스트 내에서 요소들을 정렬하는 알고리즘을 말한다. 즉, 입력 자료를 위한 추가적인 큰 메모리 공간을 할당하지 않고, 데이터 자체를 교환하거나 이동시키면서 정렬을 수행한다.

예시

버블 정렬(Bubble Sort), 선택 정렬(Selection Sort), 삽입 정렬(Insertion Sort) 등은 제자리 정렬 알고리즘이다.

비제자리 정렬 Out-Of-Place Sort

병합 정렬(Merge Sort)과 같은 알고리즘은 비제자리 정렬로 분류된다. 병합 정렬은 정렬을 위해 추가적인 배열 공간이 필요하다.

 

제자리 정렬의 특징

추가 메모리 사용이 적음

일반적으로 상수 공간(O(1))만 추가로 사용한다.

데이터 자체를 교환

원래 배열이나 리스트 내에서 데이터를 정렬하므로 입력 배열 외에 큰 메모리 할당이 필요하지 않다.

 

제자리 정렬의 장점

메모리 효율성

제자리 정렬은 큰 데이터를 다룰 때 메모리 사용량이 적어 효율적이다.

 

예시 : 선택 정렬 Selection Sort

선택 정렬은 배열 내에서 가장 작은(또는 가장 큰) 요소를 찾아 교환하면서 제자리에서 정렬을 수행한다.

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[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }
}