Chapter 06-1. 정렬 알고리즘_정렬 알고리즘이란

정렬(sorting)이란

이름, 학번, 키 등 핵심 항목(key)의 대소관계에 따라 데이터 집합을 일정한 순서로 나열하는 작업

작은 데이터를 앞쪽에 놓으면 오름차순(ascending order) 정렬, 반대로 놓으면 내림차순(descending order) 정렬

 

정렬 알고리즘의 안정성

정렬 알고리즘은 안정된(stable) 알고리즘과 그렇지 않은 알고리즘으로 나눌 수 있음

안정된 정렬이란 키값이 같은 요소의 순서가 정렬 전후에도 유지되는 것을 말함(점수순으로 정렬하되, 점수가 같으면 학번순으로 정렬하는 것과 같이)

안정되지 않은 알고리즘은 점수가 같을 때 반드시 학번 순서대로 정렬되지 않음

 

내부 정렬과 외부 정렬

• 내부 정렬(internal sorting): 정렬할 모든 데이터를 하나의 배열에 저장할 수 있을 때 사용
• 외부 정렬(external sorting): 정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없을 때에 사용 → 외부 정렬은 내부 정렬을 응용한 것으로, 구현하려면 작업을 위한 별도의 파일 등이 필요하고 알고리즘도 복잡함

 

정렬 알고리즘의 핵심 요소

교환, 선택, 삽입 → 대부분의 정렬 알고리즘은 이 3가지 요소를 응용함