Crocodile Tears

삽입정렬(Insertion Sort)

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

배열의 모든 데이터들을 앞에서부터 차례대로 정렬시키면서 나아가는 방식입니다.

즉, 앞에서부터 차례대로 정렬해 나간다고 보면 되겠습니다.

위키 참고하면 많은 도움이 되실꺼에요. <- 클릭하면 이동합니다.

위키를 보시면 memcpy()를 사용했을 때 25~30% 빠르게 처리된다고 합니다.

삽입정렬 알고리즘의 작동 과정은 다음과 같습니다. (Swap을 하여 처리하는 경우입니다)

< [ 4, -8, 3, 1 ] 정렬 >

위 그림을 보시면 앞에서부터 정렬이 되어 갑니다.

이렇게 순차적으로 정렬을 해 나가면서, 

자신과 비교후 조건이 충족되면 자기 자신을 앞에다 삽입을 합니다.

위를 코드로 보시면 다음과 같습니다.

< C++ 코드 >

#include 
using namespace std;

void insertionSort(int arr[], int length)
{
	int i, j, tmp;
	for(i = 1; i < length; i++)
	{
		j = i;
		while(j > 0 && arr[j - 1] > arr[j])
		{
			tmp = arr[j];
			arr[j] = arr[j - 1];
			arr[j -1] = tmp;
			j--;
		}
	}
}

int main()
{
	int values[] = {4, -8, 3, 1};

	cout << "Before sorting" << endl;
	for(int i = 0; i < 4; i++)
	{
		cout << values[i];
		if(i < 3)
			cout << ", ";
		else 
			cout << endl;
	}

	// sort
	insertionSort(values, 4);
	cout << "After sorting" << endl;
	for(int i = 0; i < 4; i++)
	{
		cout << values[i];
		if(i < 3)
			cout << ", ";
		else 
			cout << endl;
	}
}

< 결과 >

잘못된 부분이 있으면 언제든 리플해주시기 바랍니다.

참고 : http://www.algolist.net/Algorithms/Sorting/Insertion_sort

선택정렬(Selection Sort)

선택 정렬(Selection Sort)은 버블정렬(Bubble Sort)와 같은 시간복잡도(O(n2))를 가지지만, 

버블 정렬과는 조금 달리 불안정(Unstable)한 알고리즘 입니다. 무슨말이냐면, 

예를 들어 {8, 7, 5, 5, 6} 이 있을 경우 정렬한 후에 5와 5의 위치가 바뀔수도 있다는 거랍니다.

즉, 같은 내용을 가지는 키 값들이 정렬 후에도 순서가 유지되는걸 말합니다.

선택정렬은 다음과 같은 과정을 거칩니다.

< [ 8, 2, -1, 5, 4 ] 선택정렬 >

선택 정렬(Selection Sort) 알고리즘은 최초 한 값을 선택하고, 다른 값들과 비교한 후 작은 값이 있으면

그 값을 저장하고 마지막까지 갔다면, 최초 선택한 값과 스왑하는 방식입니다.

글로 쓰니까 어렵네요. 그림이 도움이 될꺼에요.(시간상 2, 3회전은 스킵하였습니다)

< C++ 코드 >

#include 
using namespace std;

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

		if( minIndex != i)
		{
			int temp = arr[minIndex];
			arr[minIndex] = arr[i];
			arr[i] = temp;
		}
	}
}

int main()
{
	int values[] = {8, 2, -1, 5, 4};

	cout << "Before sorting" << endl;
	for(int i = 0; i < 5; i++)
	{
		cout << values[i];
		if(i < 4)
			cout << ", ";
		else 
			cout << endl;
	}

	// sort
	selectionSort(values, 5);
	cout << "After sorting" << endl;
	for(int i = 0; i < 5; i++)
	{
		cout << values[i];
		if(i < 4)
			cout << ", ";
		else 
			cout << endl;
	}
}

< 결과 >

참고 : http://www.algolist.net/

버블정렬(Bubble Sort)

기본적으로 가장 간단한 정렬이라 생각이 듭니다.

앞 뒤를 비교해서 우선순위를 정해 교체하는 알고리즘이죠.

버블정렬(Bubble Sort)의 시간복잡도는 O(n2)가 됩니다. 분기문을 두번 돌아야 하니까요.

{3, 2, 5, 4, 1} 을 버블정렬을 통해 정렬을 하면 다음과 같은 과정을 거치게 됩니다.

< [ 3, 2, 5, 4, 1] 정렬 >

녹색은 이미 정렬된 상태이므로 그대로 두고, 빨간색은 교체(스왑) 시켜줍니다.

그리고 주황색은 이미 정렬된 상태로 건드리지 않는다는 의미 입니다.

< C++ 코드 >

#include 
using namespace std;

void bubbleSort(int arr[], int n)
{
	bool swapped = true;
	int j= 0;
	int tmp = 0;
	while(swapped)
	{
		swapped = false;
		j++;
		for(int i = 0; i < n - j; i++)
		{
			// 이 조건을 변경하여 오름차순, 내림차순을 설정합니다.
			if(arr[i] < arr[i+1])
			{
				tmp = arr[i];
				arr[i]= arr[i + 1];
				arr[i + 1]= tmp;
				swapped = true;
			}
		}		
	}
}

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

	cout << "Before sorting" << endl;
	for(int i = 0; i < 5; i++)
	{
		cout << values[i];
		if(i < 4)
			cout << ", ";
		else 
			cout << endl;
	}

	// sort
	bubbleSort(values, 5);
	cout << "After sorting" << endl;
	for(int i = 0; i < 5; i++)
	{
		cout << values[i];
		if(i < 4)
			cout << ", ";
		else 
			cout << endl;
	}
}

< 결과 >

참고 : http://www.algolist.net/Algorithms/Sorting/Bubble_sort