선택정렬 Select Sort

정렬정리

선택정렬은 앞쪽에서부터 차례대로 순서에 맞게 원소를 넣어주는 소팅방법이다.

일단 최소값을찾고 그값에대한 자리를 확정해주는 방법이다. 

구현이쉽고 간단하지만 시간복잡도가 높은게 단점이다.

10만개의 배열을 랜덤하게 생성후 정렬한 결과.

#include<iostream>
#include <time.h>
using namespace std;
#define MAX 100000
 
void select(int *arr, int right);
int arr[MAX];
 
int main(void)
{
    
    for (int i = 0; i < MAX; i++)
    {
        arr[i] = rand();
    }
    double now = clock();
    select(arr, MAX);
    double finish = clock();
 
    for (int i = 0; i < MAX; i++)
        cout << arr[i] << " ";
 
    cout << endl << "선택정렬 " << MAX << "개 소요시간 : " << finish-now << "ms" << endl;
 
    return 0;
}
 
void select(int *arr, int right)
{
    for (int i = 0; i < right; i++)
    {
        int min = i;
        for (int j = i + 1; j < right; j++)
        {
            if (arr[j] < arr[min])
                min = j;
        }
        if (min != i)
        {
            int tmp = arr[i];
            arr[i] = arr[min];
            arr[min] = tmp;
        }
    }
}