Alex-Moon Alex-Moon

정렬 알고리즘의 정의 정렬(sorting)이란 텍스트나 숫자 등의 key를 항목 값의 대소 관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업을 말한다. 데이터를 정렬하면 쉽게 검색할 수 있다. 값이 작은 데이터를 앞쪽에 늘어놓는 것을 오름차순(ascending order)정렬이라 하고, 반대를 내림차순(descending order) 정렬이라 한다. 정렬 알고리즘은 데이터를 교환-선택-삽입하면서 정렬을 완료한다. 대부분의 정렬 알고리즘은 이 세가지를 응용한다. 안정성 여러 정렬 알고리즘 가운데 안정적인(stable) 알고리즘과 그렇지 않은 알고리즘으로 나눌 수 있다. 위의 그림처럼 안정적인 정렬 알고리즘은 값이 같은 원소의 순서가 정렬한 후에도 유지되는 것을 말한다. 안정적이지 않은 알고리즘..

병합 정렬 merge sort 노이만이 고안한 분할 정복 알고리즘. 퀵 정렬과 반대로 안정 정렬에 속한다. 배열을 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘이다. 과정 i) 리스트의 길이가 0또는 1이면 이미 정렬된 것으로 본다. ii) 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. iii) 각 부분 리스트를 재귀적으로 병합 정렬을 이용해 정렬한다. iv) 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 장점 - 안정적인 정렬 방법 - 레코드를 linked list로 구성하면, 데이터의 이동은 무시할 수 있을 정도로 작아진다. (퀵 정렬을 포함한 다른 정렬 방법보다 효율적이다.) 단점 - 레코드를 배열로 구성하면 임시 ..