생성일: 2021년 12월 3일 오후 6:33
template<class ItemType>
int MinIndex(ItemType values[], int startIndex, int endIndex)
{
int indexOfMin = startIndex;
for (int index = startIndex + 1; index <= endIndex; index++)
if (values[index] < values[indexOfMin])
indexOfMin = index;
return indexOfMin;
}
template<class ItemType>
void SelectionSort(ItemType values[], int numValues)
{
int endIndex = numValues-1; //마지막 남은 아이템은 어차피 제일 큰 아이템이라 검사 X
for (int current = 0; current < endIndex; current++)
Swap(values[current], values[MinIndex(values, current, endIndex)]);
}
template<class ItemType>
void BubbleUp(ItemType values[], int startIndex, int endIndex)
{
for (int index = endIndex; index > startIndex; index--)
if (values[index] < values[index-1])
Swap(values[index], values[index-1]);
}
template<class ItemType>
void BubbleSort(ItemType values[], int numValues)
{
int current = 0;
while (current < numValues - 1) // 마지막 아이템은 검사할 필요 X
{
BubbleUp(values, current, numValues-1);
current++;
}
}
template<class ItemType>
void InsertItem(ItemType values[], int startIndex, int endIndex)
{
bool finished = false;
int current = endIndex;
bool moreToSearch = (current != startIndex);
while (moreToSearch && !finished)
{
if (values[current] < values[current-1])
{
Swap(values[current], values[current-1]);
current--;
moreToSearch = (current != startIndex);
}
else
finished = true;
}
}
template<class ItemType>
void InsertionSort(ItemType values[], int numValues)
{
for (int count = 0; count < numValues; count++)
InsertItem(values, 0, count);
}
template<class ItemType>
void ReheapDown(ItemType elements[], int root, int bottom)
{
int maxChild;
int rightChild;
int leftChild;
leftChild = root*2+1;
rightChild = root*2+2;
if (leftChild <= bottom)
{
if (leftChild == bottom)
maxChild = leftChild;
else
{
if (elements[leftChild] <= elements[rightChild])
maxChild = rightChild;
else
maxChild = leftChild;
}
if (elements[root] < elements[maxChild])
{
Swap(elements[root], elements[maxChild]);
ReheapDown(elements, maxChild, bottom);
}
}
}
template<class ItemType>
void HeapSort(ItemType values[], int numValues)
{
int index;
// 비정렬 어레이를 heap으로 바꿔 줌, 여기서 index = numValues/2 - 1 는 non-terminal 노드 중 가장 마지막 노드
for (index = numValues/2 - 1; index >= 0; index--)
ReheapDown(values, index, numValues-1);
// heap이 된 어레이를 정렬시키기
for (index = numValues-1; index >=1; index--)
{
Swap(values[0], values[index]);
ReheapDown(values, 0, index-1);
}
}
// 첫번재 아이템을 pivot으로 잡을때의 구현
template <class ItemType>
void Split(ItemType values[], int first, int last, int& splitPoint)
{
ItemType splitVal = values[first];
int saveFirst = first;
bool onCorrectSide;
first++;
do
{
onCorrectSide = true;
while (onCorrectSide) // Move first toward last.
if (values[first] > splitVal)
onCorrectSide = false;
else
{
first++;
onCorrectSide = (first <= last);
}
onCorrectSide = (first <= last);
while (onCorrectSide) // Move last toward first.
if (values[last] <= splitVal)
onCorrectSide = false;
else
{
last--;
onCorrectSide = (first <= last);
}
if (first < last)
{
Swap(values[first], values[last]);
first++;
last--;
}
} while (first <= last);
splitPoint = last;
Swap(values[saveFirst], values[splitPoint]);
}
template<class ItemType>
void QuickSort(ItemType values[], int first, int last)
{
if (first < last) // general case
{
int splitPoint;
Split(values, first, last, splitPoint);
QuickSort(values, first, splitPoint-1);
QuickSort(values, splitPoint+1, last);
}
}
//중앙에 위치한 아이템을 pivot으로 잡을 때의 구현
template <class ItemType>
void Split2(ItemType values[], int first, int last,
int& splitPt1, int& splitPt2)
{
ItemType splitVal = values[(first+last)/2];
bool onCorrectSide;
do
{
onCorrectSide = true;
while (onCorrectSide) // Move first toward last.
if (values[first] >= splitVal)
onCorrectSide = false;
else
first++;
onCorrectSide = true;
while (onCorrectSide) // Move last toward first.
if (values[last] <= splitVal)
onCorrectSide = false;
else
last--;
if (first <= last)
{
Swap(values[first], values[last]);
first++;
last--;
}
} while (first <= last);
splitPt1 = first;
splitPt2 = last;
}
template <class ItemType>
void QuickSort2(ItemType values[], int first, int last)
{
if (first < last) // general case
{
int splitPt1;
int splitPt2;
Split2(values, first, last, splitPt1, splitPt2);
if (splitPt1 < last)
QuickSort2(values, splitPt1, last);
if (first < splitPt2)
QuickSort2(values, first, splitPt2);
}
}
template<class ItemType>
void Merge (ItemType values[], int leftFirst, int leftLast,
int rightFirst, int rightLast)
{
ItemType tempArray[SIZE];
int index = leftFirst;
int saveFirst = leftFirst;
while ((leftFirst <= leftLast) && (rightFirst <= rightLast))
{
if (values[leftFirst] < values[rightFirst])
{
tempArray[index] = values[leftFirst];
leftFirst++;
}
else
{
tempArray[index] = values[rightFirst];
rightFirst++;
}
index++;
}
while (leftFirst <= leftLast)
// Copy remaining items from left half.
{
tempArray[index] = values[leftFirst];
leftFirst++;
index++;
}
while (rightFirst <= rightLast)
// Copy remaining items from right half.
{
tempArray[index] = values[rightFirst];
rightFirst++;
index++;
}
for (index = saveFirst; index <= rightLast; index++)
values[index] = tempArray[index];
}
template<class ItemType>
void MergeSort(ItemType values[], int first, int last)
{
if (first < last)
{
int middle = (first + last) / 2;
MergeSort(values, first, middle);
MergeSort(values, middle + 1, last);
Merge(values, first, middle, middle + 1, last);
}
}
// This file contains the functions for Radix Sort.
// In the RadixSort function, the parameters have these meanings:
//
// values is the array to be sorted
// numValues is the size of the array to be sorted
// numPositions is the size of the key measured in digits, characters etc..
// If keys have 3 digits, this has the value 3,
// If 10 digit keys, this has the value 10.
// If word keys, then this is the number of characters in
// the longest word.
// radix is the radix of the key, 10 in the case of decimal digit keys
// 26 for case-insensitive letters, 52 if case-sensitive letters.
#include "QueType.h"
template<class ItemType>
void RadixSort(ItemType values, int numValues,
int numPositions, int radix)
// Post: Elements in values are in order by key.
{
QueType<int> queues[10];
// With default constructor, each queue size is 500
int whichQueue;
for (int position = 1; position <= numPositions; position++)
{
for (int counter = 0; counter < numValues; counter++)
{
whichQueue = values[counter].SubKey(position);
queues[whichQueue].Enqueue(values[counter]);
}
CollectQueues(values, queues, radix);
}
}
template<class ItemType>
void CollectQueues(ItemType values[], QueType<ItemType>
queues[], int radix)
// Post: queues are concatanated with queue[0]'s on top and
// queue[9]'s on the bottom and copied into values.
{
int index = 0;
ItemType item;
for (int counter = 0; counter < radix; counter++)
{
while (!queues[counter].IsEmpty())
{
queues[counter].Dequeue(item);
values[index] = item;
index++;
}
}
}