5가지의 정렬 알고리즘을 선택하여 배열을 정렬하는 프로그램 with C++

정렬 알고리즘(sorting algorithms) 대표적인 5가지를 활용하여 visual studio console에서 사용자로부터 배열의 크기와 요소들을 입력받고, 5가지 정렬 방법 중 1가지를 선택하게 하여, 정렬한뒤 결과값을 출력하는 프로그램이다. 기본적으로 무한반복이고 -1을 입력하면 프로그램이 종료한다.

사용한 정렬 방법은 순서대로 선택정렬(selection sort), 버블정렬(bubble sort), 삽입정렬(insertion sort), 머지정렬(merge sort), 퀵정렬(quick sort)이다.

// This program is about 5 sorting algorithms. In main function, we select 5 ways to solve and loop.
#include <iostream>
using namespace std;

void swap(int* a, int* b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}
void printArr(int arr[], int size)
{
	for (int i = 0; i < size; i++)
	{
		cout << arr[i] << " ";
	}
	cout << "\n";
}
void selectionSort(int arr[], int size)
{
	for (int i = 0; i < size - 1; i++)
	{
		int min = i;
		for (int j = i + 1; j < size; j++)
		{
			if (arr[min] > arr[j])
			{
				min = j;
			}
		}
		swap(arr[i], arr[min]);
	}
}
void bubbleSort(int arr[], int size)
{
	for (int i = 0; i < size - 1; i++)
	{
		bool swapped = false;
		for (int j = 0; j < size - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				swap(arr[j], arr[j + 1]);
				swapped = true;
			}
		}
		if (!swapped)
			break;
	}
}
void insertionSort(int arr[], int size)
{
	for (int i = 1; i < size; i++)
	{
		int key = arr[i];
		int j = i - 1;
		while (j >= 0 && arr[j] > key)
		{
			arr[j + 1] = arr[j];
			j--;
		}
		arr[j + 1] = key;
	}
}
void merge(int arr[], int left, int mid, int right)
{
	int numOfLeftArr = mid - left + 1;
	int numOfRightArr = right - mid;
	auto* leftArr = new int[numOfLeftArr];
	auto* rightArr = new int[numOfRightArr];
	for (int i = 0; i < numOfLeftArr; i++)
	{
		leftArr[i] = arr[left + i];
	}
	for (int i = 0; i < numOfRightArr; i++)
	{
		rightArr[i] = arr[mid + 1 + i];
	}

	int indexOfLeftArr = 0;
	int indexOfRightArr = 0;
	int indexOfMergedArr = left;
	while (indexOfLeftArr < numOfLeftArr && indexOfRightArr < numOfRightArr)
	{
		if (leftArr[indexOfLeftArr] < rightArr[indexOfRightArr])
			arr[indexOfMergedArr++] = leftArr[indexOfLeftArr++];
		else
			arr[indexOfMergedArr++] = rightArr[indexOfRightArr++];
	}
	while (indexOfLeftArr < numOfLeftArr)
		arr[indexOfMergedArr++] = leftArr[indexOfLeftArr++];
	while (indexOfRightArr < numOfRightArr)
		arr[indexOfMergedArr++] = rightArr[indexOfRightArr++];
	delete[] leftArr;
	delete[] rightArr;
}
void mergeSort(int arr[], int begin, int end)
{
	if (begin >= end)
		return;
	int mid = begin + (end - begin) / 2;
	mergeSort(arr, begin, mid);
	mergeSort(arr, mid + 1, end);
	merge(arr, begin, mid, end);
}
int partition(int arr[], int low, int high)
{
	int pivot = high;
	int pi = low - 1;
	for (int i = low; i < pivot; i++)
	{
		if (arr[i] < arr[pivot])
			swap(arr[++pi], arr[i]);
	}
	swap(arr[++pi], arr[pivot]);
	return pi;
}
void quickSort(int arr[], int low, int high)
{
	if (low >= high)
		return;
	int pivot = partition(arr, low, high);
	quickSort(arr, low, pivot - 1);
	quickSort(arr, pivot + 1, high);
}

int main()
{
	while (true)
	{
		cout << "Input array size(exit to -1)>>";
		int arrSize{};
		cin >> arrSize;
		if (arrSize == -1)
		{
			cout << "Program exit" << endl;
			break;
		}
		auto* arr = new int[arrSize];
		for (int i = 0; i < arrSize; i++)
		{
			cout << "arr[" << i << "]>>";
			cin >> arr[i];
		}

		while (true)
		{
			cout << "Current Array is >>";
			printArr(arr, arrSize);
			cout << "\n";

			cout << "We sort this arry in ascending order. Input sorting menu\n1. Selection Sort\n2. Bubble Sort\n";
			cout << "3. Insertion Sort\n4. Merge Sort\n5. Quick Sort\n>>";
			int menuNum{};
			cin >> menuNum;
			bool isWrongInput = false;
			switch (menuNum)
			{
			case 1:
				selectionSort(arr, arrSize);
				printArr(arr, arrSize);
				break;
			case 2:
				bubbleSort(arr, arrSize);
				printArr(arr, arrSize);
				break;
			case 3:
				insertionSort(arr, arrSize);
				printArr(arr, arrSize);
				break;
			case 4:
				mergeSort(arr, 0, arrSize - 1);
				printArr(arr, arrSize);
				break;
			case 5:
				quickSort(arr, 0, arrSize - 1);
				printArr(arr, arrSize);
				break;
			default:
				cout << "Wrong input. Try again" << endl;
				isWrongInput = true;
				break;
			}
			if (!isWrongInput)
				break;
		}
	}
}