'정렬' 태그의 글 목록

정렬 알고리즘에서 시간복잡도의 핵심 - 정렬 알고리즘의 평균적인 시간복잡도는 C * nlg(n) + A이지만 (C는 상수) 여기서 C값을 결정하는 요인은 '지역성의 원리'이다. - 지역성의 원리란 '최근에 참조된' 또는 '참조된 데이터의 주변의 데이터'가 또다시 참조될 가능성을 의미한다. - 따라서 이를 활용하면 캐시 hit 발생률이 높아지고 메모리까지 가지 않아도 빠르게 데이터를 읽어올 수 있다. - 예를 들어, merge sort의 경우에는 인접한 데이터들끼리 쪼개서 정렬 후 병합하기 때문에 지역성의 원리가 잘 활용된다고 볼 수 있다. - 퀵 소트의 경우 pivot 주변에서 데이터의 이동이 빈번하게 발생하기 때문에 작은 C값을 가진다. (퀵 소트는 추가적인 메모리 사용 없이도 정렬한다는 점에서 '평균..