2. O(n²) 알고리즘(선택, 버블, 삽입 정렬)

 

1. 선택 정렬

가장 적은 것을 선택해 제일 앞으로 보낸다

- 가장 쉽고, 가장 단순

 

#include <stdio.h>

int main(void){
	int i, j, min, index, temp;
	// i, j 반복 탐색, min 작은 것
	int arr[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>arr[j]){
				min = array[j];
				index = j;
			}
		}
		swap(&arr[i], &arr[index]);
	}
	return 0;
}

void swap(int * a, int* b){
	temp = *a;
	*a = *b;
	*b = temp;
}

시간복잡도: n*(n+1)/2 = O(n^2)

 

2. 버블 정렬

옆에 있는 값과 비교해서 더 작은 값을 앞으로 보낸다

- 구현은 쉽지만, 매우 비효율적

- 한 번 반복 시 가장 큰 값이 맨 뒤로 가게 됨

 

#include <stdio.h>

void swap(int * a, int* b){
	int temp = *a;
	*a = *b;
	*b = temp;
}

int main(void){
	int i, j;
	int arr[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9} ;
	for(i=0; i<10; i++){
		for(j=0; j<9-i; j++){
			if(arr[j]>arr[j+1]){
				swap(&arr[j], &arr[j+1]);				
			}
		}
		
	}
	return 0;	
}

 

시간복잡도: 10+9+...+2+1 = O(n^2)

- 실제 실행시 선택 정렬보다 오래걸림. 왜냐면 swap함수가 3줄로 구성되어 있는데 비교시마다 실제로 swap동작을 하기 때문에 속도가 느려지는 것

 

3. 삽입 정렬

각 숫자를 적절한 위치에 삽입하는 방법 -> 필요한 때만 위치를 바꾼다. -> 속도가 빠르다

가정: 선택된 값보다 앞은 모두 정렬이 되어 있다.

index보다 앞에 있는 정렬된 배열 중 어느 사이에 들어가야할지를 정하고 거기에 들어가는 것

 

#include <stdio.h>

void swap(int* a, int* b){
	int temp = *a;
	*a = *b;
	*b = temp;
}


int main(void){
	
	int i, j;
	int arr[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9} ;
	for(i=0; i<9; i++){
		j=i;
		while(arr[j]>arr[j+1]){
			swap(&arr[j], &arr[j+1]);
			j--;
			// 자기가 들어갈 위치를 찾으면 반복문이 멈추게  됨 
		}
	}
	
	for(i=0; i<10; i++){
		printf("%d ", arr[i]);
	} 
}

 

거의 정렬된 상태에서는 swap이 별로 일어나지 않아서 빠른 속도를 가지고 있음

시간복잡도: O(n^2)