병합정렬 (2) 썸네일형 리스트형 <알고리즘> 퀵정렬은 병합정렬보다 항상 좋은 선택인가 1. 소개 최근에 필자는 하스켈이라는 언어를 공부하고 있다. 함수형 프로그래밍에 대한 깊은 이해를 위해서 겉핥기를 하고 있는데, 최근 정렬과 관련하여 궁금한 점이 생겨서 이렇게 정리하게 되었다. 참고로 이 포스팅에서 하스켈에 대해 깊이 알 필요는 없으며 함수형 언어라고만 생각해도 이해하는 데에는 지장이 없다. Data.List는 리스트 정렬을 위한 sort 함수를 제공한다. 이 함수는 퀵정렬을 쓰지 않는다. 대신 병합 정렬이라는 알고리즘의 효율적인 구현을 사용한다. - WikibooksHaskell - 지금까지 공부하기로는 대부분의 언어에서 정렬 함수는 퀵정렬(Quick Sort)을 활용하고 있다고 배웠다. 심지어 같은 시간복잡도를 가지는 병합정렬에 비해 일반적으로 더 빠르며, 면접 준비에서도 그렇게 대.. <알고리즘> 삽입정렬과 병합정렬 1. 삽입정렬과 병합정렬 * 삽입 정렬(Insetion Sort) - 선택정렬과 버블정렬과 마찬가지로 제자리 정렬(in-place sorting) 알고리즘이다. - 삽입 정렬은 마치 카드게임에서 손 안의 패를 정렬하는 것과 같다. 카드를 새로 받으면 기존에 정렬시켜둔 카드 사이에 삽입시켜 정렬시킨다. 이에 따라 동일한 값에 대해 순서가 유지되는 안정정렬방식을 보장한다. - 삽입 정렬을 알아보기 위해 10 5 7 1 3 이라는 5개의 숫자를 오름차순으로 정렬시켜보자. - 삽입 정렬은 두 번째 값부터 정렬을 시작하며, 해당 값과 그 앞의 값들과만 비교한다. - 먼저 5와 10을 비교한다. 5가 더 작으므로 10을 뒤로 이동시키고 5를 그자리에 삽입한다. 5 > 10 7 1 3 5 10 7 1 3 - 다음은 .. 이전 1 다음
