정렬 알고리즘

1. 정렬 알고리즘

• 목록 안에 저장된 요소들을 특정한 순서대로 재배치하는 알고리즘
• 정렬을 하는 이유
  - 좀 더 효율적인 알고리즘을 사용하기 위해
  • 사람이 읽기 편하도록 등등
• 입력 데이터는 일반적으로 배열 같은 데이터 구조에 저장
  - 아무 위치로 임의 접근을 허용
  • 연결 리스트를 사용하면 처음 혹은 끝부터 차례대로 훑어야 함
• 흔히 사용하는 순서: 숫자 순서, 사전 순서
• 정렬 방향: 오름차순, 내림차순
• 다양한 정렬 알고리즘이 있음
  - 시가나 복잡도 차이
  • 메모리 사용량 차이
  • 안정성(stability) 차이
  • 직렬 vs 병렬 차이

2. 정렬 알고리듬의 안정성

• 안전성(safety)이 아님!
• 똑같은 키(key)를 가진 데이터들의 순서가 바뀌지 않느냐 여부
  

2.1 안정성을 잘 모르는 이유

• 같은 키를 가진 데이터의 순서가 바뀌어도 문제가 아닌경우가 보통
• 그래서 잘 모르고 생각도 안 하는 부분
• 심지어는 이렇게 잘못 생각하기도 함
  - '모든 정렬 알고리즘은 같은 키를 가진 데이터의 순서를 안 바꾼다'
• 이 때문에 버그가 나도 못고치는 경우가 있음
  - 진실
  - 어떤 정렬 알고리즘은 안정성을 보장
  - 어떤 정렬 알고리즘은 보장 안 함

2.2 안정성이 문제가 되는 경우 1

1. 정렬의 기준이 되는 정렬 키(sort key)와 실제 데이터가 다름
2. 구조체/클래스의 일부 멤버만 정렬 키로 사용