[알고리즘] 선택 정렬

선택정렬 : 가장 작은 것을 선택해서 제일 앞으로 보내는 알고리즘

​

1 10 5 8 7 6 4 3 2 9 를 오름차순으로 정렬하시오

 

1 10 5 8 7 6 4 3 2 9 을 정렬하기 위해서는

​

1 ~ 10 => 10 , 2 ~ 10 => 9 , 3 ~ 10 => 8 .... , 10 ~ 10 => 1

=> 1 + 2 + 3 + 4 + ... + 10 <= 이처럼 일정한 값으로 증가하는 것을 등차 수열이라고 한다.

=> 10 * (10 + 1) / 2 = 55 <= 이 식을 등차수열의 합이라고 한다.

​

※등차 수열 : 1 ~ 10처럼 특정한 값으로 더해진 수들을 말한다.

등차 수열의 합 : N(첫번째 값) + M(마지막 값) / 2 * 더한 항

ex) 1+ 3 + 5 + 7 => (1 + 7) / 2 * 4

​

1 ~ 10 까지 정렬하기 위해서 최소한 55번의 비교 연산을 해야한다.

​

즉 위 알고리즘의 수행시간은

=> N * (N + 1) / 2 로 나타낼 수 있다.

컴퓨터에서는 "/ 2" 나 "+ 1" 는 N의 값이 클 경우 의미가 없기 때문에 무시한다

​

그렇기 때문에 결과적으로 N * N의 시간을 가지는 것이다.

​

이를 시간 복잡도로 표기하면

O(N * N) => O(N ^ 2)이다. <- O는 특정한 알고리즘의 수행시간을 간략하게 표기한 것이다.

​

※ 시간복잡도란?

문제를 해결하기 위해서 걸리는 시간을 말한다.

선택 정렬의 시간 복잡도

O(N ^ 2)

​

다시말해 데이터의 개수가 10.000개라면 대략 일 억 번 정도의 계산을 한다고 가정을 해야한다.

​

이는 다른 정렬 알고리즘과 비교하였을 경우 비효율적인 알고리즘이다.

​

선택 정렬의 비교 횟수와 이동 횟수

비교 횟수는 O(N ^ 2)이고

이동 횟수는 바깥 for문에 이동이 있기때문에

tmp = array[i]; array[i] = array[index]; array[index] = tmp;

1번에 3번씩 밖에 수행하지 않으므로 3(n-1)이다

그러므로 이동 횟수는 O(N)이다.