선택정렬(Selection sort)

binary·2020년 6월 11일
0

Algorithm

목록 보기
1/2
post-thumbnail

선택정렬은 정렬 알고리즘 중에 가장 직관적이고 이해하기 쉬운(?) 알고리즘 입니다. 작동 방법을 살펴보면

  1. 첫번째 값을 기준으로 나머지 배열 중에서 최솟값을 찾습니다.
  2. 최솟값과 기준값의 위치를 바꿔줍니다.
  3. 나머지 값에 대해서도 반복합니다.

예를 들어 살펴보겠습니다. [9,1,7,8,4,3,0,2]의 배열을 선택정렬로 배열한다고 하면 아래와 같은 방법으로 정렬됩니다.


        테이블         최솟값

[9,1,7,8,4,3,0,2]    0

[0,1,7,8,4,3,9,2]    1

[0,1,7,8,4,3,9,2]    2

[0,1,2,8,4,3,9,7]    3

[0,1,2,3,4,8,9,7]    4

[0,1,2,3,4,8,9,7]    7

[0,1,2,3,4,7,9,8]    8

[0,1,2,3,4,7,8,9] 정렬 완료

  • 애니메이션으로 살펴보면 다음과 같습니다

복잡도

선택정렬의 복잡도는 O(n^2)입니다. 상당히 느리기 때문에 정렬에서 자주 사용되지는 않습니다.


구현 방법

function selectionSort(arr) {
    let i, j, temp, minIndex;
    for(i = 0; i < arr.length- 1; i++) {
        minIndex = i;  // 기준값으로 첫번째 값을 설정한다.
        for(j= i+1; j < arr.length; j++) { // 나머지 배열중에 최솟값의 위치를 찾는다
            if(arr[minIndex] > arr[j]) {
                minIndex = j
            }
        }
        temp = arr[minIndex]; // 찾은 최솟값을 임시 배열에 담는다
        arr[minIndex] = arr[i] // 기존 최솟값 위치에 기준값을 담는다
        arr[i] = temp; // 기준값은 최솟값으로 바꾼다
    }
    return arr
}

console.log(selectionSort([5,1,4,7,2,6,8,3])) // [1,2,3,4,5,6,7,8]



잘못된 부분이 있으면 언제든 말씀해주세요.

Reference

  1. https://www.zerocho.com/category/Algorithm/post/57f728c85141fc5fe4f4ca89
  2. https://im-developer.tistory.com/133
  3. https://ko.wikipedia.org/wiki/선택_정렬
profile
제대로 알기위해 기록합니다

0개의 댓글