C언어 | 선택 정렬 (selection sort) | 파이썬 선택정렬
선택정렬은 직관적으로 이해하기 쉬운 정렬 방식이다.
예를 들어 여기 숫자 카드가 5장 있다.
[2, 1, 5, 3, 4]
오름차순으로 어떻게 정렬하는가? 누구나 알 수 있다.
[2, 1, 5, 3, 4] 카드에서 작은 숫자 순으로 뽑아서 오른쪽에 놓는다.
두번째, 첫번째, 네번째, 다섯번째, 세번째 순으로 뽑아서 나열한다.
[1, 2, 3, 4, 5] 가 될 것은 의심의 여지가 없다.
뽑은 카드의 순서를 표시하면
CARD[2]
CARD[1]
CARD[4]
CARD[5]
CARD[3]
이 나온다. 이제 컴퓨터에서 어떤 코드를 구현하는가만 남아있다. 사람에겐 달리 생각이 필요없는 일도 컴퓨터에게 있어서는 구체적인 명령어와 지시가 필요하다. 온라인의 올라와있는 기본 자료들은 서로 약간의 차이가 있는데 다들 비슷하다. 코드를 쉽게 구할 수 있다는 것은 좋은 일이다. 인터넷이 제대로 되있지 않았던 시대와 비교하는 건 시대착오일지 모르지만 지금의 프로그래밍의 대가들도 초창기에 소스 코드를 이렇게 쉽게 구하지는 못했다.
시대착오는 착각이겠으나 역사를 돌아보는 것은 의미가 있다. IT환경이 빨리 변한 것 처럼 앞으로도 소스코드를 활용하는 방식이 바뀌지 않는다는 보장은 없다. 개인적으로는 VR 기기에 소스코드를 다운로드 받아서 타이핑 조차 필요없이 음성인식 같이 AI 도우미의 도움을 방식으로 실행시키는 등 기존의 생각을 뒤엎는 기술을 기대하고 있다.
선택 정렬 같은 것은 배울 필요도 없이 AI비서가 필요할 때 그냥 쉽게 이해시켜주거나, 아니면 자기가 알아서 관리해줬으면 좋겠다는 생각이다.
*먼저 파이썬의 코드다. 정렬이나 검색 코드는 C언어로 작성해야 성능이 좋지만 파이썬으로 알고리즘을 구현하는게 조금 더 쉬울 수 있다. 학습 차원이나 간단한 기능을 처리할 때 쓸 수 있다.
- 먼저 랜덤 함수로 10개의 중복없는 난수를 생성하고 정렬한다. 난수를 생성해서 테스트 하면 데이터 오류 방지에 좋다.
- 바깥 for 문을 사용하여 최소값의 인덱스를 갱신한다. 내부 for 문에서는 최소값의 인덱스가 확정된다.
- 내부 for문이 끝나면 값을 갱신하고(SWAP) 바깥 for문이 새롭게 시작할 때 최소값이 정해진 그 다음 인덱스 부터 for 루프를 반복한다. i 가 0에서 시작해서 count - 1 까지 가면 i는 count-1에 j는 count에 조건식을 검사하고 끝난다.
import random
list1 = []
while len(list1) != 10:
newNumber = random.randint(1, 10)
if newNumber not in list1:
list1.append(newNumber)
print("*Before selection sort: ")
print(list1)
count = len(list1)
for i in range(0, count-1):
minIndex = i
for j in range(i+1, count):
if list1[j] < list1[minIndex]:
minIndex = j
temp = list1[i]
list1[i] = list1[minIndex]
list1[minIndex] = temp
print("*After selection sort: ")
print(list1)
- 출력이 제대로 나오면 성공이다.
* 다음은 C언어 코드다. 파이썬과 문법은 다르지만 정렬하는 for문의 내용은 같다.
- 숫자 10개를 정렬한다면 아래와 같은 루프를 돌 것이다. 루프를 많이 돌아서 대용량 데이터의 정렬에는 적합하지 않다. (시간 복잡도가 높다고 한다) 하지만 직관적 방식이라 이해하기 쉽고 구현하기 쉽다는 것이 학습적으로 장점을 가진다.
| i | j | loop 횟수 |
| 0 | 1 ~ 9 | 9 |
| 1 | 2 ~ 9 | 8 |
| 2 | 3 ~ 9 | 7 |
| 3 | 4 ~ 9 | 6 |
| 4 | 5 ~ 9 | 5 |
| 5 | 6 ~ 9 | 4 |
| 6 | 7 ~ 9 | 3 |
| 7 | 8 ~ 9 | 2 |
| 8 | 9 | 1 |
* 전체 소스 코드 - 핵심은 selectionSort 함수다. 다른 함수들은 편의상 만들어 놓았다.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define Line printf("\n-------------------------------------------------\n\n");
void selectionSort(int arr[], int count);
void showArray(int arr[], int count);
void swap (int *x, int *y);
int getRandomInt(int from, int to);
int* getArray(int count);
int main(int argc, char const *argv[])
{
srand(time(NULL));
/*--- 선택정렬 ---*/
int array[] = {15, 23, 14, 79, 25, 35, 47};
int count = sizeof(array)/sizeof(int);
showArray(array, count);
selectionSort(array, count);
showArray(array, count);
Line;
/* ---- 랜덤생성 후 선택정렬 ---*/
count = 10;
int* array1 = getArray(count);
showArray(array1, count);
selectionSort(array1, count);
showArray(array1, count);
return 0;
}
void selectionSort(int arr[], int count)
{
for (int i = 0; i < count-1; i++)
{
int min_idx = i;
for (int j =i + 1; j < count; j++)
{
if(arr[j] < arr[min_idx]){
min_idx = j;
}
}
swap(&arr[i], &arr[min_idx]);
}
}
void showArray(int arr[], int count)
{
printf("[Show Array]\n");
printf("[");
for (int i = 0; i < count; i++)
{
printf("%d, ", arr[i]);
}
printf("]\n");
}
void swap(int *x, int *y)
{
int temp = *x;
*x = *y;
*y = temp;
}
int getRandomInt(int from, int to)
{
int random = rand() % (to-from+1) + from;
return random;
}
int* getArray(int count)
{
int *array = calloc(count, sizeof(int));
for (int i = 0; i < count; i++)
{
array[i] = getRandomInt(1,100);
}
return array;
}
정렬 전과 후에 배열을 출력하면 제대로 작동이 된건지 확인 가능하다.
