선택정렬은 직관적으로 이해하기 쉬운 정렬 방식이다.

 

예를 들어 여기 숫자 카드가 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;
}

정렬 전과 후에 배열을 출력하면 제대로 작동이 된건지 확인 가능하다.

공유하기

facebook twitter kakaoTalk kakaostory naver band