실력키우기 선택정렬(C++)

1146 : 선택정렬

제한시간: 1Sec    메모리제한: 32mb
해결횟수: 875회    시도횟수: 2563회   

선택 정렬(selection sort)이란 내부정렬 알고리즘의 하나로 다음 순서대로 실행하여 정렬을 한다.

1. 주어진 수열 중에 최소값을 찾는다.
2. 찾은 최소값을 맨 앞의 값과 자리를 바꾼다.
3. 맨 앞의 값을 뺀 나머지 수열을 같은 방법으로 전체 개수-1번 반복 실행한다.

n개의 주어진 수열을 위와 같은 방법으로 정렬한다.

수열이 주어지면 선택정렬의 과정을 한 단계씩 출력한다.

 

첫줄에 수열의 길이 N(4≤N≤100)이 주어진다.
두 번째 줄에 N개의 0이상 100이하의 정수가 주어진다.

처음 상태를 제외하고 정렬과정의 각 단계별 결과를 "출력형식"과 같이 출력한다.

[Copy] 5 6 4 8 3 1

[Copy] 1 4 8 3 6 1 3 8 4 6 1 3 4 8 6 1 3 4 6 8

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

/**************************************************************     Problem: 1146     User: a132034     Language: C++     Result: Success     Time:2 ms     Memory:1740 kb ****************************************************************/     #include    <iostream> #include    <algorithm> using namespace std;   int main() {     int n;     int* arr;     cin >> n;       arr = new int[n];     for (int i = 0; i < n; ++i)         cin >> arr[i];       int *min;     int index;     for (int i = 0; i < n-1; ++i)     {         min = min_element(arr + i, arr + n);         index = find(arr + i, arr + n, *min) - arr;           int tmp = *min;         arr[index] = arr[i];         arr[i] = tmp;           for (int z = 0; z < n; ++z)             cout << arr[z] << " ";         cout << endl;       }       return 0; }

선택정렬

1. 주어진 수열 중 최소값을 찾는다( stl -> min_element함수로 찾음)

2. 맨앞의 값과 자리를 바꾼다. (stl -> find함수로 min값의 위치를 찾아 i번째 위치와 바꾸어 줌)

3. n-1번 반복한다. 

크게 어려운 것은 없었으나 빠른 구현을 위해

stl의 min_element, find를 사용해 보았다. 

주의할 점은 보통 배열의 시작과 끝을

예를들어 n[10]의 배열이 있을 때, 시작과 끝이 n[0] -> n[9] 이나 

종료주소는 n[10] 또는 n + 10으로 한다.