stable_sort 검색 결과

해당 글 2건
선택 정렬 알고리즘 : 가장 우선 순위가 높은 것을 매 턴마다 찾는다.

오늘은 선택 정렬 알고리즘에 대해 공부해 봅시다. 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
stable sort : 우선 순위가 같은 데이터들은 어떻게 정렬될까요?

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