선택 정렬

정렬은 데이터를 쉽게 사용할 수 있도록 특정 순서로 데이터 집합을 정렬 및 재배열하는 작업 또는 기술을 말합니다. 목록의 요소를 숫자 순서 또는 사용자 정의 순서 중 하나일 수 있는 특정 순서로 배치하는 데 사용되는 많은 정렬 알고리즘이 있습니다. 널리 사용되는 정렬 알고리즘 중 일부는 다음과 같습니다.

선택 정렬

삽입 정렬

버블 정렬

병합 정렬

오늘은 Selection Sort Algorithm에 대해 알아보겠습니다.

선택 정렬은 초보자도 쉽게 이해할 수 있는 간단한 정렬 알고리즘입니다. 선택 정렬에서 배열은 다음과 같이 두 부분으로 나뉩니다.

오른쪽 끝에 정렬된 부분입니다.

왼쪽 끝의 정렬되지 않은 부분입니다.

첫째, 전체 목록이 정렬되지 않은 부분을 차지하는 동안 정렬된 부분은 비어 있습니다. 정렬되지 않은 부분의 최소 요소를 찾아 정렬되지 않은 부분의 가장 왼쪽 요소와 교체합니다. 그런 다음 해당 요소는 정렬된 배열의 일부가 됩니다. 시간이 지남에 따라 분류된 부분은 확장되고 분류되지 않은 부분은 축소됩니다. 마지막으로 정렬되지 않은 부분이 비게 되면 정렬된 배열을 얻게 됩니다.
선택 정렬 알고리즘에서 배열이 정렬되는 방식은 아래 이미지에 나와 있습니다.



선택 정렬을 위한 의사 코드

1. for i=1 to i=n-1
2. min=i
3. for j=i+1 to j=n
4.  if A[j]<A[min], then
5.    min=j
6. end for
7. if min≠i then , interchange A[i] and A[min]
8. end for

C에서 선택 정렬 구현

//arr is the name of the array to be sorted
// n is the size of the array

void SelectionSort(int arr[], int n) 
{ 
    int i, j, min; 

    for (i = 0; i < n-1; i++) 
    { 
        // Find the minimum element in the unsorted part of the array
        min = i; 
        for (j = i+1; j < n; j++) 
          if (arr[j] < arr[min]) 
            min = j; 

        // Swap the found minimum element with the first element of the unsorted array
            int temp = arr[i];  
            arr[i] = arr[min];  
            arr[min] = temp; 
    } 
} 

선택 정렬의 복잡성

첫 번째 패스에서 가장 작은 값을 가진 요소를 찾으려면 모든 n개 요소를 스캔해야 합니다. 따라서 n-1 비교는 첫 번째 패스에서 필요합니다. 그런 다음 가장 작은 값이
첫 번째 위치의 요소. 패스 2에서 두 번째로 작은 값을 찾으려면 나머지 n – 1개 요소 등을 스캔해야 합니다. 그러므로,

(n – 1) + (n – 2) + ... + 2 + 1
= n(n – 1) / 2 = O(n2) 

따라서 선택 정렬의 시간 복잡도는 주어진 배열에 있는 요소의 원래 순서와 관계없이 동일함을 알 수 있습니다.
공간복잡도는 임시변수 temp를 사용하므로 0(1)이다.

선택 정렬의 장점

매우 간단하고 구현하기 쉽습니다.

매우 작은 데이터 세트를 정렬하는 데 사용할 수 있습니다.

요약하면 선택 정렬은 이해하기 쉬운 간단한 정렬 알고리즘이며 선택 정렬 알고리즘에 대한 지식은 다른 정렬 알고리즘을 배우는 데 강력한 입문을 하는 데 도움이 될 것입니다.