[자료구조] 단순한 정렬 : 버블 정렬, 선택 정렬, 삽입 정렬

버블 정렬(Bubble Sort)

: 인접한 두 개의 데이터를 비교하여, 정렬순서 상 위치가 바뀌어야 하는 경우에 두 데이터의 위치를 바꿔나가는 방식이다. 오름차순으로 데이터를 정렬한다고 가정했을때, 큰 값을 뒤로 보내는 방식으로 구현된다.

#include <stdio.h>

void BubbleSort(int arr[], int n)
{
	int i, j;
	int temp; 

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


int main(void)
{
	int arr[4] = {3, 2, 4, 1};
	int i;

	BubbleSort(arr, sizeof(arr)/sizeof(int));

	for(i=0; i<4; i++)
		printf("%d ", arr[i]);

	printf("\n");
	return 0;
}

선택 정렬(Selection Sort)

: 오름차순으로 데이터를 나열한다는 가정하에, 주어진 배열에서 최솟값을 찾은 후 앞에서부터 데이터를 채워나가는 방식이다. 별도의 메모리 공간이 필요할 것 같지만, 최솟값이 있는 메모리 공간과 바꿔야하는 메모리 공간을 교환하는 방식으로 구현된다. 구현 방식 상 교환이라는 표현을 사용하고 있지만, 실제로는 작은 값을 앞에서 부터 채워나가는 방식이다.

#include <stdio.h>

void SelSort(int arr[], int n)
{
	int i, j;
	int maxIdx;
	int temp;

	for(i=0; i<n-1; i++)
	{
		maxIdx = i;   
        
		for(j=i+1; j<n; j++)  
		{
			if(arr[j] < arr[maxIdx])
				maxIdx = j;
		}

		temp = arr[i];
		arr[i] = arr[maxIdx];
		arr[maxIdx] = temp;
	}
}


int main(void)
{
	int arr[4] = {3, 4, 2, 1};
	int i;

	SelSort(arr, sizeof(arr)/sizeof(int));

	for(i=0; i<4; i++)
		printf("%d ", arr[i]);

	printf("\n");
	return 0;
}

 

 삽입 정렬(Insertion Sort)

: 정렬이 된 부분과 그렇지 않은 부분을 나누어서, 정렬이 안된 데이터를 정렬이 된 데이터의 특정 위치에 "삽입"해나가면서 정렬을 진행하는 알고리즘이다. 삽입 정렬은 데이터가 이미 정렬되어 있는 경우 매우 빠르게 동작한다.

#include <stdio.h>

void InserSort(int arr[], int n)
{
	int i, j;
	int insData;

	for(i=1; i<n; i++)
	{
		insData = arr[i];   

		for(j=i-1; j>=0 ; j--)
		{
			if(arr[j] > insData) 
				arr[j+1] = arr[j];   
			else
				break;   
		}

		arr[j+1] = insData;  
	}
}


int main(void)
{
	int arr[5] = {5, 3, 2, 4, 1};
	int i;

	InserSort(arr, sizeof(arr)/sizeof(int));

	for(i=0; i<5; i++)
		printf("%d ", arr[i]);

	printf("\n");
	return 0;
}

출처 : 윤성우의 열혈 자료구조