[ 정렬 ]

1. 정렬(Sort)의 뜻

[ 국어사전 ]
(1) 가지런하게 줄지어 늘어섬. 또는 그렇게 늘어서게 함.
(2) 데이터를 특정한 조건에 따라 일정한 순서가 되도록 다시 배열하는 일

[ 교재 ]
이름, 학번, 키 등 핵심 항목(key)의 대소 관계에 따라 데이터 집합을 일정한 순서로 줄지어 늘어서도록 바꾸는 작업.

 

---

2. 정렬의 분류

 ▶ 실행 방법에 따른 분류

• 비교식 정렬(Comparative Sort) : 키 값들을 두 개씩 비교하며 교환하는 방식의 정렬 방법.
• 분산식 정렬(Distribute Sort) : 키 값들을 여러 개의 부분 집합으로 분해, 각 부분 집합을 정렬함으로써 전체를 정렬하는 방식으로 실행하는 방법.

 ▶ 정렬 장소에 따른 분류

• 내부 정렬(Internal Sort) : 정렬할 모든 데이터를 하나의 메모리(배열 등)에 저장할 수 있는 경우에 사용(모든 데이터가 주기억 장치 안에 있다고 가정)
• 외부 정렬(External Sort) : 정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없는 경우에 사용(데이터가 테이프나 디스크에 저장되어 있다고 가정)

    ex) 30장의 카드를 한 줄로 늘어놓을 수 있는 책상에서 트럼프 카드를 정렬한다고 가정.

         카드가 30장 이하라면, 모든 카드를 책상에 늘어놓고 한 번에 훑어보면서 작업 가능

         카드가 500장이라면, 책상에 모두 늘어놓을 수 없기 때문에 책상을 따로 마련해야함.

 

---

3. 정렬의 종류

[ 내부 정렬 ]

• 선택 정렬(selection sort)
• 삽입 정렬(insertion sort)
• 버블 정렬(bubble sort)
• 셸 정렬(shell sort)
• 퀵 정렬(quick sort)
• 병합 정렬(merge sort)
• 힙  정렬(heap sort)
• 도수 정렬(counting sort)
• 기수 정렬(radix sort)

• 버블 정렬(bubble sort)

 

[ 외부 정렬의 종류 ]

: 기본적으로 병합 정렬(2-way 병합, n-way 병합)

• 밸런스드 병합 정렬(balanced merge sort)
• 다단계 병합 정렬(polyphase merge sort)
• 캐스케이드 병합 정렬(cascade merge sort)
• 오실레이팅 병합 정렬(oscillating merge sort)

---

이 외에도 다양한 정렬이 있음.

 

[참고]
1. Do it! 자료구조와 함꼐 배우는 알고리즘 입문 자바편
2. PRACTICAL DATA STRUCTURE 데이터 구조
3. 블로그