/*
프로젝트명(Subject): 알고리즘(정렬)
작성자(Author): 도도(Dodo)
작성일자(Create Date): 2017-10-01
파일명(FileName): sort.cpp */ #include <iostream>
#include "sort.h" // 최대(배열)
int Sort::getArrMax(int arr[], int n)
{
int mx = arr[0]; for (int i = 1; i < n; i++)
if (arr[i] > mx)
mx = arr[i]; return mx;
} // 최소
int Sort::min(int x, int y){
return x < y ? x : y;
} // 최대
int Sort::max(int x, int y) {
return x > y ? x : y;
} // 교환 (Swap)
void Sort::swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
} // 삽입 정렬(Insertion Sort)
void Sort::insertion(int arr[], int n)
{
int i, key, j;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i - 1; while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
} } void Sort::recurInsertion(int arr[], int n)
{
// Base case
if (n <= 1)
return; // Sort first n-1 elements
recurInsertion(arr, n - 1); // Insert last element at its correct position
// in sorted array.
int last = arr[n - 1];
int j = n - 2; /* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > last)
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = last;
}
// 버블 정렬(Bubble Sort)
void Sort::bubbleSort(int arr[], int n)
{
int i, j;
for (i = 0; i < n - 1; i++)
// Last i elements are already in place
for (j = 0; j < n - i - 1; j++)
if (arr[j] > arr[j + 1])
swap(&arr[j], &arr[j + 1]); } // 재귀 버블 정렬(recursive Bubble Sort)
void Sort::recurBubbleSort(int arr[], int n)
{
// Base case
if (n == 1)
return; // one pass of bubble sort. After
// this pass, the largest element
// is moved (or bubbled) to end.
for (int i = 0; i < n - 1; i++)
if (arr[i] > arr[i + 1])
swap(&arr[i], &arr[i + 1]); // Largest element is fixed,
// recur for remaining array
recurBubbleSort(arr, n - 1);
} // 선택 정렬(Selection Sort)
void Sort::selectionSort(int arr[], int n)
{
int i, j, min_idx; // one by one move boundary of unsorted subarray
for (i = 0; i < n - 1; i++)
{
// Find the minimum element in unsorted array
min_idx = i;
for (j = i + 1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j; // Swap the found minimum element with the first element
swap(&arr[min_idx], &arr[i]);
}
} // 병합(Merge)
void Sort::merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m; /* create temp arrays */ int *L = new int[n1];
int *R = new int[n2]; /* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j]; /* Merge the temp arrays back into arr[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
} /* Copy the remaining elements of L[], if there
are any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
} /* Copy the remaining elements of R[], if there
are any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
} // 재귀 병합 정렬(Recursive Merge Sort)
void Sort::recurMergeSort(int arr[], int l, int r)
{
if (l < r)
{
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l + (r - l) / 2; // Sort first and second halves
recurMergeSort(arr, l, m);
recurMergeSort(arr, m + 1, r); merge(arr, l, m, r);
}
} // 병합 정렬(Merge Sort)
void Sort::mergeSort(int arr[], int n)
{
int curr_size; // For current size of subarrays to be merged
// curr_size varies from 1 to n/2
int left_start; // For picking starting index of left subarray
// to be merged // Merge subarrays in bottom up manner. First merge subarrays of
// size 1 to create sorted subarrays of size 2, then merge subarrays
// of size 2 to create sorted subarrays of size 4, and so on.
for (curr_size = 1; curr_size <= n - 1; curr_size = 2 * curr_size)
{
// Pick starting point of different subarrays of current size
for (left_start = 0; left_start<n - 1; left_start += 2 * curr_size)
{
// Find ending point of left subarray. mid+1 is starting
// point of right
int mid = left_start + curr_size - 1; int right_end = min(left_start + 2 * curr_size - 1, n - 1); // Merge Subarrays arr[left_start...mid] & arr[mid+1...right_end]
merge(arr, left_start, mid, right_end);
}
}
} // 분할(Partition)
int Sort::partition(int arr[], int low, int high)
{
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element for (int j = low; j <= high - 1; j++)
{
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot)
{
i++; // increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
} // 재귀 퀵 정렬(Recursive Quick Sort)
void Sort::recurQuickSort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[p] is now
at right place */
int pi = partition(arr, low, high); // Separately sort elements before
// partition and after partition
recurQuickSort(arr, low, pi - 1);
recurQuickSort(arr, pi + 1, high);
}
} // 퀵 정렬(Quick Sort)
void Sort::quickSort(int arr[], int l, int h)
{
// Create an auxiliary stack
int *stack = new int[h - l + 1]; // initialize top of stack
int top = -1; // push initial values of l and h to stack
stack[++top] = l;
stack[++top] = h; // Keep popping from stack while is not empty
while (top >= 0)
{
// Pop h and l
h = stack[top--];
l = stack[top--]; // Set pivot element at its correct position
// in sorted array
int p = partition(arr, l, h); // If there are elements on left side of pivot,
// then push left side to stack
if (p - 1 > l)
{
stack[++top] = l;
stack[++top] = p - 1;
} // If there are elements on right side of pivot,
// then push right side to stack
if (p + 1 < h)
{
stack[++top] = p + 1;
stack[++top] = h;
}
}
} // heapify(히피) - 힙 정렬(Heap Sort)
void Sort::heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2 // If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l; // If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r; // If largest is not root
if (largest != i)
{
swap(&arr[i], &arr[largest]); // Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
} // 힙 정렬(Heap Sort)
void Sort::heapSort(int arr[], int n)
{
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i); // one by one extract an element from heap
for (int i = n - 1; i >= 0; i--)
{
// Move current root to end
swap(&arr[0], &arr[i]); // call max heapify on the reduced heap
heapify(arr, i, 0);
}
} // 카운트 정렬(Count Sort)
void Sort::countSort(int arr[], int n, int exp)
{
int *output = new int[n]; // output array
int i, count[10] = { 0 }; // Store count of occurrences in count[]
for (i = 0; i < n; i++)
count[(arr[i] / exp) % 10]++; // Change count[i] so that count[i] now contains actual
// position of this digit in output[]
for (i = 1; i < 10; i++)
count[i] += count[i - 1]; // Build the output array
for (i = n - 1; i >= 0; i--)
{
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
} // Copy the output array to arr[], so that arr[] now
// contains sorted numbers according to current digit
for (i = 0; i < n; i++)
arr[i] = output[i];
} // 기수 정렬(Radix Sort)
void Sort::radixsort(int arr[], int n)
{
// Find the maximum number to know number of digits
int m = getArrMax(arr, n); for (int exp = 1; m / exp > 0; exp *= 10)
countSort(arr, n, exp);
} // 이진 탐색(Binary Search)
int Sort::binarySearch(int a[], int item, int low, int high)
{
if (high <= low)
return (item > a[low]) ? (low + 1) : low; int mid = (low + high) / 2; if (item == a[mid])
return mid + 1; if (item > a[mid])
return binarySearch(a, item, mid + 1, high);
return binarySearch(a, item, low, mid - 1);
} // 삽입 정렬(Binary Insertion Sort)
void Sort::binaryInsertion(int a[], int n)
{
int i, loc, j, k, selected; for (i = 1; i < n; ++i)
{
j = i - 1;
selected = a[i]; // find location where selected sould be inseretd
loc = binarySearch(a, selected, 0, j); // Move all elements after location to create space
while (j >= loc)
{
a[j + 1] = a[j];
j--;
}
a[j + 1] = selected;
}
}
// 출력
void Sort::printArray(int arr[], int n){
int i; for (i = 0; i < n; i++)
printf("%d ", arr[i]); printf("\n"); }
| 
Sort.zip