[알고리즘] 정렬 알고리즘 1. 버블정렬, 선택정렬, 삽입정렬

 

정렬(Sorting)

---

정렬(Sorting)은 주어진 데이터 집합을 특정 기준(키 값)에 따라 순서 있게 재배치 하는 과정이다. 일반적으로 오름차순 정렬은 모든 인덱스 i, j에 대해 i< j이면 A[i] < A[j] 조건을 만족하는 상태를 의미한다. 즉, 배열의 앞에서부터 뒤까지 순서가 일관되게 증가(또는 감소)해야 정렬된 상태라고 볼 수 있다. 정렬 알고리즘은 어떤게 좋은 알고리즘이고 어떤게 비교적 덜 안좋은 알고리즘이라고 할 수 없다. 주어진 데이터에 따라 정렬 성능이 달라지기 때문에 정렬할 데이터와 정렬 목적에 따라서 상황에 맞게 알고리즘을 선택해야한다. 

 

정렬 알고리즘 선택 고려 사항

고려 요소	이유	예시
데이터의 크기 (n)	데이터의 개수가 작을수록 단순한 알고리즘(삽입/선택/버블)도 충분히 빠름. 데이터가 많을수록 O(n log n) 이상의 효율이 필요함	n=100 → 삽입정렬도 OK, n=1,000,000 → 퀵/힙/병합정렬
데이터의 정렬 정도	이미 거의 정렬된 데이터라면 삽입 정렬이 매우 빠름. 무작위거나 역순이면 퀵정렬이 느려질 수 있음	삽입 정렬은 "거의 정렬된" 데이터에 매우 효율적
메모리 사용량 제약	병합정렬은 추가 메모리가 필요하지만, 힙정렬은 제자리 정렬임	임베디드 환경 → 메모리 절약형 정렬 필요
안정성(Stable Sort)	같은 값을 가진 원소들의 원래 순서를 유지해야 하는지 여부	학생 (이름, 점수) 정렬 시 점수 같을 때 이름 순 유지 필요
비교 기반 여부	데이터가 숫자형일 경우 계수정렬, 기수정렬, 버킷정렬 등의 비비교 정렬이 더 빠를 수 있음 (O(n))	정수 키 정렬 시 카운팅 정렬 유리
병렬화 가능성	대규모 데이터나 GPU 환경에서는 병합정렬이나 퀵정렬 변형이 병렬화에 유리	대용량 데이터 병렬 정렬 시
데이터 접근 특성	랜덤 접근이 가능한지, 연속적인 메모리인지 등에 따라 적합한 알고리즘이 달라짐	연결 리스트 → 병합정렬, 배열 → 퀵/힙정렬

 

 

정렬 알고리즘 성능 판단 지표

성능 지표	설명	예시
시간 복잡도 (Time Complexity)	평균/최악/최선의 경우에 걸리는 비교 횟수나 연산 횟수	퀵정렬: 평균 O(n log n), 최악 O(n²)
공간 복잡도 (Space Complexity)	정렬 수행 중 추가로 필요한 메모리의 크기	힙정렬: O(1), 병합정렬: O(n)
안정성 (Stability)	같은 키 값을 가진 원소의 순서를 유지하는가	삽입/병합정렬: 안정적, 퀵/힙정렬: 불안정
제자리 정렬 여부 (In-place)	추가 메모리를 거의 사용하지 않고 원본 배열 내에서 정렬하는가	버블/삽입/선택/힙정렬: 제자리 정렬
적응성 (Adaptiveness)	데이터가 이미 정렬되어 있을 때 더 빠르게 작동하는가	삽입정렬: 매우 적응적
비교 횟수 / 교환 횟수	실제 수행 속도에 영향을 주는 세부 지표	버블정렬: 교환 많음, 힙정렬: 비교 많음

 

 

 

제자리 정렬 (In-place sort)

 

제자리 정렬(In-place sort)이란 추가적인 메모리 공간을 거의 사용하지 않고, 입력 배열 내부에서 이동(shift), 교환(swap)만으로 정렬을 수행하는 알고리즘을 의미한다.

제자리 정렬 알고리즘	버블정렬, 선택정렬, 삽입정렬, 퀵정렬, 힙정렬
제자리 정렬이 아닌 알고리즘	병합 정렬, 기수 정렬

 

 

안정 정렬(Stable sort)과 비안정 정렬(Unstable sort)

 

정렬할 데이터에 같은 키(key)값을 가진 원소들이 여러개 있을때, 정렬 후에도 원래의 순서가 유지되면 안정 정렬(satble sort), 순서가 깨질 수 있으면 비안정 정렬(unstable sort)이다. 

안정 정렬 알고리즘	버블정렬, 삽입정렬, 병합정렬, 기수정렬
비안정 정렬 알고리즘	선택정렬, 퀵정렬, 힙정렬

 

 

 

 

역순 쌍(Inversion pair)

---

역순 쌍(Inversion pair)은 정렬 알고리즘의 정렬 정도(disorder)를 측정할 때 자주 사용되는 개념으로, 앞에 있는 원소가 뒤에보다 큰 경우를 역순쌍이라고 부른다. 즉, 두 원소를 비교했을때 정렬이 되어있지 않다면 역순쌍이라고 한다. 예를 들어 배열 A에서 두 원소(A[i], A[j])가 i<j 이면서 A[i] > A[j]인 경우, 이 두 원소는 역순 쌍이다. 배열이 정렬되어 있다면 역순 쌍의 개수는 0개가 되며, 완전히 뒤집힌 배열이라면 역순 쌍이 많을 것이다. 이러한 역순 쌍의 개수는 배열이 정렬된 상태와 얼마나 어긋나 있는지를 나타내는 척도가 된다.

