032. 동적 메모리 할당을 이용하여 배열을 만들자.

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

#include 
#include 
using namespace std;

void SWAP(int& x, int& y);
void QuickSort(int ary[], int n);

void main()
{
	// 메모리의 종류
	// 정적메모리(스택) : 프로그램에게 미리 할당되는 메모리 영역.
	// 동적메모리(힙) : 프로그램이 스스로 할당하고 해제할 수 있는 메모리 영역.

	// 배열의 정적 생성.
	// 1. 프로그램이 실행될 때 메모리가 할당된다.
	// 2. 프로그램이 종료될 때 메모리가 해제된다.
	int ary[2] = {1,2};

	// 배열의 동적 생성.
	// 1. 이름을 지을 수 없다.
	// 2. 초기화를 할 수 없다.
	// 3. 코드가 수행될 때 메모리가 할당된다.
	int* pary = new int[2];
	pary[0] = 100;
	pary[1] = 200;
	// 4. 메모리를 직접 해제해야만 메모리가 해제된다.
	delete [] pary;

	// 일반 변수의 동적 생성.
	// #. 초기화를 할 수 있다.
	int* pvar = new int(100);
	int& rvar = *pvar;
	cout << rvar << endl; // 100이 출력.
	int* apvar = pvar;
	delete apvar;

	// #. 해제(delete)시 포인터 변수를 넘기는게 아니라 힙에 생성한 메모리의 주소를 넘긴다.

	// 주의점.

	for(int i=0; i<10; i++)
	{
		int a = i+1;
		cout << a << endl;
	}

	for(int i=0; i<10; i++)
	{
		int* pa = new int(i+1);
		cout << *pa << endl;
		// 동적으로 생성한 메모리는 더이상 중괄호의 영향을 받지 않는다.
		delete pa;
	}

	// 연습문제.
	// 1. 사용자로부터 저장할 숫자의 개수를 입력받고, 해당 개수만큼 int형 배열을 만드시오.
	// 2. 사용자로부터 숫자를 입력받아 1번에서 생성한 배열에 순서대로 저장하시오.
	// 3. 입력이 모두 끝나면 입력받은 숫자를 모두 내림차순으로 정렬시킨 후 출력하시오.

	int ary_size = 0;
	int* int_ary = NULL;

	cout << "저장할 숫자의 개수 : ";
	cin >> ary_size;
	int_ary = new int[ary_size];

	for(int i=0; i < ary_size; i++)
	{
		cout << i+1 << "번째 숫자를 입력하시오 : ";
		cin >> int_ary[i];
	}

	QuickSort(int_ary, ary_size);

	cout << ">> 내림차순으로 정렬하여 출력..." << endl;

	for(int i=0; i < ary_size; i++)
	{
		cout << int_ary[i] << "  ";
	}
	cout << endl;

	delete [] int_ary;
}

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));
}