정렬 알고리즘(sort)

버블 정렬 알고리즘(Bubble Sort)

 

서로 인접한 두 원소를 검사하여 순서에 맞지 않는 경우 위치를 바꾼다.

 

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

 

 

| 5 | 4 | 6 | 1 | 3 | 2 |

 

위의 숫자로 이루어져 있을때

 

 

 

1회전 시

 

 

5 4 비교하여 작은숫자를 왼쪽 큰 숫자를 오른쪽으로

| 4 | 5 | 6 | 1 | 3 | 2 |

5 6 비교 시 아무일도 일어나지 않음.

6 1 비교 시

| 4 | 5 | 1 | 6 | 3 | 2 |

6 3 비교 시

| 4 | 5 | 1 | 3 | 6 | 2 |

6 2 비교 시

| 4 | 5 | 1 | 3 | 2 | [6] |

4 5 1 3 2 [6] 마지막 6은 이제 고정

 

큰수를 계속 뒤로 미뤄내기때문에 가장 마지막값은 최대값이 되고 2회전때는 마지막값은 비교할 필요 없으니 그 외의 값들을 다시 비교한다.

 

 

 

2회전

 

 

4 5 비교 4 5 1 3 2 [6]

5 1 비교 4 1 5 3 2 [6]

5 3 비교 4 1 3 5 2 [6]

5 2 비교 4 1 3 2 [5] [6]

 

| 4 | 1 | 3 | 2 | [5] | [6] |

 

 

마지막의 전번째가 고정되게 된다.

 

 

 

3회전

 

| 1 | 3 | 2 | [4] | [5] | [6] |

4회전

| 1 | 2 | [3] | [4] | [5] | [6] |

5회전

 

| 1 | [2] | [3] | [4] | [5] | [6] |

 

 

 

(원소의갯수 -1)회전을 돌게 되면 전체 다 정렬이 가능하다.

 

 

버블정렬 코드

#include<stdio.h>
#define MAX 6

