Sorting Alogorithms

생성일: 2021년 12월 3일 오후 6:33

SelectionSort.cpp

• Straight Selection Sort

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

BubbleSort.cpp

• Bubble Sort

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

InsertionSort.cpp

• Insertion Sort

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

HeapSort.cpp

• Heap Sort

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

QuickSort.cpp

// 첫번재 아이템을 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);
  }
}

QuickSort2.cpp

//중앙에 위치한 아이템을 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);
  }
}

MergeSort.cpp

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

RadixSort

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