컴퓨터 알고리즘 초급 #2 ( 선택정렬 in c )

 

정렬 문제 ( 오름차순 내림차순 )

 

입력 - n개의 숫자들의 배열이다.

출력 - 입력된 숫자의 배열이 크기순을 조건으로 만족하도록 나열한 결과

 

 

선택정렬 알고리즘

 

선택정렬은 무엇인가? - 선택해서 정렬하는 알고리즘이다.

 

선택을 할때 무엇을 선택하는지가 중요한 핵심이 된다.

 

1. 최소값 선택 정렬 (결과 : 오름차순)

2. 최대값 선택 정렬 (결과 : 내림차순)

 

 

최소값 선택 정렬의 알고리즘

 

1. 정렬되지 않는 숫자 중 가장 작은 숫자 선택 ( 최소값 )

2. 선택한 숫자를 정렬되지 않은 숫자들 중 첫 번째 숫자와 자리를 바꾸면 최소값이 가장 앞으로감

3. 첫번째를 제외하고 그 뒤에서부터 정렬되지 않은 숫자들 중 가장 작은 숫자 선택, 가장 앞 +1 로 보냄

 

4. 반복

 

ex) 5 , 4 , 2 , 1, 3

 

첫 번째 최소값 맨 앞자리로 ex) 1 , 5 , 4 , 2, 3

 

두번째 최소값 맨 앞 +1로 ex) 1, 2, 5, 4, 3

 

세번째 최소값 맨 앞 +2로 ex) 1, 2, 3, 5, 4

네번째 최소값 맨 앞 +3로 ex) 1, 2, 3, 4, 5

 

5개의 숫자를 4번의 실행으로 정렬 완료

 

 

정확성 증명 : 수학적 귀납법을 이용하여 , i번째 선택한 숫자가 i번째로 작은 숫자인지를 증명하면 된다.

 

즉 3번째 최소값을 선택한다면, 3번째로 작은 숫자라는것을 증명한다.

 

3번째 최소값은 3번째 자리에 위치하면 된다.

 

성능 : 5자리일때 처음엔 4 개와 비교, 두번째엔 첫자리를 제외한 3개와 비교, 세번째엔 2개와 비교, 네번째엔 1개와 비교, 다섯번째엔 1개와 비교

 

즉 4+3+2+1 = 10

n개가 있을때 n-1, n-2 ,n-3 ... n-n 이 될때까지

1부터 n-1까지 합한 수

n*(n-1)/2

즉 n^2-n/2

여기서 n^2이 최고차항이므로 빅오표기법으로는 O(n^2) 이다.

 

이동도 +1씩 4번하지만, n^2가 최고차항이므로 의미를 두지 않음  1+1+1+1 = 4  

 

최선이든 최악이든 같은 연산을 하기 때문에 항상 빅오 O( n^2 )만큼의 연산을 한다.

 

아래는 c언어에서 사용할 수 있는 선택정렬 코드이다.

 

#include<stdio.h>
//Prosto
int main(void) {
 int data[10] = {10, 6, 7, 9, 3, 4, 2, 1, 5, 8};
 int temp;
 //랜덤한 위치라고 생각.
 printf("정렬 전 순서\n");  //정렬하기 전 상태 출력.
 for (int i = 0; i < 10; i++) {
  printf("%d ", data[i]);
 }
 printf("\n");

 //아래의 2중 for문이 선택 정렬 핵심.
 for (int i = 0; i < 9; i++) {  //10-1까지 마지막 대상은 비교할 필요가 없으니.
  for (int j = i + 1; j < 10; j++) {  //선정 위치 +1부터 마지막까지 비교.
   if (data[i] > data[j]) {  //오름차순이니 작은지 확인.
    temp = data[i];//swap.
    data[i] = data[j];
    data[j] = temp;
   }
  }
 }

 

 printf("정렬 후 순서\n");  //정렬한 후 상태 출력.
 for (int i = 0; i < 10; i++) {
  printf("%d ", data[i]);
 }
 printf("\n");
 return 0;

출처: https://prosto.tistory.com/159 [Prosto]