int bubble_sort(int arr[],int n){
    int i,j,temp;
    for (i= n-1; i>0; i--){
        for (j =0; j < i; j++){
            if (arr[j] > arr[j+1]){
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

int main(){
	int arr[MAX] = {5,4,6,1,3,2};
	bubble_sort(arr,MAX);
	for (int i=0; i < MAX; i++){
		printf("%d\n",arr[i]);
	}
	return 0;
}

 

 

코드를 돌려보면 bubble_sort를 돌면서 두 숫자를 비교하게 되고 if (arr[j] > arr[j+1])

 

 

앞의 숫자가 크면 두 자리를 바꿔주는 코드이다.

 

 

1회전시 i=5 j = 0,1,2,3,4

arr[0] > arr[1] 비교 5 > 4 => 4 5 6 1 3 2

arr[1] > arr[2] 비교 5 > 6 => 4 5 6 1 3 2

arr[2] > arr[3] 비교 6 > 1 => 4 5 1 6 3 2

arr[3] > arr[4] 비교 6 > 3 => 4 5 1 3 6 2

arr[4] > arr[5] 비교 6 > 2 => 4 5 1 3 2 [6]

2회전시 i=4 j = 0,1,2,3 4 1 3 2 [5] [6]

....

5회전시 i=1 j= 0 1 [2] [3] [4] [5] [6]

1회전~5회전 돌게 되면서 정리되어서

 

결과는 1,2,3,4,5,6이 나오게된다.

 

 

선택 정렬 알고리즘(Selection Sort)

 

 

가장 작은(큰) 원소를 선택하여 순차적으로 배치하는 알고리즘

 

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

 

 

| 5 | 4 | 6 | 1 | 3 | 2 |

[0] [1] [2] [3] [4] [5]

일때 최소값의 index를 저장해두는데

 

최소값이 미정이니 인덱스0을 넣어두고 돌려보겠다.

 

 

 

1회전시에 5(인덱스0)와 4(인덱스1)를 비교 index = 1 저장

 

저장되어있는 인덱스의 값인

4(인덱스1)와 6(인덱스2)와 비교 index =1 그대로

4(인덱스1)와 1(인덱스3) 비교 index = 3 저장

1과 3 비교 index = 3

1과 2 비교 index = 3

최종적으로 최소값 인덱스는 3이 되고,

 

제일 작은 값은 제일 앞에 와야하기에 맨 앞과 바꿔준다. (1과 5를 교체)

 

 

1회전

 

| [1] | 4 | 6 | 5 | 3 | 2 |

 

 

2회전

| [1] | [2] | 6 | 5 | 3 | 4 |

....

5회전

| [1] | [2] | [3] | [4] | [5] | 6 |

#include<stdio.h>
#define MAX 6

int selection_sort(int arr[],int n){
    int i,j, minIndex, temp;
    for (i= 0; i<n-1; i++){
    	minIndex = i; // 초기 최소값 인덱스 설정
        for (j =i+1; j < n; j++){
            if (arr[j] < arr[minIndex]){ // 비교부분
            	minIndex = j;
            	}
       	}
        temp = arr[minIndex]; //교체부분
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

int main(){
	int arr[MAX] = {5,4,6,1,3,2};
	selection_sort(arr,MAX);
	for (int i=0; i < MAX; i++){
		printf("%d\n",arr[i]);
	}
	return 0;
}

 

삽입 정렬 알고리즘(Insertion Sort)

앞의 원소부터 차례대로 진행하여 원소 앞의 이미 정렬된 배열에 자신의 위치를 삽입하는 알고리즘

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

 

앞의 정렬들과 다 똑같은 시간복잡도지만 좀 더 빠르게 수행될수도 있다.(아래 코드부분에서 확인)

 

| 5 | 4 | 6 | 1 | 3 | 2 |

삽입 정렬 알고리즘에선 앞의 배열과 현재 원소를 비교하게 된다.

그래서 인덱스 1부터 시작하게되는데

 

1회전 시

 

[4]와 5를 비교하여 변경

| [4] | 5] | 6 | 1 | 3 | 2 |

 

2회전시

 

[4 5]와 6을 비교

| [4 | 5 | 6] | 1 | 3 | 2 |

 

3회전시

 

[4 5 6] 과 1을 비교

1) 6 과 1 비교 -> 1 6

2) 5와 1 비교 -> 1 5

3) 4와 1 비교 -> 1 4

| [1 | 4 | 5 | 6] | 3 | 2 |

 

4회전시

 

[1 4 5 6] 과 3을 비교

1) 6 3 비교 -> 3 6

2) 5 3 비교 -> 3 5

3) 4 3 비교 -> 3 4

4) 1 3 비교 -> 1 3

| [1 | 3 | 4 | 5 | 6] | 2 |

 

5회전시

 

[1 3 4 5 6] 과 2를 비교

| [1 | 2 | 3 | 4 | 5 | 6] |

 

기존의 정렬들과의 차이점은

기존 정렬들은 일단 전체 반복을 해서 비교를 한다면

앞의 배열중에 맨 처음 비교하는것보다 클 경우 다른것들과 비교하지 않는다는것이다.

예) 2회전 시 [4 5]와 6을 비교

5 와 6 비교시 6이 크므로 4랑은 따로 비교를 하지 않는다.

#include<stdio.h>
#define MAX 6

int insertion_sort(int data[],int n){ //data[] = {5,4,7,1,3,2}
	int i, j, remember;
	for (i=1; i< n; i++){
        remember = data[(j=i)]; //현재 숫자 저장
        // 아래 코드 : 비교대상이 인덱스 0이상이면서(&&) 현재숫자가 비교숫자보다 작으면
        while(--j >= 0 && remeber < data[j])
        {
        	data[j + 1] = data[j]; // 비교숫자는 한칸 뒤로 이동
            data[j] = remember;	//비교숫자 위치에 현재숫자 저장
        }
    }

int main(){
	int arr[MAX] = {5,4,6,1,3,2};
	selection_sort(arr,MAX);
	for (int i=0; i < MAX; i++){
		printf("%d\n",arr[i]);
	}
	return 0;
}