6-1장 정렬

1. 정렬 정의 하기 

 

정렬(sorting)

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

 - 키 값이 작은 데이터를 앞쪽에 놓으면 오름차순(ascending order)

 - 키 값이 큰 데이터를 앞쪽에 놓으면 내림차순(descending order)

 

정렬 알고리즘의 안정성 

 

 - 안정된(stable) 정렬

 -> 같은 값의 키를 가진 요소의 순서가 정렬 전후에도 유지 

 -> 중복된 값을 입력 순서와 동일하게 정렬

 -> 삽입 정렬, 병합 정렬, 버블 정렬

 

 - 불안정(unstable) 정렬

  -> 중복된 값을 입력순서와 동일하지 않게 정렬

  -> 퀵 정렬, 선택 정렬

 

정렬 알고리즘의 핵심 요소 

 

 - 교환, 선택, 삽입

 

내부 정렬과 외부 정렬

 

 - 내부(internal) 정렬 

 -> 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용

 

 - 외부(external) 정렬 

  -> 정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없는 경우에 사용