'Selection Sort' 태그의 글 목록

해당 순서에 원소를 넣을 위치는 이미 정해져 있고 어떤 원소를 넣을지 선택하는 알고리즘. 주어진 배열 중에 최솟값을 찾고 그 값을 맨 앞에 위치한 값과 교체한다. 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다. 시간 복잡도 (n - 1) + (n - 2) + ... + 2 + 1 = n(n - 1)/2만큼의 비교가 일어나기 때문에 n개의 주어진 배열을 정렬하는데 O(n^2)만큼의 시간이 걸린다. 최선, 평균, 최악의 경우 시간 복잡도는 O(n^2)로 동일하다. 공간 복잡도 주어진 배열 안에서 교환(swap)을 통해 정렬이 수행되므로 O(n) 장점 알고리즘이 단순하다. 정렬을 위한 비교 횟수는 많지만, Bubble Sort에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자..

Algorithm 2021. 10. 19. 23:21

이전 1 다음