선택정렬(Selection Sort) 구현

 

선택정렬(Selection sort)

- 제자리 정렬 알고리즘의 하나이다.

- 각 순회마다 제일 앞의 기준 원소를 잡고 다음 원소부터 차례차례로 검사하여 정렬하는 방법이다.

- 시간복잡도가 O(n^2)이지만, 메모리가 제한적인 경우 사용시 성능 상의 이점이 있다.

  ※ 같은 시간복잡도를 가지고 있는 버블정렬보다 선택정렬이 우수하다. (교환 횟수가 작기때문)

 

 

 

원리 (오름차순 기준)

  1. 각 순회마다 제일 앞의 원소를 기준 원소로 잡는다.

  2. 기준 원소의 다음 원소부터 배열 끝까지 돌면서 최소값을 탐색한다. (이 때, 최소값은 기준 원소값보다 작아야한다.)

  3. 최소값이 존재하면 원소의 위치를 바꿔준다.

    ※ 마지막 순회는 정렬할 필요가 없으므로 순회를 돌 필요가 없다.

 

 

 

코드

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MAX 10

void SetArr(int arr[])
{
    for(int i = 0; i < MAX; i++)
    {
        arr[i] = rand() % 100;
    }
}

void PrintArr(int arr[])
{
    for (int i = 0; i < MAX; i++)
    {
        printf("%d\n", arr[i]);
    
    }
}

void SelectionSortAscending(int arr[])
{
    for (int i = 0; i < MAX - 1; i++)
    {
        int min = i;
        for (int j = i + 1; j < MAX; j++)
        {
            if (arr[min] > arr[j])
            {
                min = j;
            }
        }

        if (i != min)
        {
            int tmp = arr[min];
            arr[min] = arr[i];
            arr[i] = tmp;
        }
    }
}

void SelectionSortDescending(int arr[])
{
    for (int i = 0; i < MAX - 1; i++)
    {
        int min = i;
        for (int j = i + 1; j < MAX; j++)
        {
            if (arr[min] < arr[j])
            {
                min = j;
            }
        }

        if (i != min)
        {
            int tmp = arr[min];
            arr[min] = arr[i];
            arr[i] = tmp;
        }
    }
}

void main()
{
    srand(time(NULL));
    int iArr[MAX] = {0};
    
    SetArr(iArr);
    
    SelectionSortAscending(iArr);
    //PrintArr(iArr);
    
    SelectionSortDescending(iArr);
    //PrintArr(iArr);
}