반응형

알고리즘/알고리즘 구현 2

merge-insertion sort, 혹은 Ford–Johnson algorithm 찬찬히 뜯어보기(2)

이전 글 보러가기 : https://ebang.tistory.com/103 3. merge insert sort 그래서 결국 merge insert 는 뭔가하면, 배열을 쪼개고 다시 합병하는 과정이라는 점에서 merge sort, 원소가 들어가는 부분을 탐색하는 점에서 Insertion sort 의 포인트를 갖고 있는 알고리즘이라고 할 수 있다. 단 이전의 insertion sort 에서 설명된 것과는 다르게 삽입될 부분이 이진탐색으로 탐색된다. 이진 탐색은 이미 배열이 정렬되어있을 때, 특정 값이 들어갈 위치를 범위를 절반으로 줄여가면서 탐색하는 기법이다. (중간값보다 크면 그 이후 범위에서 다시 찾고, 중간값보다 작으면 그 이전 범위에서 다시 찾는 방식) 그리고 이게 핵심이다. binary searc..

merge-insertion sort, 혹은 Ford–Johnson algorithm 찬찬히 뜯어보기(1)

개요 1. 소개 2. merge sort 3. insertion sort 4. binary search (이진 탐색) 4. Tim sort 1. 소개 꽤나 느린 알고리즘이고 특정 자료구조가 필요하다. (쌍으로 묶는... ) 하지만 컴퓨터 과학적인 관점에서 꽤나 흥미롭다 : 숫자 비교를 아주 최적화해서 하지는 못하지만, 비교의 횟수를 최소로 만드는 면에서는 가장 널리 알려진 알고리즘이다. The Art of Computer Programming, Volume 3 by Donald Knuth 에서 소개 되어있는 알고리즘이다. 이해하는데 이틀 ~ 삼일 정도 걸렸고 여태 알고 있던 알고리즘으로만 사고방향이 흘러서 그 틀을 깨는데 가장 시간이 오래걸렸다... 그래도 찬찬히 뜯어본만큼 기록으로 남겨두고 싶어서 글을..

728x90
728x90