[알고리즘] 기본적인 정렬 알고리즘(버블 정렬, 선택 정렬, 삽입 정렬)

정렬  :  주어진 데이터를 정해진 기준에 따라 순서를 재배열하는 작업

가장 기본적인 정렬 알고리즘에 대해 설명하겠다.

 

1. 버블 정렬(bubble sort)

인접한 두 원소의 크기를 비교하여 교환하는 작업을 반복하여 정렬하는 알고리즘

 

출처 : product plan

 

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

 

2. 선택 정렬 (selection sort)

 

정렬 되지 않은 원소 중에서 최소값 원소를 찾아서 맨 왼쪽 원소와 교환

 

void selection_sort(int data[], int n)
{
	for (int i=0; i<n-1; i++){
    		int idx=i;
        	for(int j=i+1; j<n; j++)
        		if(data[j] < data[idx])
            			idx = j;
        	swap(data[i], data[idx]);
    	}
}

 

3. 삽입 정렬(insertion sort)

 

정렬되지 않은 부분의 첫번째 원소를 정렬된 부분의 알맞은 위치에 삽입하는 과정을 반복

 

 

void insertion_sort(int data[], int n)
{
	for(int i=1;i<n;i++){
    		int key=data[i];
        	int j=i-1;
        	while(j>=0 && data[j] > key){
        		data[j+1] = data[j];
            		j--;
        	}
        	data[j+1] = key;
    	}
}

 

4. 시간복잡도

삽입정렬 = O(n^2)

선택정렬 = O(n^2)

버블정렬 = O(n^2)