알고리즘 ] 2. 선택 정렬, 버블 정렬, 삽입 정렬

기본적인 정렬 방법을 안다고 가정하고 종류에 대해서만 간단히 정리

 

1. 선택 정렬

- 전체를 돌면서 가장 작은 값을 차례대로 찾는 방법

// ConsoleApplication9.cpp : 이 파일에는 'main' 함수가 포함됩니다. 거기서 프로그램 실행이 시작되고 종료됩니다.
//

#include <iostream>
#include <queue>
using namespace std;

int main()
{
	int array[10] = { 1, 10, 9, 5, 3, 2, 7, 8, 4, 6 };

	for (int rec = 0; rec < 10; rec++)
	{
		int min = 999;
		int idx, tmp;

		for (int i = rec; i < 10; i++)
		{
			if (array[i] < min)
			{
				min = array[i];
				idx = i;
			}
		}

		tmp = array[rec];
		array[rec] = array[idx];
		array[idx] = tmp;
	}

	for (int i = 0; i < 10; i++)
	{
		cout << array[i];
	}

	return 0;
}

2. 버블 정렬

- 이웃하는 두개를 비교하고 왼쪽이 작은 것이 오도록 하는 정렬

// ConsoleApplication9.cpp : 이 파일에는 'main' 함수가 포함됩니다. 거기서 프로그램 실행이 시작되고 종료됩니다.
//

#include <iostream>
#include <queue>
using namespace std;

int main()
{
	int array[10] = { 1, 10, 9, 5, 3, 2, 7, 8, 4, 6 };

	for (int rec = 0; rec < 10; rec++)
	{
		int min = 999;
		int idx, tmp;

		for (int i = 0; i < 9 - rec; i++)
		{
			if (array[i] > array[i + 1])
			{
				cout << " " << array[i] << ", " << array[i + 1];
				tmp = array[i];
				array[i] = array[i+1];
				array[i+1] = tmp;
			}
		}
		cout << endl;
	}

	for (int i = 0; i < 10; i++)
	{
		cout << array[i];
	}

	return 0;
}

3. 삽입 정렬

- 하나씩 차례로 선택해서 들어가야할 자리를 선택하는 정렬

- 이미 어느정도 정렬되어 있을 경우 효율적인 정렬

// ConsoleApplication9.cpp : 이 파일에는 'main' 함수가 포함됩니다. 거기서 프로그램 실행이 시작되고 종료됩니다.
//

#include <iostream>
#include <queue>
using namespace std;

int main()
{

	int i, j, temp;
	int array[10] = { 1, 10, 9, 5, 3, 2, 7, 8, 4, 6 };

	for (i = 0; i < 9; i++)
	{
		j = i;
		while (array[j] > array[j + 1])
		{
			temp = array[j]; 
			array[j] = array[j+1];
			array[j + 1] = temp;
			j--;
		}
	}

	for (i = 0; i < 10; i++)
	{
		cout << array[i];
	}

	return 0;
}