[자료구조] 12장 Sort

1. 정렬

: 데이터를크기순으로 오름, 내림 차순으로 나열하는 것

  - 정렬의 대상: 레코드

  - 종류

• 단순하지만 비효율적인 방법: 삽입,선택, 버블 정렬
• 복잡하지만 효율적인 방법: 퀵, 힙, 합병, 기수 정렬 

 

2. 선택 정렬

: 가장 작은 값과 정렬 안 된 값들 중 가장 앞에 있는 값을 교환

  - 시간 복잡도: O(n^2)

  - 특징: 매우 간단. 비효율적. 안정성 만족 안함.

 

3. 삽입 정렬

정렬되어 있는 부분에 새로운 레코드를 올바른 위치에 삽입하는 과정

  - 시간 복잡도: O(n^2)

  - 특징: 많은 이동 필요. 안정됨. 대부분 정렬되어 있으면 효율적.

 

4. 버블 정렬

: 인접한 2개 레코드를 비교해 바꿈

  - 시간 복잡도: O(n^2)

  - 특징: 많은 이동 필요. 

 

5. 셸 정렬

: 삽입 정렬은 어느정도 정렬된 리스트에서 꽤 빠름. 그러나 많은 이동 발생..  

  - 시간 복잡도: 최악-O(n^2), 최선-O(nlogn)

  - 특징: 적은 위치 교환.

 

6. 병합 정렬

리스트를 두 부분으로 분할하고 각각을 정

  - 시간 복잡도: O(n*logn)

  - 특징: 효율적. 안정적. 초기 분산순서에영향 덜 받음 

 

7. 퀵 정렬

평균적으로 가장 빠른 정렬 방법

  - 시간 복잡도: 최선-O(nlogn), 최악-O(n^2) 

''

8. 계수 정렬용

데이터의 크기 범위가 제한되어 있고, 정수 범위로 표현할 수 있을 때 사

  - 시간 복잡도: O(n+k) 여기서 k는 최댓값

 

9. 기수 정렬

레코드를 비교하지 않고 정렬 수행.

  - 시간 복잡도: O(n)으로 O(nlogn)보다 좋을 수 있음.

  - 특징: 실수, 한자, 한글로 이뤄진 키는 정렬 못 함