첫 번째 알고리즘은 정렬에 대한 알고리즘입니다.
쉽게 예를들어 설명한다면, 만약 사람에게 1/7/3/5/8/6/9/2/4을 정렬(오름차순)하라 한다면 사람들은 아주 쉽게 1/2/3/4/5/6/7/8/9가 답인것을 알고있을것입니다. 하지만, 멍청한 컴퓨터는 계산밖에 모르는 바보이기에 우리가 어떤식으로 정렬하라는 그 과정을 구체적으로 명시해주어야 합니다.
그럼 어떤 방법이 있을까요?
입력하는 숫자 혹은 입력되어있는 숫자를 대소비교하여 작은 숫자를 앞으로 보내주면 됩니다. 이를 '선택정렬' 알고리즘이라 하며 가장 기초적인 방법이라고 할 수 있습니다. 다시말해 가장 작은숫자를 선택하여 그 숫자를 맨 앞으로 보내면 됩니다!
다음은 정렬을 하는 코드입니다.
#include <iostream> using namespace std; int main() { int index, temp, min; int array[9] = { 1, 7, 3, 5, 8, 6, 9, 2, 4 }; for (int i = 0; i < 9; i++) { min = 10; for (int j = i; j < 9; j++) { if (min > array[j]) { min = array[j]; index = j; } } temp = array[i]; array[i] = array[index]; array[index] = temp; // 위 3개의 소스코드를 합쳐 스와핑한다고 말함 } for (int i = 0; i < 9; i++) { cout << array[i] << " "; } return 0; }
💡 이제 코드를 하나하나 뜯어 봅시다!
일단 index, temp, min이라는 세개의 변수를 선언하였고, array에 1부터 9까지 숫자에 무작위 순서로 숫자들을 배치하였습니다. 여기까지는 문제에 대한 조건을 코드로 작성한거라 할 수 있습니다.
이후 for문이 나오는데 처음나오는 i for문에서 비교를 위한 min값을 10으로 초기화 해줍니다. 근데 왜 첫번째 i for문에서 min을 10으로 초기화 해줄까요? min의 역할은 0번째 index(1)부터 마지막 index(4)까지의 요소 중 가장 작은값을 찾기 위해 사용됩니다! 또한, i for문 밖에서 min을 10으로 초기화 하게 된다면 if문을 타지 못하기 때문에 첫번째 i for문 안에서 초기화 해주는것이 올바른 방법입니다!
다음으로 첫 번째 j for문을 보면 j는 i로 초기화되어 for문을 돌게 됩니다. 첫번째로 말한 10보다 array[j]는 모두 작으니 if문은 항상 true조건이 되고 min에 array[j]를 넣어주면 됩니다! 또한 index에는 j값을 넣어주는 작업을 9(8,7,6...1)번 반복해주고 j for문을 빠져나오게 됩니다.
이후 temp를 array[i]로 초기화 한 이후, array[i]에는
array[index](array[j])로 초기화되며 다시 array[index]는 temp로 초기화 됩니다. 이 과정을 왜 해주냐 이런 생각이 들 수 있는데 이는 주석에 나와있듯 세번의 초기화 과정을 통해 3개의 값을 스와핑 할 수 있게됩니다! 다시 정리하면 다음과 같습니다.
- temp = array[i];: 현재 위치(i)의 값을 temp 변수에 임시로 저장합니다. 이렇게 하면 현재 위치의 값을 나중에 다시 사용할 수 있습니다.
- array[i] = array[index];: 현재 위치(i)에 최솟값을 가진 요소(array[index])를 대입합니다. 이렇게 하면 최솟값이 현재 위치로 이동됩니다.
- array[index] = temp;: 최솟값을 가진 요소(array[index])에 이전에 임시로 저장한 값을 대입합니다. 이렇게 하면 최솟값이 현재 위치로 이동하면서 현재 위치의 값은 최솟값의 위치로 이동합니다.
위의 과정들을 통해 선택정렬 알고리즘이 동작하여 숫자를 조건에 맞게 배열시킬 수 있게됩니다! 근데 선택정렬의 시간복잡도는 O(N^2)의 형태이므로 굉장히 비효율적인 알고리즘이라 할 수 있습니다... 맥빠지지만,,, 그렇습니다
