정렬(1) - 선택 정렬 / 버블 정렬 / 삽입 정렬

기본적으로 세 정렬 모두 2중 for문을 사용하기 때문에

시간 복잡도는 최대 O(n2) 이다. 

 

1. 선택 정렬

 (1) 맨 첫 번째 위치에서 시작한다 (ex : a[0])

 (2) 자신보다 오른쪽에 있는 원소 들을 하나씩 탐색한다.

 (3) 그 중 자신보다 작은 원소가 있으면 swap하여 정렬한다. 

 

#include <iostream>
using namespace std;

int main(void) {

	int i,j;
	int arr[5] = {10,2,15,59,28};    
    
	for(int i=0; i<4; i++)
    	{
    		for(int j=i+1; j<5; j++)
        	{
        		if(arr[i] > arr[j])
            		swap(arr[i], arr[j]);
        	}
    	}

	for(int x=0; x<5; x++)
    	cout << arr[x] << " ";

	return 0;
}

가장 이해하기 쉬운 정렬이다. 

 

2. 버블 정렬

(1) 배열의 원소 N개가 있다면, 첫 번째에는 0부터 N까지 숫자를 비교한다. 

(2) a[0]과 a[1]을 비교하여 a[1](자신의 오른쪽 원소)이 a[0]보다 크면 자리를 바꾼다. 

(3) a[0]과 a[1] -> a[1]과 a[2] .. 이렇게 비교가 진행된다.

(3) 한 사이클을 돌았으면 범위를 점점 좁혀서 진행한다. 

 

#include <iostream>
using namespace std;

int main(void) {

	int i,j;
	int arr[5] = {10,2,15,59,28};    
    
	for(i=0; i<4; i++)
    	{
    		for(j=0; j<4-i; j++)
        	{
        		if(arr[j] > arr[j+1])
            		swap(arr[j], arr[j+1]);
        	}
    	}

	for(int x=0; x<5; x++)
    	cout << arr[x] << " ";

	return 0;
}

 

3. 삽입정렬 

(1) 위의 정렬들과는 다르게 자신의 왼쪽과 비교를 한다. 그래서 i=1부터 시작한다. 

(2) i=1부터 N까지 KEY값으로 설정된다. 

(3) KEY값보다 값이 작으면 자리를 바꾸게 된다. 

#include <iostream>
using namespace std;

int main(void) {

	int i,j,key;
	int arr[5] = {10,2,15,59,28};    
    
	for(int i=1; i<5; i++)
    	{
        	key = arr[i];
    		for(j=i-1; j>=0; j--)
        	{
        		if(arr[j] > key)
            			arr[j+1]=arr[j];
                	else 
                   	 	break;
        	}
            	arr[j+1] = key;
    	}

	for(int x=0; x<5; x++)
    	cout << arr[i] << " ";

	return 0;
}