[c++] 알고리즘 - 선택정렬

선택정렬 (Selection Sort)

- 배열에서 가장 작은 원소를 찾아 첫 번째 원소와 교환하고 두 번째 작은 원소를 찾아 두 번째 원소와 교환하고.. 이러한 방식으로 전체가 정렬될 때까지 계속함

 

 

특징

- 레코드가 실제로 교환되는 것은 많아야 한번 뿐이므로 작은 키와 매우 큰 레코드를 가지는 화일을 정렬하는데 적합

- 실행 시간은 입력 자료의 순서에 민감하지 않음

- 제자리 정렬

- 현재 값과 가장 작은 값을 교환할 때 현재 값이 어디로 갈지 알 수없으므로 불안정

 

 

 

 

수행과정

 

 

 

 

 

 

성능 특성

- n개의 원소 각각에 대해 n-1 번 비교

- 전체 비교 횟수 n(n-1)/2

- 전체 시간 복잡도 O(n^2)

- 큰 레코드와 작은 키를 가지는 화일의 경우 효율적

 

 

 

 

 

소스 코드

#include <iostream>
#include <time.h>
#include <stdlib.h>

using namespace std;

const int N = 10;

//const int TRUE = 1;
//const int FALSE = 0;

inline void swap(int a[], int i, int j)
{
  int t = a[i]; a[i] = a[j]; a[j] = t;
}

/*
void CheckTime(int a[], int n)
{
  int i, isSrt;
  isSrt = TRUE;
  for (i = 1; i < n; i++) {
    if (a[i] > a[i+1]) isSrt = FALSE;
    if (!isSrt) break;
  }
  if (isSrt) cout << "Sort Complete" << endl;
  else cout << "Sort Error" << endl;
}
*/

void printList(int a[])
{
 int i;
 for (i = 1; i < 10; i++)
   cout << a[i] << ", ";
 cout << a[i] << endl;
}

void SelectionSort(int a[], int N)
{
  int i, j, min;
  for (i = 1; i < N; i++) {
    min = i;
    for (j = i+1; j <= N; j++)
      if (a[j] < a[min]) min = j;
    swap(a, min, i);
 printList(a);
  }
}

int main()
{
//  int i;
  int a[N+1] = {-1, 6, 2, 8, 1, 3, 9, 4, 5, 10, 7};
//  double start_time;

//  srand(time(NULL));
//  for (i = 1; i <= N; i++) a[i] = rand();

//  start_time = clock();
  printList(a);
  SelectionSort(a, N);
//  cout << "Selection Sort Running Time (N = " << N << ") : " << clock() - start_time << endl;
//  CheckTime(a, N);
}