선택정렬 (C#)

📌선택(Selection Sort) 란?

선택 정렬(Selection Sort)은 배열에서 최소값(또는 최대값)을 선택해서 맨 앞(또는 맨 뒤)으로 이동시키는 과정을 반복하여 전체 배열을 정렬하는 방식이다.

 

버블정렬때와 마찬가지로 오름차 순으로 다음 배열을 정렬해보자

 

선택 정렬은 다음과 같이 정렬된다.

 

첫 사이클을 돈 후, 배열에서 가장 작은값이 맨 앞으로 오게된다.

 

• 배열의 크기가 n일 때, i = 0, i < n - 1까지 반복한다.
• i + 1 번 원소부터 마지막 원소 크기까지 비교하기 때문에 j = i + 1, j < n까지 반복한다.
• i == 정렬할 원소, j == 비교할 원소
• 비교하는 원소들 중 가장 작은 값을 찾아야하므로 해당 인덱스를 저장할 int index를 따로 만들어 둔다.

public void SelectionSort(int[] arr)
{
    int n = arr.Length;
    for (int i = 0; i < n - 1; i++)
    {
        int index = i;
        for (int j = i + 1; j < n; j++)
            if (arr[index] > arr[j])
                index = j;

        int temp = arr[i];
        arr[i] = arr[index];
        arr[index] = temp;
    }
}