알고리즘, 자료구조/정리

선택 정렬 알고리즘 (Selection sort Algorithm)

jaee 2023. 3. 18. 12:05

 
틀린 내용을 발견하신 경우 말씀 부탁드립니다! 🙇

 
선택 정렬 알고리즘은 제자리(in-placing) 알고리즘 중 하나로, 결과 값을 만들기 위해 별도의 추가적인 메모리를 사용하지 않고 입력 배열의 메모리만 사용하는 정렬 방법이다. 제자리(in-placing) 알고리즘은 일반적으로 입력 값이 출력 값으로 덮어씌워지며, 입력 값을 출력 값으로 교체하거나 요소들의 위치를 바꾸는 방식으로 출력 값을 반환한다. 선택정렬 시각화 참고
 

https://codepumpkin.com/selection-sort-algorithms/

 

Pseudo code

n개의 요소로 이루어진 (정렬되지 않은) 배열이 있을 경우,
첫 번째 ~ n번째까지 탐색하며 기준에 맞는 요소를 찾은 뒤, 첫 번째 자리와 위치를 변경한다. 
두 번째 ~ n번째까지 탐색하며 기준에 맞는 요소를 찾은 뒤, 두 번째 자리와 위치를 변경한다.
세 번째 ~ n번째까지 탐색하며 기준에 맞는 요소를 찾은 뒤, 세 번째 자리와 위치를 변경한다.
... 
n-1번째 ~ n번째까지 탐색하며 기준에 맞는 요소를 찾은 뒤, n-1번째 자리와 위치를 변경한다.
n번째까지 탐색을 마치면 정렬을 종료한다.

 
 

Javascript code

const selectionSort = (array) => {
	for (let i = 0; i < array.length - 1; i++) {
        // 제일 작은 수를 저장할 변수를 선언하고, array[i]를 할당한다.
    	let min = array[i];
        // 제일 작은 수의 인덱스를 저장할 변수를 선언하고, 인덱스i 숫자를 할당한다.
        let minIndex = i;
        
        for (let j = i+1; j < array.length; j++) {
            // 제일 작은 수보다 더 작은 값을 발견한 경우, min과 minIndex를 변경한다.
            if (min > array[j]) {
            	min = array[j];
                minIndex = j;
            };
        };
        
        // 제일 작은 수와 i번째 숫자의 위치를 서로 바꾼다.
        array[minIndex] = array[i];
        array[i] = min;
    };
    
    return array;
};


selectionSort([8,9,2,10,6,7,1,5,3,4]);
// result: [1,2,3,4,5,6,7,8,9,10]

 

시간복잡도

선택 정렬 알고리즘의 시간 복잡도는 O(N^2)이다.
n + (n-1) + (n-2) + (n-3) + ... + 1 = n(n+1)/2 → O(n^2)
 
 

장단점

장점

  • 단순하다.
  • 비교는 여러번 수행되나 실제 교환은 적기에 한 번씩만 발생된다. 그러므로 교환이 빈번하게 이루어져야하는 자료 상태에서 효율적으로 사용할 수 있다.
  • 메모리 낭비가 없으므로 메모리가 제한적인 경우에 사용하기 좋다.

단점

  • 속도가 느리다.
  • 이미 정렬된 배열에 소수의 자료가 추가되면 재정렬할 때 최악의 처리 속도를 보인다.
  • 불안정(Unstable)하다. (= 순서 유지가 보장되지 않는다)
    - 안정 정렬:동일한 값에 대해 기존의 순서가 유지되는 정렬 방식 ( 버블 정렬, 삽입 정렬 )
    - 불안정 정렬: 동일한 값에 대해 기존의 순서가 유지되지 않는 정렬 방식 ( 선택 정렬, 퀵 정렬)

 

 

참고 자료