정렬이란? 이름, 학번, 키 등 핵심 항목(key)의 대소관계에 따라 데이터 집합을 일정한 순서로 나열하는 작업을 말한다.
이 알고리즘을 이용해 데이터를 정렬하면 검색을 더 쉽게하는 자료형으로 바꿀수도 있다.
정렬에는 보통 오름차순(ascending order) 정렬과 내림차순(descending order) 정렬이 있다.
정렬 알고리즘의 안정성
이 글에서는 정렬 알고리즘의 대표적인 알고리즘 8개를 배워볼 것이다.
이 때 정렬 알고리즘은 안정된(stable)알고리즘과, 그렇지 않은 알고리즘을 나눌 수 있다.
만약 같은 반 5명의 점수가 아래와 같다고 하자,
1번 = 10점
2번 = 20점
3번 = 21점
4번 = 10점
5번 = 21점
해당 5명을 점수를 key로하여 안정된 오름차순 알고리즘으로 정렬하면 아래처럼 정렬 될 것이다.
1번 = 10점
4번 = 10점
2번 = 20점
3번 = 21점
5번 = 21점
이번엔 5명을 점수로 key로하여 오름차순 알고리즘으로 정렬하지만 안정되지 않은 알고리즘으로 정렬 한다.
4번 = 10점
1번 = 10점
2번 = 20점
3번 = 21점
5번 = 21점
뭐가 다른지 한 눈에 알 수 있을 것이다. 10점이라는 같은 점수(key값)를 가지고 있는 학생들을 정렬하면 번호가 낮은 친구가 제일 앞에 정렬된다.
반면 안정되지 않은 알고리즘은 같은 10점끼리의 학생들 중 번호가 낮아도 먼저 정렬이 안될 수 있다.
물론 우연의 일치로 안정된 알고리즘처럼 정렬되는 경우는 있을 수 있다.
이렇게 안정된 정렬은 키값이 같은 요소의 순서가 정렬 전후에도 유지되는 것을 말한다.
또한 안정되지 않은 정렬은 키값이 같은 요소의 순서가 정렬 전후에 유지되는 것을 보장하지 않는다.
내부 정렬과 외부 정렬
학교 책상에서 트럼프카드 1팩(54)장을 순서대로 놓는다고 생각 해 보자. 딱히 어려운 일은 아닐 것이다. 충분히 54장을 책상위에 모두 정렬해 놓을 수 있을것 같다.
이번엔 10팩을 순서대로 놓는다고 생각 해 보자. 될까? 책상이 미어터질것이다.
정렬 알고리즘도 하나의 배열에서 작업할 수 있을땐 내부 정렬(internal sorting)을 사용하고, 하나의 배열에서 작업할 수 없을땐 외부 정렬(external sorting)을 사용한다.
- 내부 정렬: 정렬할 모든 데이터를 하나의 배열에 저장할 수 있을 때 사용하는 알고리즘
- 외부 정렬: 정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없을 때 사용하는 알고리즘
외부 정렬은 내부 정렬을 응용한 것으로, 외부 정렬을 구현하려면 작업을 위한 별도의 파일 등이 필요하고 알고리즘도 복잡하다.
정렬 알고리즘의 핵심 요소
정렬 알고리즘의 핵심 요소는 교환, 선택, 삽입이다. 대부분의 정렬 알고리즘은 이 3가지 요소를 응용한 것이다.
