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

출력 화면이다.

Microsoft Visual C++ 컴파일러 사용해서 2024년 5월에 정상 작동하였다.
reference : geeksforgeeks