[Javascript] 정렬(1) - 선택 정렬(sorting)

1. 선택정렬 (selection sort)

• 매 단계에서 가장 작은 원소를 선택해서 앞으로 보내는 정렬 방법
• 앞으로 보내진 원소는 더 이상 위치가 변경되지 않는다.
• 시간 복잡도 O(N²)로 비효율적인 정렬 알고리즘 중 하나

 

1-1. 동작 방식

• 각 단계에서 가장 작은 원소 선택
• 현재까지 처리되지 않은 원소들 중 가장 앞의 원소와 위치를 교체

 

1-2 시간 복잡도

• 매 단계에서 가장 작은것을 선택하는 데에 약 N번의 연산이 필요 (선형 탐색)
• 결과적으로 약 N개의 단계를 거친다는 점에서 최악의 경우 O(N²)의 시간 복잡도를 가진다.

 

ex) 정렬할 배열

2

4

3

1

9

8

6

7

5

 

1단계

1

4

3

2

9

8

6

7

5

 

2단계

1

2

3

4

9

8

6

7

5

 

3단계

1

2

3

4

9

8

6

7

5

 

4단계

1

2

3

4

9

8

6

7

5

 

5단계

1

2

3

4

5

8

6

7

9

 

6단계

1

2

3

4

5

6

8

7

9

 

7단계

1

2

3

4

5

6

7

8

9

 

8단계

1

2

3

4

5

6

7

8

9

 

9단계

1

2

3

4

5

6

7

8

9

 

소스코드 예시

//선택정렬함수
function selectionSort(arr){
	for (let i = 0; i < arr.length; i++) {
    	let minIndex = i;
        for (let j = i + 1; j < arr.length; j++) {
        	if(arr[minIndex] > arr[j]){
            	minIndex = j;
            }
        }
        //swap
        let temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

let check = [3, 6, 5, 8, 10, 2];

selectionSort(check);
console.log(check); // [2, 3, 5, 6, 8, 10]