[알고리즘] 단순 정렬(N²) : 버블(Bubble Sort), 선택(Selection Sort), 삽입(Insertion Sort) 과 안정/불안정 정렬

 

0. 정렬과 역순 쌍 

0-1. 정렬 (Sorting)

• 배열의 원소들을 특정 기준(키 값) 에 따라 순서 있게 나열하는 과정
  • 오름차순 정렬 : 모든 i < j에 대해 A[i] ≤ A[j]

 

0-2. 역순 쌍 (Inversion)

• 조건 : i < j 이면서 A[i] > A[j]
• 의미 : 배열이 정렬된 상태의 배열과 비교하여 얼마나 어긋나 있는지를 나타내는 척도
• 특징
  • 정렬된 배열 → 역순 쌍 개수 = 0
  • 완전 역순 배열 → 최대치 = N(N-1)/2
  • 부분 정렬 배열 → 그 사이 값

 

0-2-1. 역순 쌍 예시

(앞 원소 > 뒤 원소 조건일 때)

• [ 1, 2, 3 ] 
  • 역순 없음 -> 0개 
• [ 2, 1, 3 ]
  • (2,1) -> 역순 1개
  • 즉, 역순 쌍 = 1개 
• [ 3, 1, 2 ]
  • (3,1) (3,2) -> 역순 2개
  • 즉, 역순 쌍 = 2개
• [ 4, 3, 2, 1 ]
  • (4,3) (4,2) (4,1) (3,2) (3,1) (2,1) -> 역순 6개 
  • 완전 뒤집힌 배열이므로 역순 쌍 = 최대치 

 

0-3. 정렬과 역순 쌍의 관계

• 정렬된 배열 : 역순 쌍 개수 = 0
• 완전 역순 배열 : 역순 쌍 개수 = N(N-1) / 2 (최대치)
• 부분적으로 정렬된 배열 : 역순 쌍 개수 = 그 사이 값 

 

 

1. 버블 정렬 (Bubble Sort)

인접한 두 원소 비교 → swap 반복, 뒤쪽부터 정렬 완료

2번째 루프에서 한번도 swap이 일어나지 않으면 완전 정렬 되었다는 의미이므로 종료. 

• 최적화: swap이 없으면 조기 종료 가능
• 시간복잡도:
  • 최선: Ω(N) (이미 정렬된 경우, 1패스 후 종료)
  • 평균/최악: Θ(N²), O(N²)
• 특징: 구현은 쉽지만 비효율적, 안정 정렬

 

 

2. 선택 정렬 (Selection Sort)

매 패스마다 최솟값(또는 최댓값) 찾아 맨 앞으로 이동 ( 최소 또는 최대값 Swap하는 방식 )

• 최적화 불가: 항상 끝까지 비교 필요
• 시간복잡도:
  • 최선/평균/최악: Ω(N²), Θ(N²), O(N²)
• 특징: 스왑은 적지만 비교는 항상 많음, 불안정 정렬

 

 

3. 삽입 정렬 (Insertion Sort)

정렬된 구간에 새로운 원소를 삽입

( 삽입 위치를 찾는 과정에서 앞 원소들을 뒤로 이동(shift) )

• 최적화: 이미 정렬된 부분이 많을수록 효율적
• 시간복잡도:
  • 최선: Ω(N) (이미 정렬된 경우, 이동 없음)
  • 평균/최악: Θ(N²), O(N²)
• 특징: 작은 데이터·부분 정렬된 배열에 효율적, 안정 정렬

 

 

4. 안정 정렬과 불안정 정렬 

정렬 알고리즘을 비교할 때 "안정성(stability)" 은 중요한 기준이다.

 

5-1. 안정 정렬

정렬 후에도 같은 값의 원소들이 원래의 상대적 순서를 유지하는 정렬 방식

즉, 값이 같으면 정렬하기 전의 순서가 정렬 후에도 그대로 보존됨.

 

• 초기 배열: [(국어, 90), (영어, 80), (수학, 90)]
  • 점수 기준으로 오름차순 정렬한다고 하면
• 안정 정렬 결과: [(영어, 80), (국어, 90), (수학, 90)]
  • 90점짜리 중에서는 "국어"가 "수학"보다 앞에 있었으므로 순서가 그대로 유지됨.

 

5-2. 불안정 정렬

정렬 과정에서 같은 값의 원소들 사이의 상대적 순서가 바뀔 수 있음.

• 초기 배열: [(국어, 90), (영어, 80), (수학, 90)]
• 불안정 정렬 결과 (가능한 경우): [(영어, 80), (수학, 90), (국어, 90)]
  • 90점끼리 순서가 뒤바뀜.

 

5. 시간복잡도 및 특징 비교

 

Big-O (빅-오 표기, 상한 Upper Bound):        “최대 이 정도까지 걸릴 수 있다”

Ω        (빅-오메가 표기, 하한 Lower Bound): “아무리 빨라도 이 정도는 걸린다”

Θ        (세타 표기, Tight Bound):                   즉, 최악과 최선이 같은 차수일 때 전체 평균 성능을 표현

알고리즘	최선 (Ω)	평균 (Θ)	최악 (O)	특징
버블 정렬	Ω(N) (이미 정렬된 경우, 교환 없음)	Θ(N²)	O(N²)	스왑 횟수 많음, 안정 정렬
삽입 정렬	Ω(N) (이미 정렬된 경우, 이동 없음)	Θ(N²)	O(N²)	작은 데이터&거의 정렬된 경우 빠름, 안정 정렬
선택 정렬	Ω(N²) (이미 정렬돼 있어도 최소값 찾으려 전부 비교)	Θ(N²)	O(N²)	스왑은 적지만 비교는 항상 많음, 불안정 정렬

 

 

 

6. 예시 : 부분 정렬된 데이터

[1, 2, 3, 7, 5, 6, 8] 

→ 이미 대부분 정렬되어 있고, 중간에 [7, 5, 6] 만 어긋나 있는 상태

 

6-1. 역순 쌍 찾기

역순 쌍 = (7,5), (7,6)  총 개수 2개

 

6-2. 버블 정렬 동작

• 1 패스
  • 1–2 OK
  • 2–3 OK
  • 3–7 OK
  • 7–5 → swap → [1, 2, 3, 5, 7, 6, 8]
  • 7–6 → swap → [1, 2, 3, 5, 6, 7, 8]
  • 7–8 OK
  • 비교 6회, 교환 2회 → 배열 정렬 완료
• 2 패스
  • 비교 5회, 교환 없음 → 종료
• 총 비교 11회 / 교환 2회

swap이 발생하지 않는 조기종료 까지 각 패스에서 비교와 Swap은 정렬되어 있어도 계속 진행된다.

swap이 없어도 불필요한 비교는 계속됨..!

 

6-3. 삽입 정렬 동작

• key = 5 
  • 7 > 5 → 7을 뒤로 이동
  • [1, 2, 3, 5, 7, 6, 8]
• key = 6
  • 7 > 6 → 7을 뒤로 이동
  • [1, 2, 3, 5, 6, 7, 8]

• 총 비교 약 8회 / 이동 2회

정렬되어 있는 구간에서 뒤쪽 부터 삽입할 위치를 찾는다.

이미 정렬된 구간은 뒤쪽 과 비교만 할 뿐 이동이 없다.

 

따라서 이미 정렬된 부분이 많을수록 삽입 정렬이 유리하다!