정렬 알고리즘 기초

정렬 알고리즘 기초

정렬

1. 내부 정렬:
   • 주기억장치에 데이터를 저장하고 정렬하는 방식
   • 예시: 배열, 리스트 정렬
2. 외부 정렬:
   • 주기억장치와 외부기억장치에 걸쳐 데이터를 저장하고 정렬하는 방식
   • 예시: 대용량 파일 정렬

정렬 알고리즘 기본 개념

1. 상황에 따라 적절한 정렬 방식 채택이 기본
   1) 시간 복잡도
   데이터를 정렬하는 데 걸리는 시간
   2) 공간 복잡도
   정렬을 수행하기 위한 추가 메모리 사용량
   3) 안정성
   동일한 값이 있을 때 원래의 순서가 유지되는지 여부
   4) 성능
   특정 조건(예: 정렬된 상태)이 주어졌을 때 성능

2. 정렬 시 중요한 요소:
   1) 자료의 개수
   - 작은 데이터: 단순한 정렬 알고리즘(삽입 정렬, 선택 정렬)도 가능.
   - 큰 데이터: 효율적인 정렬 알고리즘(퀵 정렬, 병합 정렬) 필요.

   2) 기준치의 개수
   - 단일 기준: 한 가지 기준으로 정렬.
   - 다중 기준: 여러 기준으로 정렬할 때 안정적인 알고리즘 필요.

   3) 정렬된 정도
   - 거의 정렬된 데이터: 삽입 정렬이 효율적.
   - 무작위 데이터: 효율적인 알고리즘(퀵 정렬, 병합 정렬) 필요.

3. 안정성:
   동일한 값의 상대적 위치가 변하지 않는 특성
   버블 정렬 (안정적)
   버블 정렬을 사용하면, (3, b)와 (3, c)의 순서가 변하지 않고 그대로 유지됩니다.
   - 정렬 전: (5, a), (3, b), (3, c), (4, d), (5, e)
   - 정렬 후: (3, b), (3, c), (4, d), (5, a), (5, e)
   퀵 정렬 (불안정): 퀵 정렬을 사용하면, (3, b)와 (3, c)의 순서가 변할 수 있습니다.
   - 정렬 전: (5, a), (3, b), (3, c), (4, d), (5, e)
   - 정렬 후: (3, c), (3, b), (4, d), (5, a),