030. 정렬 알고리즘에 대해서 알아보자.

◈ 이 글은 강의를 위하여 제가 직접 작성한 내용입니다. 따라서 퍼가실 경우, 출처를 명확히 해주시기 바랍니다!!
◈ This ariticle was written by me for teaching. So if you want to copy this article, please clarify the source!!

삽입 소트

// 삽입 소트 알고리즘.
/*
배열의 2번째 요소부터 마지막 요소까지 아래 내용을 수행하시오.
1. 배열의 2번째 요소를 1번째 요소와 크기를 비교한 후 큰 값이 오른쪽(2번째요소)에 오도록 스왑한다.
2. 배열의 3번째 요소를 2번째 요소와 크기를 비교한 후 큰 값이 오른쪽(3번째요소)에 오도록 스왑한다. 
   그리고 다시 1번을 수행한다.
3. 배열의 4번째 요소를 3번째요소와 크기를 비교한 후 큰 값이 오른쪽(4번째요소)에 오도록 스왑한다. 
   그리고 다시 2번을 수행한다.
4. 배열의 마지막 요소를 마지막-1 요소와 크기를 비교한 후 큰 값이 오른쪽에 오도록 스왑한다. 
   그리고 다시 이전 작업을 수행한다.

// 삽입소트 정렬순서.
// 데이터가 10개일때,
(2,1)
(3,2), (2,1)
(4,3), (3,2), (2,1)
(5,4), (4,3), (3,2), (2,1)
(6,5), (5,4), (4,3), (3,2), (2,1)
(7,6), (6,5), (5,4), (4,3), (3,2), (2,1)
(8,7), (7,6), (6,5), (5,4), (4,3), (3,2), (2,1)
(9,8), (8,7), (7,6), (6,5), (5,4), (4,3), (3,2), (2,1)
(10, 9), (9,8), (8,7), (7,6), (6,5), (5,4), (4,3), (3,2), (2,1)
*/

#include  
using namespace std;
void ShowArray(char *pcAry, int cnt);
void ISort(char *pcAry, int cnt);
void main( )
{
	char a[] = {'H', 'B', 'D', 'G', 'A', 'J', 'E', 'I', 'F', 'C'};
	cout << "정렬 전..." << endl;
	ShowArray(a, sizeof(a));
	ISort(a, sizeof(a));
	cout << "정렬 후..." << endl;
	ShowArray(a, sizeof(a));
}
void ShowArray(char *pcAry, int cnt)
{
	for(int i=0; i < cnt; i++)
	{
		cout << pcAry[i] << "\t";
	}
	cout << endl;
}
void ISort(char *pcAry, int cnt)
{
	// 제 2요소부터 마지막 요소까지 반복한다.
	for(int baseItem=1; baseItem < cnt; baseItem++)
	{
		// 현재요소부터 제2요소까지 반복한다.
		for(int checkItem=baseItem; checkItem >= 1; checkItem--)
		{
			// 큰 값이 오른쪽에 위치하도록 스왑한다.
			if(pcAry[checkItem-1] > pcAry[checkItem])
			{
				char temp = pcAry[checkItem];
				pcAry[checkItem] = pcAry[checkItem-1];
				pcAry[checkItem-1] = temp;
			}
			else
			{
				break;
			}
		}
	}
}

버블 소트

// 버블 소트 알고리즘.

/*
1. 배열의 크기가 n일 경우,
2. 배열의 1번째 요소와 2번째 요소의 크기를 비교한 후 큰 값이 오른쪽에 오도록 스왑한다.
3. 배열의 2번째 요소와 3번째 요소의 크기를 비교한 후 큰 값이 오른쪽에 오도록 스왑한다.
4. 배열의 n-1번째 요소와 n번째 요소의 크기를 비교할때까지 계속 진행한다.
5. 배열의 크기 n이 1이 될때까지 n을 1감소하고 1번부터 4번까지를 다시 반복 수행한다.
6. 중간에 정렬이 끝나게 되면 불필요한 수행을 막기 위해 함수를 종료한다.

>> 데이터가 10개일 경우,
(1,2), (2,3), (3,4), (4,5), (5,6), (6,7), (7,8), (8,9), (9,10)
(1,2), (2,3), (3,4), (4,5), (5,6), (6,7), (7,8), (8,9)
(1,2), (2,3), (3,4), (4,5), (5,6), (6,7), (7,8)
(1,2), (2,3), (3,4), (4,5), (5,6), (6,7)
(1,2), (2,3), (3,4), (4,5), (5,6)
(1,2), (2,3), (3,4), (4,5)
(1,2), (2,3), (3,4)
(1,2), (2,3)
(1,2)

*/

