1. 선택정렬(Selection Sort) 정리 및 구현
C#/알고리즘 2019. 3. 29. 09:45선택정렬(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의 값을 오름차순으로 정렬한 결과와 코드이다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 | 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; } } } | cs |
'C# > 알고리즘' 카테고리의 다른 글
| Baek Joon Online Judge (0) | 2019.03.27 |
|---|