Selection Sort(선택 정렬)

Selection Sort(선택 정렬)

- n개의 원소들 중에서 첫 번째 값을 키로 하여 남은 데이터 중에서 최소 값을 선택하여 비교한 후, 선택한 값이 키 값보다 작으면 서로 교환, 그렇지 않으면 다음 값을 키로 하여 n-1만큼 반복 수행하는 정렬이다.

---

ex) n=5, 8 3 4 9 7

초기   : 8 3 4 9 7
1단계 : (3)(8 4 9 7)
2단계 : (3 4)(8 9 7)
3단계 : (3 4 7)(9 8)
4단계 : (3 4 7 8 9)

---

/* selection.cpp */

#include <iostream>

using namespace std;

void swap(int *, int *);

int main()

{

    int n, min;

        int arr[100];

        cin >> n;

        for(int i=0; i<n; i++)

               cin >> arr[i];

    for(int i=0;i<n-1;i++){                                                       

        min=i;       // 최소값의 인덱스 설정                

        for(int j=min+1;j<n;j++){       

            if(arr[min] > arr[j]) // 현재 최소값이 j번째 원소보다 클 경우        

                min=j;            // 현재 최소값의 인덱스 변경

        }                                     

        if(min != i)                    

            swap(&arr[i],&arr[min]);     // swap 함수 호출(call by reference)    

    }                                   

        for(int i=0; i<n; i++)

               cout << arr[i] << "\t";

        cout << endl;

    return 0;                                      

}

void swap(int *a, int *b)

{

        int temp;

        temp = *a;

        *a = *b;

        *b = temp;

}