정렬 검색 결과

해당 글 14건
병합 정렬 : sorting 된 두 배열을 합치면서 해결한다.

병합 정렬 (merge sort)는, 분할을 하고, 정복하는 단계에서 정렬된 두 배열을 합치는 식으로 동작합니다. 추가적인 공간이, 배열 크기만큼 필요하다는 것을 생각해 본다면, 메리트가 없을 수도 있어요. 실제로, Quick이 merge보다 빠르다는 이야기도 있을 정도이니까요. 그런데, Quick이 최악의 경우에 제곱에 비례하는 시간이 걸리는 반면에, merge는 그렇지 않아요. depth가 logn이기 때문입니다. 실제로 머지는 최악이던 최선이던 O(nlogn)에 동작합니다. 버블이나, insertion, selection sort에 비하면 꽤 빠릅니다. 일단 정렬이 된 두 부분 배열이 있다고 해 봅시다. 즉, le에서 mid까지 정렬이 되어 있고, mid+1부터 ri까지 sorting이 되어 있습니..
자료알고/알고리즘 2019. 7. 30. 20:46
버블 정렬 알고리즘 : 인접한 원소들을 비교하면서 진행한다.

정렬 알고리즘 중, 버블 정렬은 서로 이웃한 원소들끼리 비교하면서 우선 순위가 낮은 데이터를 뒤로 보내는 정렬을 합니다. 이것도, insert, selection과 같이 시간 복잡도는 O(n^2)인데요. 따로 처리를 하지 않는 이상, 어떠한 경우에도, 제곱에 비례하기 때문에, merge나 heap에 비해서는 거의 안 쓰인다고 보시면 되어요. 배열 [2, 1, 4, 5, 3]을 오름차순으로 정렬해 볼 겁니다. 그러면 수가 작을수록 우선 순위가 높고, 수가 클수록 우선 순위가 낮다는 이야기가 되겠어요. 인접한 두 수 a와 b가 있다면, a보다 b가 더 작다면, a랑 b를 바꾸는 식으로 동작할 듯 싶습니다. 배열이 이렇게 있어요. 아직 sorting 하기 전이에요. 총 5회전을 돌 건데요. 이것은 1회전입니다..
자료알고/알고리즘 2019. 7. 23. 23:17
계수 정렬 (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
stable sort : 우선 순위가 같은 데이터들은 어떻게 정렬될까요?

stable sort는, 정렬 알고리즘을 논할 때 간과하고 넘어가기 쉬운 키워드입니다. 하지만, 간과해서는 안 되는 것입니다. 이것이 대체 무엇을 의미할까요? 우선순위가 같은 데이터가 여러 개 있을 때, 정렬이 끝난 후에도, 순서가 유지되는 정렬을 stable sort라 합니다. 그렇지 않다면 unstable하다고 합니다. 예제를 하나 봅시다. n개의 데이터를 정렬한다고 해 봅시다. 매 회전마다 [i,e] 구간에 있는 원소들을 탐색해서, 가장 우선순위가 높은 원소가 있었던 위치를 lo라고 해 봅시다. 이 때 lo와 i에 있는 원소를 뒤바꾸는 정렬이 있다고 해 봅시다. 위에 있는 숫자는 숫자, 밑에 있는 숫자는 정렬 전 위치라고 해 봅시다. 만약에 숫자를 오름차순 정렬한다고 하면, 1이 0보다는 우선 순위..
자료알고/알고리즘 2019. 7. 14. 16:51