선택 정렬이란 무엇일까여?
예를 들어 배열에다가
{6,5,7,4,3,9,8,1,2,10}
이렇게 숫자가 들어있다고 생각합시다
오름차순으로 정렬이라고 생각하시면 됩니다
가장 앞에 있는 요소 6을 제외하고 그 뒤에 있는 9개의 요소들을 비교해가면서 가장 작은 요소가 1입니다
그럼 6 이랑 1의 자리를 바꿉니다
그리고 2번째 요소인 5를 제외하고 나머지 8개의 데이터들의 비교합니다
그러면 가장 작은 요소가 2입니다
2와 5의 자리를 바꿉니다
이런 식으로 반복하면서
수를 비교해가면서 자리를 바꾸는 것이 선택 정렬 알고리즘입니다
버블 알고리즘, 퀵 알고리즘 등등도 있지만
알고리즘을 공부할 때는 선택 정렬을 먼저 접해 보는 것이 좋다고 말합니다
우선 간단하게 코드를 적어보겠습니다
#include <stdio.h>
int main() {
return 0;
}이제 두 요소를 바꾸어야 하니 그 두 요소를 담을 두 변수를 a, b라고 정하겠습니다
그리고 비교를 해서 가장 작은 요소를 찾아야 하니 min이라는 변수를 만들고
두 요소들의 위치를 바꾸어야 하니 index라고 보고 이해하기 쉽게 짓겠습니다
그리고 제외하는 요소를 담을 temp라는 변수를 선언하겠습니다
그리고 배열에다가 요소들을 넣겠습니다
#include <stdio.h>
int main()
{
int a,b,min,index,temp;
int array[10] = {10,9,8,7,6,5,4,3,2,1};
return 0;
}
그리고 이제 반복문을 돌리겠습니다
#include <stdio.h>
int main()
{
int a,b,min,index,temp;
int array[10] = {10,9,8,7,6,5,4,3,2,1};
for (a = 0; a < 10; a++) {
min = 11;
for (b = a; b< 10; b++) {
}
return 0;
}min을 11로 선언하여 배열에서 가장 큰 요소가 10이기 때문에 비교를 할 때 10이 나오면 정상적으로 정렬이 되지 않기 때문에 10보다 더 높은 11로 정했습니다
그리고 이제 제일 앞에꺼를 제외하고 뒤에 9개의 요소를 비교해서 가장 작은 요소를 min 에다가 넣겠습니다
그리고 그 작은 자리의 인덱스 번호를 index변수에다가 넣겠습니다
#include <stdio.h>
int main()
{
int a,b,min,index,temp;
int array[10] = {10,9,8,7,6,5,4,3,2,1};
for (a = 0; a < 10; a++) {
min = 11;
for (b = a; b < 10; b++) {
if (min > array[b]) {
min = array[b];
index = b;
}
}
}
return 0;
}그리고 이제 자리를 바꿀 코드를 적어보겠습니다
#include <stdio.h>
int main()
{
int a,b,min,index,temp;
int array[10] = {10,9,8,7,6,5,4,3,2,1};
for (a = 0; a < 10; a++) {
min = 11;
for (b = a; b < 10; b++) {
if (min > array[b]) {
min = array[b];
index = b;
}
}
temp = array[a];
array[a] = array[index];
array[index] = temp;
}
return 0;
}배열의 가장 앞에 요소를 temp 변수에다가 넣습니다
그리고 비교해서 가장 작았던 요소의 자리(인덱스)를 가장 앞에 자리에다가 넣고
원래 가장 앞이었던 자리의 요소를 원래 그 작은 자리에다가 넣습니다
그럼 서로 자리가 바뀌었습니다
이제 출력을 해보겠습니다
#include <stdio.h>
int main()
{
int a,b,min,index,temp;
int array[10] = {10,9,8,7,6,5,4,3,2,1};
for (a = 0; a < 10; a++) {
min = 11;
for (b = a; b < 10; b++) {
if (min > array[b]) {
min = array[b];
index = b;
}
}
temp = array[a];
array[a] = array[index];
array[index] = temp;
}
for (a = 0;a < 10; a++) {
printf("%d",array[a]);
}
return 0;
}array [i]를 10번 출력하여 가장 작은 값과 앞에 갚을 비교 해서 자리를 계속 바꾸도로 해서 출력합니다
그러면 결과가 1,2,3,4,5,6,7,8,9,10 이렇게 오름차순으로 정렬이 됩니다
코드가 이해가 되지 않더라고
계속 계속 코드를 보고 따지면서 개념을 먼저 이해하시는 거를 추천드립니다
외운다고 해도 개념을 알아야 버블 정렬, 퀵 정렬 등등도 이해하는데 도움이 될 겁니다
감사합니다