[알고리즘] 선택 정렬 (Selection Sort)

1. 선택 정렬

말 그대로 현재 위치에 들어갈 데이터를 찾아 선택하는 알고리즘이다.
데이터를 '비교'하면서 찾기 때문에 '비교 정렬'이며 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않기 때문에 '제자리 정렬'이기도 하다. 정확히는 데이터를 서로 교환하는 (swap)에서 임시 변수를 하나 필요로 하나, 이는 충분히 무시할 만큼 적은 양이기 때문에 제자리 정렬로 본다.

 

[장점]
1. 추가적인 메모리 소비가 작다.

 

[단점]1. 시간복잡도가 O(N^2)이다.
2. 안정 정렬이 아니다. (불안정 정렬)

 

두 번째 단점인 안정 정렬이 아니라는 것에 대해 알아보자.

 

[B1, B2, C, A] (A < B < C)

 

주의해서 볼 점은 B에 붙어있는 숫자는 임의로 붙인 숫자다. B1이 B2보다 크거나 작은 것이 아니라는 점 유의하길 바란다.

 

그럼 순서대로 순회하면서 교환한다면 이렇다.

round 1 : [A, B2, C, B1]

round 2 : [A, B2, C, B1]

round 3 : [A, B2, B1, C]

 

이렇게 초기의 B1 B2의 순서가 뒤 바뀐 것을 볼 수 있다.

 

이러한 상태를 불안정 정렬이라고 하는데 문제가 되는 이유는 예로들어 학생을 관리하고자 할 때, 성적순으로 나열하되, 성적이 같으면 이름을 기준으로 정렬하고 싶다고 할 때. 즉, 정렬 규칙이 다수이거나 특정 순서를 유지해야 할 때 문제가 될 수 있다.

 

[(가영, 60), (가희, 60), (찬호, 70), (동우, 45)] 이렇게 리스트가 존재한다고 생각해 보자. 성적순이되, 성적이 같다면 이름순으로 정렬해야 한다고 했다.

 

그러면 보통 이름을 일단 정렬을 해놓을 것이다.

 

<이름 정렬 순>

[(가영, 60), (가희, 60), (동우, 45), (찬호, 70)]

 

그 다음에 '성적순'으로 정렬할 것이다. 만약 선택 정렬을 하면 어떻게 되는지 보자.

 

round 1 : [(동우, 45), (가희, 60), (가영, 60), (찬호, 70)]

round 2: [(동우, 45), (가희, 60), (가영, 60), (찬호, 70)]

round 3: [(동우, 45), (가희, 60), (가영, 60), (찬호, 70)]

 

이렇게 '가희'보다 '가영'이 앞에 있어야 함에도 순서가 바뀌어 버린 것을 볼 수 있다.

 

 

자세히 보기 https://visualgo.net/en/sorting

 

2. 자바로 알고리즘 구현

1. for (int stand = 0; stand < dataList.size() - 1; stand++)로 반복
2. lowest = stand 로 놓고,
3. for (int index = stand + 1; index < dataList.size(); index++)로, stand 이후부터 반복

• 내부 반복문 안에서 dataList[lowest] > dataList [index] 이면,
  • lowest = num

4. dataList[lowest] 와 dataList [index] 스왑

import java.util.ArrayList;
import java.util.Collections;

public class SelectionSort {
    public ArrayList<Integer> sort(ArrayList<Integer> dataList) {
        int lowest;
        for (int stand = 0; stand < dataList.size() - 1; stand++) {
            lowest = stand;
            for (int index = stand + 1; index < dataList.size(); index++) {
                if (dataList.get(lowest) > dataList.get(index)) {
                    lowest = index;
                }
            }
            Collections.swap(dataList, lowest, stand);
        }
        return dataList;
    }
}

 

3. 정리

 

선택 정렬의 경우 정렬 알고리즘의 기초다 보니 대부분 버블 정렬(Bubble Sort), 삽입 정렬(Insertion Sort)과 함께 많이 배운다. 물론 성능상 좋지는 못하더라도 이러한 알고리즘들을 확실하게 익혀야 좀 더 고급스러운 정렬들을 이해할 수 있으니 잘 익혀두면 좋다.

각 정렬 알고리즘 별 시간 복잡도와 평균 정렬 속도 이다.

 

 

 

 

 

출처 : https://st-lab.tistory.com/168