[알고리즘 개념] Selection Sort

Selection Sort란?

• 기본 아이디어
  • 정렬 중간 과정에서 데이터가 두 부분으로 나누어집니다.
  • 왼쪽 데이터는 정렬이 된 데이터
  • 오른쪽 데이터는 정렬이 되지 않은 데이터
  • Not stable한 알고리즘이면서 In place 알고리즘입니다.
    • 오른쪽 데이터에서 제일 작은 데이터를 검색하여 선택하고 오른쪽 데이터의 제일 앞 숫자를 그 숫자랑 교환합니다.

• 정렬 과정

Selection Sort 코드

#include <stdio.h>
#include <iostream>

#define MAX_SIZE 1000
using namespace std;
void selectionSort(int a[], int n);
int main()
{
    int numTestCases;
    scanf("%d", &numTestCases);
    for (int i = 0; i < numTestCases; ++i)
    {
        int num;
        int a[MAX_SIZE];
        scanf("%d", &num);
        for (int j = 0; j < num; j++)
            scanf("%d", &a[j]);
        selectionSort(a, num);
        printf("\n");
    }
    return 0; 
}
void swap(int* a, int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp; 
}
/* Selection Sort 함수 */
void selectionSort(int a[], int n)
{
    int countCmpOps = 0; // 비교 연산자 실행 횟수 
    int countSwaps = 0; // swap 함수 실행 횟수
    int i,j;
    // selection sort 알고리즘 구현

    for (i=0;i<n-1;i++)
    {  
        int jmin = i;
        for(j=i+1;j<n;j++){
            countCmpOps ++;
            if(a[j] < a[jmin]){
                jmin = j;
            }
        }
        if(i != jmin){
            swap(&a[jmin],&a[i]);
            countSwaps ++;
        }

    }
    printf("%d %d ", countCmpOps, countSwaps);
}