알고리즘
JS 선택정렬
KairoYang
2020. 6. 10. 22:57
선택정렬
-먼저 주어진 리스트 중에 최소값을 찾는다.
-그 값을 맨 앞에 위치한 값과 교환한다.
-이제 맨 앞을 제외하고 다시 순회하며 최소값을 찾는다.
-그 값을 맨 앞 위치 바로 다음 위치와 교체한다..... 반복
Big O
-Worst case: O(n^2): 정렬이 하나도 안 되어있는경우
-Best case: O(n^2): 이미 정렬이 되어 있는 경우
-선택 정렬은 버블과 삽입과 다르게 정렬이 이미 되어있는 경우에도 O(n^2)의 시간 복잡도를 가진다.
매번 정해진 자리에 올 수 있는 최소값을 찾아야하기 때문이다. 성능이 매우 떨어진다.
장점: in place이기 때문에 메모리가 절약된다.직관적으로 이해하기 쉽다
단점: 최선의 경우에도, 최악의 경우에도 O(n^2)의 시간이 걸리는 만큼 성능이 매우 떨어진다.
UnStable-선택정렬은 데이터가 중복되는 경우 위치가 바뀔 수 있다.
항상 첫번째 자리를 기준으로 정렬하므로 i는 0부터시작하고
첫번째 자리를 가장 작은 값이라고 가정하므로 minIndex 변수에 i를 담아준다.
i+1번째 자리부터 순회하며 array[i]보다 작은 값이 있는지 검사하고
검사가 끝나고 minIndex값이 i 와 같지 않다면 그 값과 i번째 값을 교환한다.