정렬알고리즘 검색 결과

해당 글 7건
셀 정렬 : 갭을 줄여가면서 해결한다.

삽입 정렬의 복잡도는 O(n^2)입니다. 물론 평균 복잡도 또한 O(n^2)입니다. 물론, memcpy 등으로 실행 시간을 빠르게 할 수 있는 여지는 있지만, 거기까지일 뿐입니다. 다만, insertion sort의 장점도 있는데요. 거의 정렬된 데이터에 대해서는 상당히 빠르게 동작한다는 장점이 있어요. 하지만, 한 번에 한 요소씩. 비교 1번 할 때 마다, 1요소씩만 move 하기 때문에 효율적이지 않은데요. 이를 보완하기 위해서 gap이라는 변수를 둡니다. 그러면 먼저 init 함수를 봅시다. 먼저, si 라는 벡터가 있습니다. 여기에 무슨 값들이 들어있는지 봅시다. 1, 4, 13, 40, 121, 361, 1093, 3280, ... 네. 이런 값들이 들어 있는데요. gap으로 쓸 겁니다. 예를 ..
자료알고/알고리즘 2019. 10. 14. 01:24
퀵 정렬 : bad partition이 발생할 경우 문제가 된다.

퀵 정렬 알고리즘은 간단하게 언급만 하고 넘어가겠습니다. 사실, ps에서 그리 많이 쓰이는 정렬 방법은 아니기 때문입니다. 다만, 평균적으로는 병합 정렬보다는 빠른데, 그 이유는 다음 시간에 평균 복잡도를 분석하면서, 언급하도록 하겠습니다. 먼저 퀵 정렬은 피봇을 잡는 것부터 시작합니다. arr의 [s,e] 구간을 정렬한다고 하면, pivot을 선택해서, 그 피벗이 있는 위치와 arr[s]의 값을 교환합니다. 이는, 피봇을 선택하는 함수와, 그걸 토대로 divide 하는 것을 별개로 생각하기 위해서입니다. 여기서 저는 pivot을 5로 잡았습니다. 그리고, 우리는 2개의 포인터를 잡을 겁니다. 이는 각각 le와 ri 포인터입니다. 어떤 식으로 교환이 일어나는지만 보시면 되는데요. 우리는 ri 포인터가 s..
자료알고/알고리즘 2019. 8. 15. 12:12
기수 정렬 (radix sort) : 버킷만 있으면 된다.

오늘은 기수 정렬에 대해서 알아보도록 하겠습니다. 이것은 키 2개를 가지고 비교하는 정렬이 아닌데요. 이 특성은 저번에 배운, counting sort의 '2개의 키 값을 비교'하는 '비교 기반 정렬이 아니다' 라는 성질을 가지고 있습니다. 이들과, merge sort는 키 2개를 직접 비교하는 비교 기반 정렬이냐, 아니냐의 차이가 있어요. 아래 두 개의 글을 잘 보셔도 눈치를 채실 수 있을 듯 싶습니다. [관련글] 빈도를 저장하는 counting sort. 알아봅시다. 정렬된 두 배열을 합치는 합병 정렬 알아보아요. 그러면, 이것은 어떻게 동작할까요? 저는 1가지 용어만 정의하겠습니다. b진법으로 잡고 정렬한다. 버킷의 갯수가 b개이다. 우리는 양의 정수를 표현할 때, x진법으로 표현할 수 있습니다. ..
자료알고/알고리즘 2019. 8. 2. 01:07
계수 정렬 (counting sort) : 특정 숫자의 빈도를 센다.

2가지 정렬을 배웠습니다. insert, select. 이 두 개는 키 값들을 비교를 했습니다. 2개의 값을 compare 했습니다. 제가 오늘 설명하는 counting sort, 계수 정렬은 이 둘과 크게 다른 점이 있는데요. 두 개의 키 값을 비교하지 않는다는 것입니다. 즉, 비교 기반 정렬이 아닙니다. 그러면 어떻게 구현을 할까요? arr = [3, 6, 3, 0, 4, 1]이라고 해 봅시다. 최솟값이 양수고, 최댓값 또한 적당히 작은 수라고 해 봅시다. co[x]를, 배열에서 x가 나타난 빈도수라고 정의합시다. 그러면, arr을 순회하면서, 어떠한 값 v가 나오면 co[v]의 값을 하나씩 증가시키면 될 거에요. 먼저 co 배열은 아래와 같이 초기화가 되어 있습니다. 1번째 원소를 봅니다. 3입니다..
자료알고/알고리즘 2019. 7. 20. 01:22
선택 정렬 알고리즘 : 가장 우선 순위가 높은 것을 매 턴마다 찾는다.

오늘은 선택 정렬 알고리즘에 대해 공부해 봅시다. selection sort는 매 회전마다, 제일 우선 순위가 높은 값을 선택해서 재정렬 하는 알고리즘입니다. 배열 arr의 크기가 n이라고 해 봅시다. 그러면 총 n회전을 돌 건데요. i회전일 때 이러한 일을 수행합니다. 구간 [i,n]에서 우선순위가 가장 높은 위치 lo를 찾습니다. 그리고 배열에서 i번째 원소와 lo번째에 있는 값을 맞바꿉니다. 구간 [i,n]은 정렬이 되어 있지 않기 때문에, 우선 순위가 가장 높은 값과 위치를 찾기 위해서, i에서부터 n까지 보아야 합니다. 그러므로, 회전마다 O(n-i)만큼 걸리게 되고, 결과적으로 시간 복잡도는 O(n^2)가 됩니다. 매 회전마다, O(log(n)) 급에 해결할 수 있는 방법이 있는데, 특수한 자..
자료알고/알고리즘 2019. 7. 17. 19:47