[알고리즘/자료구조] 선택 정렬 (Selection Sort)

선택 정렬 (Selection Sort)

선택 정렬(selection sort)은 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.

1. 주어진 리스트 중에 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 Θ(n²) 만큼의 시간이 걸린다.

선택 정렬은 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있습니다.

소스

/*
/*    
/*    khsh5592@naver.com
/*    has3ong.tistory.com
/*    
/*    2018 - 11 - 16
/*
/*
 
#include <iostream>
#include <stdio.h>
#include <conio.h>
 
using namespace std;
 
int Data[10] = {9, 5, 12, 23, 4, 1, 18, 6, 3, 11};
 
void main()
{
    int length = sizeof(Data) / sizeof(Data[0]);
    int Min, temp;
    for(int i = 0; i<length; i++)
    {
        Min = i;
        for(int j = i+1; j<length; j++)
        {
 
            if(Data[j] < Data[Min])
            {
                Min = j;
            }
        }
        temp = Data[Min];
        Data[Min] = Data[i];
        Data[i] = temp;
 
        cout << " Data Array is [ " ;
        for (int i = 0; i < length; i++)
        {
            cout << Data[i] << " ";
        }
        cout << "] " << endl;
 
    }
    getch();
}

결과화면

출처

위키피디아

https://en.wikipedia.org/wiki/Insertion_sort