#include  
using namespace std;
void ShowArray(char *pcAry, int cnt);
void BSort(char *pcAry, int cnt);
void main( )
{
	char a[] = {'H', 'B', 'D', 'G', 'A', 'J', 'E', 'I', 'F', 'C'};
	ShowArray(a, sizeof(a));
	BSort(a, sizeof(a));
	ShowArray(a, sizeof(a));
}
void ShowArray(char *pcAry, int cnt)
{
	for(int i=0; i < cnt; i++)
	{
		cout << pcAry[i] << "\t";
	}
	cout << endl;
};
void BSort(char *pcAry, int cnt)
{
	while(cnt > 0)
	{
		bool isChange = false;		// 스왑이 일어났는지 여부.
		int idx = 0;
		while(idx < cnt-1)		// 배열[cnt]는 존재하지 않으므로, 배열[cnt-2]와 배열[cnt-1]을 가장 마지막에 비교해야한다.
		{
			if(pcAry[idx] > pcAry[idx+1])
			{
				char temp = pcAry[idx];
				pcAry[idx] = pcAry[idx+1];
				pcAry[idx+1] = temp;
				isChange = true;
			}
			idx++;
		}
		// 스왑이 일어나지 않았다면 정렬이 끝난 상태이므로 루프를 벗어난다.
		if(isChange == false) break;
		cnt--;
	}
}

퀵 소트

// 재귀함수.
/*
#include  
using namespace std;

void Show(int n)
{
	cout << n << endl;
	if(n>0) Show(n-1);
	//cout << n << endl; // 함수작동 원리 이해하기. 결과값이 왜 그렇게 출력되는지 설명하라.
}

void main( )
{
	Show(10);
}
*/

// 퀵 소트 알고리즘.

// 4 2 5 3 7 1 6

#include 
#include 
using namespace std;

#define MAX_SIZE 100

void SWAP(int& x, int& y)
{
	int temp = x;
	x  = y;
	y = temp;
}

void QuickSort(int ary[], int n)
{
	if(n <= 1) return;

	int find=0;

	// 첫번째 요소의 값보다 작은 요소들을 찾아서
	// 첫번째 요소의 다음위치부터 차례대로 차곡차곡 쌓는다.
	for(int i=1; i < n; i++)
	{
		if(ary[i] < ary[0])
		{
			find += 1;
			SWAP(ary[i], ary[find]);
		}
	}

	// 첫번째 요소와 첫번째 요소보다 작은 요소들의 마지막 요소를 스왑하여,
	// 전체 배열을 첫번째요소보다 작은 요소들과 큰 요소들로 이등분한다.
	SWAP(ary[0], ary[find]);

	// 작은 요소들의 집합에서 위에서 한 작업을 반복수행한다.
	QuickSort(ary, find);
	// 큰 요소들의 집합에서 위에서 한 작업을 반복수행한다.
	QuickSort(ary+(find+1), n-(find+1));
}

int main()
{
	int list[MAX_SIZE];
	int num;

	cout << "랜덤 숫자 생성, 몇개 : ";
	cin >> num;
	cout << endl;

	cout << "정렬 전 리스트 출력..." << endl;
	srand((unsigned)time(NULL));
	for(int i=0; i < num; i++) 
	{
		list[i] = rand() % MAX_SIZE + 1;
		cout << list[i] << " ";
	}

	cout << endl;

	QuickSort(list, num);

	cout << "정렬 후 리스트 출력..." << endl;
	for(int i=0; i < num; i++)
	{
		cout << list[i] << " ";
	}
	
	cout << endl;
}