선택 정렬 알고리즘 : 가장 우선 순위가 높은 것을 매 턴마다 찾는다.
오늘은 선택 정렬 알고리즘에 대해 공부해 봅시다. 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
최근댓글