[알고리즘 c++] 선택정렬
선택 정렬 알고리즘이라고 하면 가장 작은 수를 가져와 맨 앞으로 가져오고, 가져온 수의 자리에 맨 앞에 있던 숫자를 스와핑하는 방식으로 배열의 수만큼 반복하는 식으로 오름차순, 내림차순으로 정렬하는 알고리즘 방식입니다.
#include <stdio.h>
int main(void) {
int i, j, min, index, temp;
int array[10] = {10,1,5,8,7,6,4,3,2,9};
for(i=0; i<10; i++){
min = 9999;
for(j=i; j< 10; j++){
if(min > array[j]){
min= array[j];
index = j;
}
}
temp = array[i];
array[i] = array[index];
array[index] = temp;
}
for(i = 0; i< 10;i++){
printf("%d ", array[i]);
}
return 0;
}
위 예제처럼 길이가 10인 배열을 선택 정렬 알고리즘으로 정렬할 경우
등차수열로 표현하면 아래와 같이
10 + 9 + 8 + ... + 1
55번의 참조가 발생하는데
10 * (10 + 1) / 2
N * (N + 1) / 2
시간 복잡도를 판단하는 빅 오 표기법에서 +1이나 /2 같은 작은 수를 생략하기 때문에
O(N * N) 라는 공식이 나옵니다.
선택 정렬의 시간 복잡도는 O(N^2) 입니다.
즉 배열의 길이가 10000 이면 10000 * 10000 = 100000000번의 참조가 발생한다고 판단하는 것인데, 매우 비효율적인 알고리즘이라고 할 수 있습니다 ^^;
_빅 오 표기
: 알고리즘에서 시간의 복잡도를 표시하기 위하여 대문자 오(O)를 사용하여 나타내는 표기. O(n), O(2) 따위와 같이 표기한다.
참고 : https://ndb796.tistory.com/
Author And Source
이 문제에 관하여([알고리즘 c++] 선택정렬), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@mhj6380/알고리즘-c-선택정렬저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)