정렬된 배열의 역순 쌍 개수 = 0
완전 역순 배열의 역순 쌍 개수 = N(N-1)/2

 

예시 ) 

1. [1, 2, 3]
   • 모든 앞 원소 ≤ 뒤 원소
   • 역순 없음 → 0개
2. [2, 1, 3]
   • (2,1) → 앞이 크니까 역순
   • 역순 쌍 = 1
3. [3, 1, 2]
   • (3,1), (3,2) → 두 개 역순
   • (1,2)는 정상
   • 역순 쌍 = 2
4. [4, 3, 2, 1]
   • (4,3), (4,2), (4,1), (3,2), (3,1), (2,1)
   • 가능한 모든 쌍이 역순 → 6개
   • 완전 뒤집힌 배열이므로 역순 쌍 = 최대치

 

 

 

1. 버블 정렬 (Bubble Sort)

---

2중 루프를 돌며 앞 뒤 원소들을 차례대로 swap하며 최대값을 맨 뒤로 보내는 정렬 방식이다. swap하며 제일 뒤쪽부터 값이 정렬되기 때문에 정렬할 영역은 -1씩 줄어들며, 다음 루프에서 한번도 swap이 일어나지 않는다면 완전 정렬 되어있다는 의미로 정렬을 종료한다. 가장 큰 원소가 버블처럼 맨 끝으로 떠오른다는 의미에서 버블정렬이라는 이름이 붙여진 것이다.

 

function OptimizedBubbleSort(A):
    n ← length(A)

    for i from 0 to n-1:
        swapped ← false   // swap 플래그

        for j from 0 to n-i-2:
            if A[j] > A[j+1]:
                // swap
                temp ← A[j]
                A[j] ← A[j+1]
                A[j+1] ← temp

                swapped ← true

        // swap이 없었으면 정렬이 완료된것이므로 종료
        if swapped == false:
            break

    return A

• 인접한 두 원소를 비교하여 순서가 잘못되었으면 교환(swap)
• 한 번 반복할 때마다 가장 큰 원소가 맨 뒤로 이동
• 반복 횟수는 점점 줄어듦 (n-i-2)
• swap이 없었거나 루프를 모두 돌면 알고리즘 종료

 

최적	평균	최악	공간 복잡도	안정성	제자리정렬 여부
O(n)	O(n²)	O(n²)	O(1)	안정	O

 

 

 

2. 선택 정렬 (Selection Sort)

---

2중 루프를 돌며 배열에서 최소값을 찾아 맨 앞으로 보내는 정렬 방식이다. 제일 앞쪽부터 값이 정렬되기 때문에 정렬할 영역이 -1씩 줄어들며, 중간 종료 없이 항상 최소 또는 최대값을 찾기 위해 마지막 루프까지 돌고 정렬을 완료한다.

 

• 현재 위치 i에 올 최소값을 찾아서 교환
• 한 번 반복할 때마다 배열 앞쪽에 확정된 최소값 위치 확보
• 반복 횟수는 항상 0~n-1까지 고정

 

function SelectionSort(A):
    n ← length(A)

    for i from 0 to n-1:
        minIndex ← i   // i번째 위치를 현재 최소값으로 가정

        // i 이후 원소 중에서 최소값 탐색
        for j from i+1 to n-1:
            if A[j] < A[minIndex]:
                minIndex ← j

        // 최소값을 i번째 위치와 교환
        if minIndex ≠ i:
            temp ← A[i]
            A[i] ← A[minIndex]
            A[minIndex] ← temp

    return A

최적	평균	최악	공간 복잡도	안정성	제자리정렬 여부
O(n²)	O(n²)	O(n²)	O(1)	불안정	O

 

 

3. 삽입 정렬 (Insertion Sort)

---

삽입 정렬(Insertion Sort)는 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누고 정렬되지 않은 부분에서 하나씩 꺼내서 정렬된 부분의 적절한 위치에 삽입하는 정렬 방식이다. 삽입 정렬은 첫번째 원소는 이미 정렬된 것으로 보고 두번째 원소부터 정렬을 시작하며, 정렬된 부분인 첫번째 원소 구간과 비교해서 적절한 위치에 삽입하는 것이다. 원소마다 삽입할 위치를 순차적으로 찾아야하므로 시간복잡도는 O(N^2)이다.

 

• 현재 원소(key)를 왼쪽 정렬된 부분에 삽입
• 배열의 앞쪽이 항상 정렬된 상태로 유지됨
• 삽입 위치를 찾으면서 원소들을 한 칸씩 뒤로 이동
• 데이터가 거의 정렬된 경우 삽입 위치를 찾는 시간이 단축되어 빠름 

 

function InsertionSort(A):
    n ← length(A)

    for i from 1 to n-1:
        key ← A[i]          // 현재 삽입할 원소
        j ← i - 1           // 정렬된 구간 마지막 인덱스

        // key보다 큰 원소들을 한 칸씩 뒤로 이동
        while j ≥ 0 and A[j] > key:
            A[j+1] ← A[j]
            j ← j - 1

        // key를 적절한 위치에 삽입
        A[j+1] ← key

    return A

최적	평균	최악	공간 복잡도	안정성	제자리정렬 여부
O(n)	O(n²)	O(n²)	O(1)	안정	O