선택 정렬(Selection Sort)

선택 정렬(Selection-Sort)

- 남은 배열의 원소들 중 최소 값을 찾아 현재 포지션(맨 앞)에 위치 시키는 방식
-  O(n2)의 복잡도를 가진다.

 

 

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

#define MAX  10 // size of array

void display_elements( int *, int);
void selection_sort( int *, int);

int main( void)
{
 int arry[MAX]  = { 0,};
 int count   = 0;
 int size   = 0;

 srand( time(NULL)); // used to init random

 size  = sizeof(arry)/4;

 // init elements of array with random numbers
 for( count = 0 ; count < size ; count ++)
 {
  arry[count]  = rand()%(MAX*10);
 }

 // display elements of array
 printf("Before sorting : ");
 display_elements( arry, size);

 // call selection-Sort
 selection_sort( arry, size);

 // output result
 printf("\n After sorting : ");
 display_elements( arry, size);

 return 0;
}

void display_elements( int *ar, int s)
{
 int count  = 0;

 for( count = 0 ; count < s ; count ++)
 {
  printf("%4d", ar[count]);
 }
}

void selection_sort( int *ar, int s)
{
 int min  = 0;
 int i, j, temp;

 for( i = 0 ; i < s ; i ++)
 {
   min = i; // set index of a minimum number
   
   // find a minimum number in the array
   for( j = i + 1 ; j < s ; j ++)
   {
    // if find the number, update the index
    if( ar[j] < ar[min])
    {
     min  = j;
    }
   }

   // swap elements
   temp = ar[min];
   ar[min] = ar[i];
   ar[i] = temp;
 }
}