선택정렬(Selection Sort)

정렬이란?

💡원소들의 크기에 따라 순서를 배치하는 것

• 내림차순: 크기가 증가하는 순으로 원소들을 배치하는 것
• 오름차순: 크기가 감소가는 순으로 원소들을 배치하는 것

 

선택정렬(Selection Sort)

💡리스트를 반복적으로 순회하며 현재 위치에 맞는 값을 선택하여 제자리에 놓는 방식

https://www.geeksforgeeks.org/

동작방식

1. 초기상태
2. 첫번째 반복
3. 두번째 반복
4. 반복
5. 종료

구현

#include <iostream>

using namespace std;

int main(){
        int arr[] = {8, 3, 2, 5, 1, 1, 2, 5, 8, 9};
        int size = sizeof(arr) / sizeof(arr[0]);

        // 선택정렬
        for (int i = 0; i < size - 1; i++) { // 좌측부터 하나의 위치 기준
            for (int j = i + 1; j < size; j++) { // 크기 비교해서 교체 여부 판단
                if (arr[i] > arr[j]) {
                    swap(arr[i], arr[j]);
                }
            }
        }
}

 

의의

선택정렬은 정렬 알고리즘에서는 구현이 간단하지만 성능은 떨어진다. 하지만 학습 용도로 swap 연산, 인덱싱을 연습하기에는 좋다.

std::swap(int a, int b); // a 와 b의 값을 교환

std::min(int a, int b); // a와 b의 값 중에 최소값을 반환

 

시간복잡도

💡 O(N^2)

 

안정성에 따른 정렬의 분류

정렬은 같은 값일 경우 순서가 유지되는 지 여부에 따라 안정한 지 여부로 분류할 수 있다. 정렬하는 와중에 값이 동일한 다른 두 원소의 순서가 바뀌는 경우에는 불안정하다고 하고 순서가 유지되는 경우에는 안정하다고 한다.