[알고리즘] 선택정렬, 버블정렬, 삽입정렬 - O(N^2)

정렬 알고리즘

 

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)

 

4. 퀵정렬 (Quick Sort)

퀵 정렬은 '분할 정복' 알고리즘으로 평균 속도가 O(N * logN)이다.

퀵 정렬은 하나의 큰 문제를 두 개의 작은 문제로 분할하는 식으로 빠르게 정렬한다. 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눈다.

일반적으로 퀵 정렬에는 기준 값이 있는데, 이를 피벗(Pivot)이라고 한다. 보통은 피벗 값을 첫번째 원소로 정한다.

 

우리는 다음과 같이 1이 피벗 값으로 설정됐다고 생각해보자.

1 10 5 8 7 6 4 3 2 9

이 경우 1보다 큰 숫자를 왼쪽부터 찾고, 동시에 1보다 작은 숫자를 오른쪽부터 찾는다.

이 때 1보다 큰 숫자로는 바로 10이 있겠고, 1보다 작은 숫자가 1의 오른쪽에 없기 때문에 9, 2, 3, 4 ... 를 지나 결국 피벗값 1에 도달한다.

Source code

#include <stdio.h>

int number = 10;
int data[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};

void quickSort(int *data, int start, int end) {
    if (start >= end) { //원소가 1개인 경우
        return;
    }
    
    int key = start; //키(pivot)는 첫 번째 원소
    int i = start + 1; //왼쪽 출발 지점
    int j = end; //오른쪽 출발 인덱스
    int temp;
    
    while(i <= j) { //i와 j가 엇갈릴 때 까지 반복
        while(data[i] <= data[key]) { //키값보다 왼쪽에 있는게 클 때까지
            i++;
        }
        while(data[j] >= data[key] && j > start) {
            j--;
        }
        if(i > j) { //'현재' 엇갈린 상태면 키 값과 교체
            temp = data[j];
            data[j] = data[key];
            data[key] = temp;
        } else {
            temp = data[j];
            data[j] = data[i];
            data[i] = temp;
        }
    }
    //재귀함수 이용해서 
    quickSort(data, start, j - 1);
    quickSort(data, j + 1, end);
}
int main(void) {
    quickSort(data, 0, number - 1);
}

퀵 정렬 범위 설정

quickSort()에서 오른쪽부터 키값보다 작은 값을 찾을 때

while의 조건문에 j > start 가 있는 이유는 만약 키 값보다 작은 값이 오른쪽에 없는 경우 더 넘어가지 않고 키값 다음 인덱스에서 검사를 멈추게 하기 위해서이다.

 

그렇다면 위에서 왼쪽부터 키 값보다 큰 값을 찾는 while문에는 왜 그런 범위를 설정하지 않아도 되는걸까?

그 이유는 왼쪽부터 키값으로 도달한 경우 i와 j가 엇갈려 제일 바깥 while이 종료 되기 때문이다.

 

퀵 정렬의 한계

그러나, pivot 값을 잘못 정할 경우 퀵정렬의 최악 시간 복잡도는 O(N^2)가 돼버리기도 한다.

 

이미 정렬이 되어있는 경우를 생각해보자.

1 2 3 4 5 6 7 8 9 10

pivot값: 1

오른쪽부터 10번이나 비교를 해도 작은 값을 찾지 못하고

1 2 3 4 5 6 7 8 9 10

이렇게 마무리된다.

...

이런식으로 10번, 9번, ... 연산을 하게 되어 O(N^2)가 되는 것이다.

 

+) 내림차순으로 바꾸고 싶을 경우 숫자를 정렬하는 방향이 반대가 되는 것이기 때문에 왼쪽을 오른쪽으로, 오른쪽을 왼쪽으로 바꿔주면 된다.