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

선택 정렬(Selection Sort)

간단하지만 비효율적인 정렬 알고리즘입니다.

특징

1. 불안정 정렬(Unstable Sort): 동일한 값에 대해 상대적인 순서가 유지되지 않을 수 있습니다.
2. 제자리 정렬(In-place Sort): 입력 배열 이외에 추가적인 메모리를 사용하지 않습니다. 입력 배열 내에서 정렬이 수행됩니다.
3. 비교 기반 정렬(Comparison Sort): 원소들의 상대적인 크기를 비교하여 정렬합니다.

알고리즘 동작 방식

1. 주어진 배열에서 가장 작은 값을 찾습니다.
2. 찾은 가장 작은 값을 현재 정렬되지 않은 부분 배열의 첫 번째 원소와 교환합니다.
3. 정렬되지 않은 부분 배열의 범위를 하나씩 옮겨가며 위의 과정을 반복합니다.

장점

1. 구현이 간단하고 이해하기 쉽습니다.
2. 제자리 정렬이므로 메모리 사용량이 작습니다.

단점

1. 평균 및 최악의 경우에 대해 O(n^2)의 시간 복잡도를 가집니다. 모든 원소를 비교하고 교환해야 하기 때문에 비효율적입니다.
2. 대량의 데이터를 정렬할 때는 다른 알고리즘들보다 성능이 떨어질 수 있습니다.
3. 불안정 정렬이므로 동일한 값의 원소들의 상대적인 순서가 변할 수 있습니다.

요약

선택 정렬은 구현이 간단하고 작은 입력에 대해서는 효율적인 정렬 알고리즘입니다.

그러나 대량의 데이터에 대해서는 다른 알고리즘들보다 성능이 떨어지며, 최악의 경우에는 시간 복잡도가 O(n^2)이기 때문에 효율적인 알고리즘이라고는 할 수 없습니다.

또한 불안정 정렬이기 때문에 동일한 값의 원소들의 상대적인 순서가 변할 수 있습니다.

https://velog.io/@kich555/Algorithm-Selection-Sort

void DoSelectionSort()
{
	int arr[MAX_LENGTH];
	cout << "Before Sort" << endl;
	for (int i = 0; i < MAX_LENGTH; i++)
	{
		arr[i] = rand() % 100;
		cout << arr[i] << " ";
	}
	cout << endll;

	cout << "After Sort" << endl;
	SelectionSort(arr, MAX_LENGTH);
	for (auto num : arr)
		cout << num << " ";

	cout << endll;
	Pause;
	return;
}

void SelectionSort(int arr[], int length)
{
	int index;

	for (int i = 0; i < length - 1; i++)
	{
		index = i;
		for (int j = i + 1; j < length; j++)
			if (arr[j] > arr[index])
				index = j;

		swap(arr[index], arr[i]);
	}
}

 

기본참고 코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <stack>
#include <map>
#include <unordered_map>
#include <fstream>
#include <ostream>
#include <sstream>
#include <cctype>
#include <cmath>

#define fastio cin.tie(0)->ios::sync_with_stdio(0); cout.tie(0);
using namespace std;

int main() 
{
    fastio;

    int i, j, min, index, temp;
    int array[10] = { 1,10,5,8,7,6,4,3,2,9 };
    for (int i = 0; i < 10; i++)
    {
        min = INT_MAX;
        for (j = i; j < 10; j++)
        {
            if (min > array[j])
            {
                min = array[j];
                index = j;
            }
        }

        swap(array[i], array[index]);

        //algorithm 을 포함하지 않았을때 사용하는 스왑
        //temp = array[i];
        //array[i] = array[index];
        //array[index] = temp;
    }

    for (int i = 0; i < 10; i++)
    {
        printf("%d ", array[i]);
    }

    return 0;
}