정렬 알고리즘

지난 글 : [알고리즘/Do it 알고리즘] - 8퀸 문제

 

정렬

정렬(sorting)은 이름, 학번, 키 등 핵심 항목(key)의 대소 관계에 따라 데이터 집합을 일정한 순서로 나열하는 작업이다. 이 알고리즘을 이용해 데이터를 정렬하면 검색을 더 쉽게 할 수 있다. 값이 작은 데이터를 앞쪽에 놓으면 오름차순(ascending order) 정렬, 값이 큰 데이터를 앞쪽에 놓으면 내림차순(descending order) 정렬이라 한다.

 

정렬 알고리즘의 안정성

앞으로 정렬 알고리즘 중 대표적인 8개의 알고리즘을 배울 것이다. 이때 정렬 알고리즘은 안정된(stable) 알고리즘과 그렇지 않은 알고리즘으로 나뉜다고 한다. 안정된 정렬이란 키값이 같은 요소의 순서가 정렬 전후에도 유지되는 것을 말한다. 안정되지 않은 알고리즘은 키값이 같을 때 어떤 조건으로 요소를 정렬할지 모른다.

 

내부 정렬과 외부 정렬

30장의 카드를 한 줄로 늘어놓을 수 있는 책상에 트럼프 카드를 정렬한다 하자. 만약 카드가 30장 이하라면 모든 카드를 책상에 늘어놓고 한 번에 훑어보며 작업할 수 있지만, 이를 초과하면 책상에 모든 카드를 늘어놓을 수 없기에 큰 책상을 따로 마련해야 한다. 정렬 알고리즘도 하나의 배열에서 작업할 수 있을 때에는 내부 정렬(internal sorting)을 사용하고, 하나의 배열에서 작업할 수 없을 때에는 외부 정렬(external sorting)을 사용한다.

내부 정렬 : 정렬할 모든 데이터를 하나의 배열에 저장할 수 있을 때 사용하는 알고리즘
외부 정렬 : 정렬할 데이터가 너무 많아 하나의 배열에 저장할 수 없을 때 사용하는 알고리즘

외부 정렬은 내부 정렬을 응용한 것으로, 외부 정렬을 구현하려면 작업을 위한 별도의 파일 등이 필요하고 알고리즘도 복잡하다 한다. 앞으로 배울 알고리즘은 모두 내부 정렬이다.

 

정렬 알고리즘의 핵심 요소

정렬 알고리즘의 핵심 요소는 교환, 선택, 삽입이다. 대부분의 정렬 알고리즘은 이 3가지 요소를 응용한 것이라 한다.

 

참고 서적 :