2. 정렬 알고리즘이 개요와 선택 정렬 정리

 

https://blog.naver.com/ndb796/221226800661 

2. 정렬의 개요와 선택 정렬(Selection Sort)

안경잡이 개발자 [알고리즘] 강의 기반으로 정리하였습니다.

---

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

1 10 5 8 7 6 4 3 2 9 

---

[ 문제 풀이 ]

i, j는 배열의 있는 원소들을 반복적으로 탐색하기 위해서 사용

min은 최소값을 의미, 가장 반복적으로 사용하는 것을 선택해야한다. 

index 가장 작은 원소가 존재하는 위치가 index

temp 특정한 두숫자는 서로 바꾸기 위해서 사용된다. 

 

10개의 원소를 탐색하기 위해서 10번을 반복한다는 의미로 아래와 같은 코드를 작성한다. 

int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9 };
for(i = 0; i < 10; i++) {

}

맨처음에 min 값에는 아주 큰 값을 넣어준다. 예를 들면 그대로 9999

min = 9999;

숫자가 만약에 9999보다 큰 숫자가 있다면 이런 식으로 하면 안 되겠죠? 모든 원소들보다 큰 숫자 아무 숫자나

무작위로 넣어줄꺼에요.

min 값은 항상 최소값을 선택해야되기때문에 가장 큰 값을 넣어주죠 

 

자 이제 j 는 i부터 시작해서 10 까지 반복을 하는데, 이제 여기에서 최소값을 골라주는 거에요. 

현재 탐색하고 있는 그 원소가 현재 최저값보다 더 작다면 -> 최저값을 현재 탐색하고 있는 그 원소로 바꿔준다. 

for(j = i; j < 10; j ++) {
if(min < array[j]) {
	min = array[j];
    index = j;
    }
 }

이코드는 배열중에 가장 작은 값을 선택한다는 코드이다. 이제 그 가장 작은 값을 맨 앞으로 보내는 로직을 보자. 

일단 temp라는 변수에 가장 앞에 있는 값을 넣어주고 array[i];

가장 앞에 있는 원소로 최소값을 넣어준뒤에 array[index];

다시 최소값이 있는 위치에 temp에 들어있는 값을 넣어준다. 아래와 같은 방식은 스왑핑한다. 

두개의 있는 원소를 바꿔준다는 의미이다. 이 3줄은 앞에 있는 값과 최소값을 바꿔준다는 의미이다. 

temp = array[i];
array[i] = array[index];
array[index]  = temp;

 그니깐 처음에

1 10 5 8 7 6 4 3 2 9 를 살펴보고 for문 돌고

5 8 7 6 4 3 2 9 범위 살펴보고 for문 돌고

7 6 4 3 2 9 범위 살펴보고 for문 돌고

6 4 3 2 9 범위 살펴보고 for문 돌고 이런식으로 가장 작은 것을 선택해서 앞으로 보내준다. 이것을 반복하는 소스코드이다. 

이제 정렬이 완성된 코드는 아래와 같이 출력해준다. 

for(i = 0; i < 10; i++) {

printf("%d ", array[i]);

}

 

선택 정렬의 알고리즘의 단점 : 시간이 많이 걸린다.  N * (N + 1) / 2

=> O(N * N) 특정한 알고리즘의 수행 시간을 시간을 가장 간략하게 표현하는 것이 바로 이 빅오 O 표기법이다. 

특정 알고리즘의 연산횟수를 간략하게 표현했다. O 빅오 표기법. 

선택정렬의 시간 복잡도는 O(N * N )

효율적인지는 고민해볼것!

 

결과물

선택정렬 끝