C# 정렬 알고리즘 - 선택정렬(Selection sort)

• 선택정렬(Selection sort)이란?

선택정렬은 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해 나가는 방식이다.

 

1. 리스트에서 최소값을 찾는다.

2. 최소값을 맨 앞의 값과 교체한다. (Swap)

3. 교체한 맨 앞의 데이터는 정렬된 것으로 간주하고 다음 인덱스부터 1, 2 행위를 끝까지 반복한다.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace SelectionSort
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("선택정렬");

            int[] data = { 20, 15, 1, 5, 10 };

            Console.Write("시작값 - ");

            for(int i = 0; i < data.Length; i++)
            {
                Console.Write(data[i] + ", ");
            }
            Console.WriteLine();
            
            //정렬  
            for(int i = 0; i < data.Length; i++)
            {
                int min = i;

                for(int j = i + 1; j < data.Length; j++)
                {
                    //최소값 비교
                    if (data[min] > data[j])
                        min = j;
                }
                Swap(ref data[i], ref data[min]);
                                
                for (int k = 0; k < data.Length; k++)
                {
                    Console.Write(data[k] + ", ");
                }

                Console.WriteLine();
            }

            Console.Write("정렬값 - ");

            for(int i = 0; i < data.Length; i++)
            {
                Console.Write(data[i] + ", ");
            }
            Console.WriteLine();
        }

        static void Swap(ref int a, ref int b)
        {
            int temp = a;
            a = b;
            b = temp;
        }
    }
}

 

• 선택정렬의 특징

- 구현은 단순하지만 비효율적인 방법

- 두 개의 for 루프의 실행 횟수

 

• Big-O 표기법

- O(1)

- O(log n)

- O(n)

- O(n log n)

- O(n^2)