[Unity C#] 선택 정렬(수정)

개념

Selection Sort는 Bubble Sort과 유사한 알고리즘으로, 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘이다.

과정

1. 주어진 배열 중에 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다. (pass)
3. 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다.

시간복잡도

데이터의 개수가 n개라고 했을 때,

• 첫 번째 회전에서의 비교횟수 : 1 ~ (n-1) => n-1
• 두 번째 회전에서의 비교횟수 : 2 ~ (n-1) => n-2
• ...
• (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2

비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 배열을 정렬하는데 O(n^2) 만큼의 시간이 걸린다. 최선, 평균, 최악의 경우 시간복잡도는 O(n^2) 으로 동일하다.

장점

• Bubble sort와 마찬가지로 알고리즘이 단순하다.
• 정렬을 위한 비교 횟수는 많지만, Bubble Sort에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료상태에서 비교적 효율적이다.
• Bubble Sort와 마찬가지로 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. => 제자리 정렬(in-place sorting)

단점

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

소스코드(JAVA)

public class SelectionSort_Source : MonoBehaviour
{
    // Start is called before the first frame update
    void Start()
    {
        int[] arr = new int[10] { 8, 2, 5, 4, 3, 9, 1, 6, 10, 7 };

        SelectionSort(arr);
    }

    //선택정렬 수행
    void SelectionSort(int[] arr)
    {
        for(int i = 0; i < arr.Length-1; i++)
        {
            for( int j = i+1; j < arr.Length; j++)
            {
                if (arr[i] > arr[j])
                { 
                    Swap(arr, i, j);
                }
            }
        }

        PrintArray(arr);
    }

    //결과물 출력
    void PrintArray(int[] arr)
    {
        for(int i = 0; i < arr.Length; i++)
        {
            Debug.Log(arr[i]);
        }
    }

    void Swap(int[] arr,int i, int j)
    {
        int temp;

        temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
}

소스코드 수정(C++)

#include <iostream>

int main() {
    int N,i,j,key,tmp;
    int arr[100];
    
    scanf("%d",&N);
    for(i = 0; i < N; i++){
        scanf("%d",&arr[i]);
    }
    
    for(i = 0; i < N-1; i++){
        key = i;
        
        for(j = key; j < N; j++){
            if(arr[key] > arr[j]){
                key = j; // 비교대상 중 작안 작은 값이 key에 들어감
            }
        }
        tmp = arr[key]; //i와 key를 바꿈
        arr[key] = arr[i];
        arr[i] = tmp;
    }
    
    for(i = 0; i < N; i++){
        printf("%d ", arr[i]);
    }
    return 0;
}
//Swap연산을 최소화 하는 방안임

 

*참고

gyoogle.dev/blog/algorithm/Selection%20Sort.html