1. 선택정렬(Selection Sort) 정리 및 구현

선택정렬(Selection Sort)

선택정렬이란 오름차순, 내림차순 원하는 순으로 정렬한다. 
제자리 정렬(in-place sorting) 중 하나이다.

오름차순으로 정렬한다는 가정하에, 현재 위치의 값보다 더 작은 값을 배열을 쭉 훑으며 찾는다. 
찾았을 경우에 현재 위치의 값과 더 작은 값을 바꾸는 정렬 알고리즘이다.

즉, 0번 방의 값을 1번방부터 끝방까지 돌아서 더 작은 값을 찾아 자리를 바꾼다. 
다음엔 1번 방의 값을 2번방부터 끝방까지 돌아서 더 작은 값을 찾고, 찾았을 경우 두 값을 바꾼다.

0번방 / 10

1번방 / 5

2번방 / 9

3번방 / 14

4번방 / 1

위와 같은 배열이 있다. 0번방 부터 4번방까지 10, 5, 9, 14, 1 순으로 저장되어있다.

오름차순으로 정렬한 결과는 1, 5, 9, 10, 14가 되어야 한다.

선택정렬을 실행하여 정렬하는 과정이다.

1. 0번방의 값 10을 왼손에 들고 4번방까지 돌면서 10보다 작은 값을 찾는다.

2. 1번방의 값 5가 10보다 작아서 오른손에는 5라는 값을 들고 5보다 작은 값을 계속 찾아간다.

3. 2번방, 3번방을 돌았으나 5보다 커서 4번방까지 왔다.

4. 4번방의 값이 1로 내 오른손에 있는 5보다 작기 때문에 오른손에 있는 걸 1로 바꾼다.

5. 4번방에 내 왼손에 있는 10을 4번방에 놓고 다시 내 방인 0번방으로 와 내 방에는 오른손에 있는 1이라는 값을 둔다.

0번방 / 1

1번방 / 5

2번방 / 9

3번방 / 14

4번방 / 10

그럼 이렇게 0번방과 4번방의 값을 서로 교환했으므로 이렇게 된다.

0번방에는 제일 작은 값을 뒀으므로 이젠 1번방부터 시작한다.

1. 1번방의 값 5를 왼손에 들고 4번방까지 돌면서 5보다 작은 값을 찾는다.

2. 2번방, 3번방, 4번방을 다 돌아봤지만 내 왼손의 5보다 작은 값은 없었다.

0번방 / 1

1번방 / 5

2번방 / 9

3번방 / 14

4번방 / 10

이제 2번방부터 시작한다.

1. 2번방의 값 9를 왼손에 들고 4번방까지 돌면서 9보다 작은 값을 찾는다.

2. 3번방, 4번방을 돌아봤지만 내 왼손의 9보다 작은 값은 없었다.

0번방 / 1

1번방 / 5

2번방 / 9

3번방 / 14

4번방 / 10

자, 이제 3번방부터 시작한다.

1. 3번방의 값 14를 왼손에 들고 4번방을 가본다.

2. 4번방의 값 10이 내 왼손의 14보다 작다.

3. 4번방의 값 10을 내 오른손에 들고, 왼손의 14를 4번방에 내려놓는다.

4. 내 방 3번방으로 돌아와 3번방에 오른손의 10을 내려놓는다.

0번방 / 1

1번방 / 5

2번방 / 9

3번방 / 10

4번방 / 14

방을 열심히 돌아다니면서 정렬한 결과 1, 5, 9, 10, 14 (오름차순)으로 정렬이 되었다.

이게 바로 선택정렬 알고리즘이다.

아래는 C#의 List를 이용하여 List에 저장된 10, 5, 7, 13, 2의 값을 오름차순으로 정렬한 결과와 코드이다.

10, 5, 7, 13, 2를 선택정렬(오름차순)을 한 결과 2, 5, 7, 10, 13으로 바뀌었다.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace Selcetion_Sort
{
    //summary
    //List에 저장된 값을 직접 정의한 Method로 선택정렬(Selection_Sort)한다.
    class App
    {
        public App() //생성자
        {
            List<int> list = this.MakeList(); //int형 List를 가리키는 변수 list에 리턴받은 itemCodeList를 저장
            PrintList(list); //정렬되지 않은 list(10, 5, 7, 13, 2)를 출력하는 메서드로 보낸다
            Console.Write("\n");
            list = SelectionSort(list); //정렬하는 메서드에 list를 보내서 정렬한다.
            PrintList(list); //정렬 결과를 출력
            Console.Write("\n");
            Console.ReadKey();
        }
 
 
        public List<int> SelectionSort(List<int> list) //리스트를 정렬하는 메서드
        {
            int indexTemp = 0; //index을 임시로 저장할 temp변수, 리스트의 첫번째 값으로 초기화
            int valueTemp; //값을 임시로 저장할 temp변수
            for (int index = 0; index <= list.Count-2; index++) //0번부터 끝까지 비교 정렬하기 위한 반복문
            {
                valueTemp = list[index];
                for (int count = index+1; count <= list.Count-1; count++) //현재 가지고 있는 값을 다른 값들과 비교하는 반복문
                {
                    if (list[count] < valueTemp) //현재 index칸의 값이 첫번째 칸의 값보다 작으면 temp에 저장
                    {
                        indexTemp = count;
                        valueTemp = list[count];
                    }
                }
                if (indexTemp != 0) //indexTemp에 비교 최소값이 없으면 자리바꿈 실행
                {
                    valueTemp = list[indexTemp];
                    list[indexTemp] = list[index];
                    list[index] = valueTemp;
                }
                indexTemp = 0;
            }
            return list;
        }
 
        public void PrintList(List<int> list) //리스트의 값을 출력하는 메서드
        {
            foreach (int printList in list) //list의 처음부터 끝까지 돌면서 int형 값을 printList에 저장
            {
                Console.Write("{0}, ", printList); //저장된 값 printList를 출력
            }
        }
 
        public List<int> MakeList() //리스트를 생성하고 값을 저장하는 메서드
        {
            List<int> itemCodeList = new List<int>();
            //정수형 List 인스턴스를 생성하고, 그를 가르키는 itemCodeList 변수생성
            itemCodeList.Add(10); //0번 Index의 Value는 10
            itemCodeList.Add(5); //1번 index의 Value는 5
            itemCodeList.Add(7); //2번 index의 Value는 7
            itemCodeList.Add(13); //3번 index의 Value는 13
            itemCodeList.Add(2); //4번 index의 Value는 2
            return itemCodeList;
        }
 
    }
}