정렬 알고리즘
1. 선택 정렬 (Selection Sort)
1 10 5 8 7 6 4 3 2 9
이걸 오름차순으로 정렬할 때, 가장 작은 걸 골라(select) 맨 앞으로 가져오는 알고리즘이다.
Source Code
#include <stdio.h>
int main(void){
int i, j, min, index, temp;
int array[10] = {1, 10, 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값을 i번째 부터 마지막 원소까지 검사한다.
min = array[j];
index = j;
}
temp = array[i]; //원래 i번째 있던 값을 temp에 저장
array[i] = array[index]; //최솟값을 i번째로 대입
array[index] = temp; //temp를 바꾼 자리에 저장
}
}
}<시간 복잡도 - 선택 정렬>
10 + 9 + 8 + … + 1
=> 10 * (10 + 1) / 2 = 55
=> N * (N + 1) / 2
=> O(N * N)
=> O(N^2)
선택 정렬은 시간 복잡도가 N제곱 이므로 비효율적인 알고리즘이다.
2. 버블 정렬 (Bubble Sort)
1 10 5 8 7 6 4 3 2 9
이걸 오름차순으로 정렬할 때, 바로 옆에 있는 수와 비교해 큰 수를 뒤로 보내는 것을 계속 반복한다.
정렬 알고리즘 중에서 가장!! 비효율적인 알고리즘이다.
이유: 위의 선택 정렬과 비교해보면 for - for 문 안에서 대입하는 횟수가
선택 정렬은 min = array[j]로 1번이지만
버블 정렬은 swap을 하기 때문에 3번이기 때문에
시간복잡도는 같아도, 실직적인 수행 시간에서 차이가 난다.
Source Code
#include <stdio.h>
int main(void){
int i, j, temp;
int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};ay
for(i = 0; i < 10; i++){ //원소의 개수만큼 반복
for(j = 0; j < 9-i; j++){ //마지막 index부터 가장 큰 수를 뒤로 보내는 것을 반복
if(array[j] > array[j+1]){
temp = array[j];
array[j] = array[j+1];
array[j+1]
}
}
}
}<시간복잡도 - 버블정렬>
10 + 9 + 8 + … + 1
=> 10 * (10 + 1) / 2 = 55
=> N * (N + 1) / 2
=> O(N * N)
=> O(N^2)
3. 삽입정렬 (Insertion Sort)
1 10 5 8 7 6 4 3 2 9
삽입 정렬은 각 숫자를 적절한 위치에 삽입하는 방법으로 문제를 해결한다. 다른 정렬 방식들은 무조건 위치를 바꾸는 방식이었다면, 삽입 정렬은 '필요할 때만' 위치를 바꾸게 된다.
시간복잡도 O(N^2)인 정렬 알고리즘 중에서 가장 빠르다.
각 숫자를 삽입할 때, 이미 앞에 있는 숫자들은 정렬이 되어있기 때문에 빠르다.
그렇다고 엄청 빠른 건 아니다.
Source Code
#include <stdio.h>
int main(void){
int i, j, temp;
int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
for(i = 0; i < 10; i ++){
j = i;
while(array[j] > array[j]+1){
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
j--;
}
}
return 0;
}<시간복잡도 - 삽입정렬>
10 + 9 + 8 + … + 1
=> 10 * (10 + 1) / 2 = 55
=> N * (N + 1) / 2
=> O(N * N)
=> O(N^2)
