정렬의 개요와 선택정렬

정렬의 개요와 선택정렬

먼저 비효율적인 정렬 알고리즘을 구현해보자. 뒤에서 효율적인 알고리즘과 비교하면서 효율적인 알고리즘을 작성해야 하는 이유에 대해 알 수 있다.

 

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요.

1 10 5 8 7 6 4 3 2 9

---

 

#include <stdio.h>

//선택정렬 
//선택정렬은 많은 시간이 소비된다. 
// 1 2 3 4 5 6 7 8 9 10
// 10 + 9 + 8 + .. + 1  -> 등차수열 
// -> 10 * (10 + 1) / 2 = 55 -> 10 + 9 + 8 + .. + 1을 더한 값. 
// 최소 55번의 비교연산을 해야한다. 
// N * (N + 1) / 2 -> 컴퓨터에서는 N값이 굉장히 크다는 가정하에 2로 나누거나 1을 더한값이
//의미가 없기 때문에 생략한다. 
// N * N -> N * N의 수행시간을 가지고 있다. 
// O(N * N) -> 빅오표기법 -> 특정 알고리즘의 수행시간을 간략하게 표기하는 표기법 
//선택 정렬의 시간 복잡도는 O(N^2)이다. 
//예를 들어 데이터 개수가 10000개라면 일억번 정도 계산을 한다고 가정을 하겠다는 의미이다. 
//실제로 프로그램에서는 데이터의 개수가 만개 십만개 넘어가는 경우가 많은데 그러한 상황에서
//선택정렬을 사용하는게 맞는지 생각해볼 필요가 있다.
//선택정렬은 다른 알고리즘에 비해 비효율적인 알고리즘이다.
//선택정렬은 데이터의 개수가 많아지면 많아질수록 많은 연산이 필요하다. 
int main(void) { 
    //i와 j는배열에 있는 요소를 반복적으로 탐색하기 위해 사용됨.
//min은최소값을저장하기 위해 사용됨.
//index는 가장 작은 값이 존재하는 요소의 index값.
//temp는 특정한 2개의 숫자를 바꾸기 위해 사용됨. 
int i, j, min, index, temp;
int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
//array 배열을 순차적으로 돈다. 
for(i = 0; i < 10; i++){
//array에 있는 숫자들보다 커야 한다. 
min = 9999;
//i번째에서 부터 최소값을 찾는다. 
for(j = i; j < 10; j++){ 
if(min > array[j]){
//최소값을 min에 넣어준다. 
min = array[j];
//최소값이 위치값을 index에 넣는다. 
index = j;
}
} 
//array 배열을 0~9 -> 1~9 -> 2~9 ... 9~9 까지 돌면서
//0~9를 돌때는 0번값과 0~9까지 최소값을 서로 바꾼다.
//1~9를 돌때는 1번값과 1~9까지 최소값을 서로 바꾼다.
//...   
//이를 스와핑을 한다고 한다. 2개의 원소값을 바꾼다. 

//임시변수인 temp에 최소값을 넣는다. 
temp = array[i]; 
//i번째에 요소에 최소값(array[index])을 넣는다. 
array[i] = array[index];
//최소값(temp)을 array[index]에 넣는다. 
array[index] = temp;
}
//정렬된 배열(array)을 출력한다. 
for(i = 0; i < 10; i++){
printf("%d ", array[i]);
} 
return 0;
}