전체 글 (171) 썸네일형 리스트형 [정렬] in-place vs not in-place 1. in-place 원소의 개수에 비해 충분히 무시할 만한 저장 공간을 더 사용하는 정렬 알고리즘 2. not in-place 원소의 개수에 비례하여 저장 공간을 더 사용하는 정렬 알고리즘 [정렬] stable vs not stable 1. stable vs not stable 중복된 키값이 있을 때 이를 원래 순서대로 정렬하는 알고리즘 정렬 전처럼 주황색 3이 초록색 3보다 앞에 있다. 2. in-place vs not in-place 중복된 키값이 있을 때 이를 원래 순서와 다르게 정렬하는 알고리즘 정렬 전과 다르게 주황색 3이 초록색 3보다 뒤에 있다. [정렬] 퀵 정렬 [Quick Sort] 퀵 정렬에 대해 알아보자. 이는 분할 정복을 통해 구현한다. (분할 정복은 큰 문제를 작은 문제 단위로 쪼개면서, 쉽게 풀 수 있는 문제 단위로 나눈 뒤 그것들을 다시 합치는 방식이다.) 불안정 정렬이고 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬이다. 그리고 병합 정렬과 함께 빠른 정렬에 해당한다. 병합 정렬과는 분할 정복을 통해 해결한다는 공통점이 있다. 차이점은 아래와 같다. 1) 병합 정렬 : O(n)의 시간이 걸리는 과정을 재귀호출 후에 한다. (분할 후 병합 시점에서 비교 연산 발생) 2) 퀵 정렬 : O(n)의 시간이 걸리는 과정을 재귀호출 전에 한다. (분할 시점부터 비교 연산 발생) 따라서 퀵 정렬이 병합에 들어가는 비용이 적거나 구현 방법에 따라서 아예 병합하지 않을 수도 있다... 이전 1 ··· 21 22 23 24 25 26 27 ··· 57 다음
