[알고리즘 이론] 정렬 Sort - 1. 기본 개념

정렬 Sort
1. 기본 개념
2. 비교 기반 알고리즘

   1) 선택 정렬
   2) 버블 정렬
   3) 삽입 정렬
   4) 셸 정렬

---

 

1. 기본 개념

1) “정렬(Sort)”이란?

• 주어진 데이터를 값의 크기 순서에 따라 재배치 하는 것
• 대표 : 오름차순(Ascending), 내림차순(Descending)

 

2) 정렬 구분

• 기준 : 정렬이 수행되는 시점에 데이터가 어디에 저장되어 있는가?

✅ 내부 정렬	컴퓨터 내에 있는 주기억 장치에 데이터가 있음
	전체 데이터 위치 : 주기억장치에 저장 → 정렬 수행

외부 정렬	주기억 장치 밖에 데이터가 있음 (주기억장치에 모든 데이터를 저장 할 수 없는 경우)
	전체 데이터 위치 : 보조 기억장치 → 필요한 일부 데이터만 반복적으로 주기억장치로 옮겨 → 정렬 수행

 

 

3) 내부 정렬의 정렬 방식

📍point - 몇 번 비교 했는가 vs 몇 번 이동했는가!

• 비교 기반 알고리즘
  • 어떤 값을 비교할 때, 직접 적으로 비교하는 방식 (1은 2보다 작다. 2는 1보다 크다.)
  • 성능 기준 : 키 값의 비교 횟수
  • 종류
    • 선택정렬, 버블 정렬, 삽입정렬, 셸 정렬 ← O(n²) : 가장 기본 성능
    • 퀵 정렬, 합병 정렬, 힙 정렬 ← O(nlogn)

시간복잡도

 

• 데이터 분포 기반 알고리즘
  • 데이터의 분포 정보를 활용하여 정렬 수행
  • 성능 기준 : 데이터의 이동 횟수
    • 정렬 전 데이터의 분포 정보가 중요함
  • 계수 정렬, 기수 정렬, 버킷 정렬 ← 제한 조건 부합 시 : O(n)
  •  

4) 안정적 정렬 (Stable Sort)

• 동일한 값을 갖는 데이터가 여러 개일 경우, 정렬 전의 상대적 위치가 정렬 후에도 그대로 유지되는 정렬

입력 데이터	[5, 1, 4, 3, 6, 2, 4]
정렬 데이터	[1, 2, 3, 4, 4, 5, 6]	안정 정렬
	[1, 2, 3, 4, 4, 5, 6]	불안정적 정렬

 

• 안정적 정렬 : 버블 정렬, 삽입 정렬
• 불안정적 정렬 : 선택 정렬, 셸 정렬
•  

5) 제자리 정렬(In-place Sort)

• 입력 배열 이외에 별로도 필요한 저장 공간이 상수개를 넘지 않는 정렬
  • 입력되는 데이터의 크기 n이 증가 하더라도, 저장공간이 추가되지 않음. 저장 공간은 고정.
  • 저장 공간이 추가되면? ‘제자리 정렬이 아니다.

 

[정렬별 특징]

•  

선택 정렬	버블 정렬	삽입 정렬	셸 정렬
O(n2)	O(n2)	O(n2)	O(n2)
제자리	제자리	제자리	제자리
불안정	안정적	안정적	불안정