[Algorithm] 선택정렬(Selection Sort)을 쉽게 알아보자

알고리즘 중에는 정렬 알고리즘(sorting algorithm)이 존재한다. 정렬 알고리즘이란 n개의 숫자가 주어졌을 때 이를 오름차순 / 내림차순으로 정렬하는 알고리즘을 말하며 정렬 알고리즘 안에는 다양한 알고리즘이 존재하고, 알고리즘에 따라 시간 복잡도가 다르다. 오늘은 정렬 알고리즘 중에서 선택 정렬 알고리즘에 대해 쉽게 알아보려고 한다.

 

💡 선택 정렬

선택 정렬이란, 현재 선택된 데이터 이후의 정렬되지 않은 데이터 중에서 가장 작은(혹은 가장 큰) 데이터를 선택해 현재의 데이터와 위치를 교환하는 방식으로 정렬되는 방식이며 제자리 정렬 알고리즘의 하나이다.

☝🏻 여기서 잠깐 , 제자리 정렬이 무엇인가요?

주어진 공간 외에 추가적인 공간을 사용하지 않는 정렬로 이미 할당된 배열 내에서 원소들의 정렬이 일어나는 방식

 

💡 선택 정렬의 과정

▲ 선택 정렬의 과정

 

1. 주어진 배열 중에 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다.
3. 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다.
4. 하나의 원소만 남을 때까지 1~3 과정을 반복한다.

▲ gif로 한눈에 보는 선택정렬 [출처: https://github.com/GimunLee]

 

💡 JAVA로 보는 선택 정렬 - ① 오름차순 

void selectionSort(int[] arr) {
    int indexMin, temp;
    
    // 1. 원소를 넣을 위치(index) 선택
    for (int i = 0; i < arr.length-1; i++) {        
        indexMin = i; // 배열의 첫번째 값을 최소값으로 설정
        
        // 2. i+1번째 원소부터 index 의 값과 비교
        for (int j = i + 1; j < arr.length; j++) {  
        	// 3. 현재 선택한 자리에 있는 값보다 순회하고 있는 값이 작다면, index를 갱신
            if (arr[j] < arr[indexMin]) {           
                indexMin = j;
            }
        }
        // 4. swap(arr[indexMin], arr[i])
        temp = arr[indexMin];
        arr[indexMin] = arr[i];
        arr[i] = temp;
  }
  System.out.println(Arrays.toString(arr));
}

💡 JAVA로 보는 선택 정렬 - ② 내림차순

public static int[] SelectionSortDesc(int[] items) {
        int indexMax, temp;
        for (int i=0;i<items.length-1;i++) {
            indexMax = i;
            for(int j=i+1;j<items.length;j++) {
                //선택원소 보다 큰 원소위치 찾기
                if (items[j] > items[indexMax]) {
                    indexMax = j;
                }
            }
            temp = items[indexMax]; //최대값 임시 저장
            items[indexMax] = items[i]; //최대값 위치에 선택위치의 원소와 교환
            items[i] = temp; //선택위치에 최대값 교환
        }
        return items;
    }

 

 

💡 선택 정렬의 장/단점

[장점]

• 거품정렬(Bubble Sort)와 마찬가지로 알고리즘이 단순하다.
• 비교횟수는 많지만 거품정렬에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료 상태에서 비교적 효율적이다.

[단점]

• 시간 복잡도가 O(n^2) 으로 비효율적이다.
• 불안정 정렬(Unstable sort)이다.

☝🏻 여기서 잠깐 , 불안정 정렬이 무엇인가요?

비교 시 같은 값으로 처리하지만, 실제 값이 다른 경우에 정렬 후 순서가 바뀔 수 있는 정렬

 

 

[참고자료]

https://sxxb-in.tistory.com/4?category=895744

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

https://creatordev.tistory.com/69

불러오는 중입니다...