1-1 [C]선택정렬(Selection Sort)

1) 선택정렬이란?

수열 중에서 최솟값을 검색해서 왼쪽 끝에 있는 숫자와 교체하는 작업 반복

1. 수열을 선형 탐색해서 최솟값을 찾는다-> min : 1

2. min(1)과 가장 왼쪽의 5를 교체하고 1은 정렬이 끝난 것으로 간주한다.

3. 선형 탐색으로 최솟값을 찾았지만 왼쪽 끝에 있기에 다음 단계로 넘어간다.

4. 같은 작업을 반복하다보면 정렬 완료

 

2) 선택정렬의 시간복잡도

선택 정렬은 선형 탐색을 위해 1라운드에서 n-1, 2라운드에서 n-2, ... , n-1라운드에서 1회 비교를 한다.

따라서 비교 횟수는 (n-1) + (n-2) + ... + 1 ≈  n^/2        ps. 버블 정렬과 같다

 

또한, 숫자 교체는 각 라운드에서 최대 1회이며, 입력 데이터가 작은 순으로 나열되어 있다면 교체는 발생하지 않는다.

따라서 선택 정렬의 계산 시간은 O(n^2)이다.

 

3) 선택정렬 구현

#include <stdio.h>

int main(void){
  int data[6] = {5, 2, 4, 6, 1, 3};
  int temp;
  printf("Before sorting :\n");
  for(int i =0; i<6;i++){
    printf("%d",data[i]);
  }
  printf("\n");
  for(int i=0; i<5;i++){ //비교대상이 되는 기준원소
      for(int j=i+1;j<6;j++){ //기준원소에서 오른쪽 옆으로 가면서 비교
          if(data[i]>data[j]){ //오름차순으로 비교
              temp=data[i];
              data[i]=data[j];
              data[j]=temp; //왼쪽에 더 작은수 저장
          }
      }
  }
  printf("After sorting :\n");
  for(int i=0; i<6;i++){
      printf("%d",data[i]);
  }
  printf("\n");
  return 0;
  }

결과화면

Before sorting :
524613
After sorting :
123456