10. Sorting and Searching Algorithms

Selection Sort

1. 일단 전체에서 가장 작은 값 찾아서 앞으로 가져옴=> 첫번째는 sorted 나머지는 unsorted(최솟값이랑 현 위치만 바꾸고 나머지는 순서 바뀌지 않음)
2. unsorted에서 가장 작은 값 찾아서 또 땡겨옴 => 두번째까지 sorted 나머지 unsorted
3. 위 과정 반복

시간복잡도: 갯수가 n개일때 비교횟수는 n*(n-1)/2이므로 O(n**2)이다.

template<class ItemType>
int MinIndex(ItemType values[], int startIndex, int endIndex)
// Post: Returns the index of the smallest value in
//       values[startIndex]..values[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)
// Post: The elements in the array values are sorted by key.
{
  int endIndex = numValues-1;
  for (int current = 0; current < endIndex; current++)
    Swap(values[current], values[MinIndex(values, current, endIndex)]);
}

Bubble Sort

현재위치에서 이웃을 비교해서 올바르지 않은 순서면 자리바꿈

1. 맨 끝 index와 index-1값 비교 후 자리 정렬(버블처럼 바꿔줌)
2. index = 1 될때까지 함. 그려면 0번째는 가장작은 값으로 정렬되어 있을 거임
3. 이번에는 index가 끝 값일때부터 2일때까지 함 그럼 두개가 정렬될 꺼임
4. 이렇게 반복하면 정렬됨

시간복잡도는 O(N**2)

template<class ItemType>
void BubbleUp(ItemType values[], int startIndex, int endIndex)
// Post: Adjacent pairs that are out of order have been 
//       switched between values[startIndex]..values[endIndex]
//       beginning at values[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)
// Post: The elements in the array values are sorted by key.
{
  int current = 0;

  while (current < numValues - 1)
  {
    BubbleUp(values, current, numValues-1);
    current++;
  }
}

Insertion Sort

1. 0번째 값을 들어갈 알맞은 위치에 삽입
2. 1번째 값을 0번째 값들과 비교해서 들어갈 알맞은 위치(0~1)에 삽입
3. 2번째 값을 0,1번째 값들과 비교해서 들어갈 알맞은 위치(0~2)에 삽입
4. 끝까지 반복

template<class ItemType>
void InsertItem(ItemType values[], int startIndex, int endIndex)
// Post: values[0]..values[endIndex] are now sorted.
{
  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)
// Post: The elements in the array values are sorted by key.
{
  for (int count = 0; count < numValues; count++)
    InsertItem(values, 0, count);
}

Heap Sort

root값이 최대임을 이용한 정렬

1. root값을 맨 아래 오른쪽 과 바꾸고 바뀐 root를 reheapDown해준다.
2. root 값을 또 맨아래 오른쪽(이전에 바꾼거 그전꺼)과 바꾸고 reheapDown
3. 이거 반복하면 array에 알아서 정렬되어 있음

만약에 tree가 heap구조가 아니라면?? => 개귀찮지만 heap 구조를 만들어준다음에 정렬을 해야함

시간복잡도:
heap으로 만드는데 걸리는 시간: (N/2)*O(logN) (리프아닌거 갯수*트리 높이) 
heap인거 다시 진짜 정렬하는데 걸리는 시간: (N-1)*O(logN) (노드갯수*트리높이)
최종 복잡도: O(n*logn)

template<class ItemType>
void ReheapDown(ItemType elements[], int root, int bottom)
// Post: Heap property is restored.
{
  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)
// Pre:  Struct HeapType is available.
// Post: The elements in the array values are sorted by key.
{
  int index;

  // Convert the array of values into a heap.
  for (index = numValues/2 - 1; index >= 0; index--)
    ReheapDown(values, index, numValues-1);

  // Sort the array.
  for (index = numValues-1; index >=1; index--)
  {
    Swap(values[0], values[index]);
    ReheapDown(values, 0, index-1);
  }
}

Quick Sort

쪼개면서 정렬하는 것이다. 

1. split value를 정한다. 
2. split value를 기준으로 큰거하고 작은 걸 찾고 split value가 있어야 할 위치에 놓는다.
   1. low high 가운데로 모이다가 low high가 갈수없을때 값을 바꿔줌. 
   2. 그러다가 high가 low보다 작은 인덱스 값을 가질때 split value로 바꿔줌
3. 이제 split value를 기준으로 두 덩어리가 생길 텐데 각 덩어리에서 split value를 찾고 2에서 했던 걸 반복한다. 

시간복잡도는 최상의 경우 O(n*logn)이다. 
최상의 경우는 쪼갰을 때 항상 반반씩 쪼개지는 상황인데 그러면 쪼개지는 층이 logn개이고 각 층별 비교횟수가 n이라서 n*logn이다.
최악의 경우는 O(n*n)이다.
최악의 경우는 쪼갰는데 한덩어리가 1인 경우이다. 그러면 층이 n개가 생길 것이고 층별 비교횟수는 여전히 n이기때문에 n*n이다.

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)
  {
    int splitPoint;

    Split(values, first, last, splitPoint);
    // values[first]..values[splitPoint-1] <= splitVal
    // values[splitPoint] = splitVal
    // values[splitPoint+1]..values[last] > splitVal

    QuickSort(values, first, splitPoint-1);
    QuickSort(values, splitPoint+1, last);
  }
}

Merge Sort

일단 쪼개놓고 보는 전략

1. 일단 싹다 쪼갠다.
2. 합치면서 비교한다.(예. 2 덩어리끼리 비교할때 작은값부터 비교해서 큰 값까지 비교)
3. 다 합치면 정렬이 되어있다. 

시간복잡도는 층이 log(N)이고 각 층별 비교횟수가 N이라서 N*log(N) 이다.

template<class ItemType>
void Merge (ItemType values[], int leftFirst, int leftLast, 
     int rightFirst, int rightLast)
// Post: values[leftFirst]..values[leftLast] and 
//       values[rightFirst]..values[rightLast] have been merged.
//       values[leftFirst]..values[rightLast] is now sorted.
{
  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)
// Post: The elements in values are sorted by key.
{
  if (first < last)
  {
    int middle = (first + last) / 2;
    MergeSort(values, first, middle);
    MergeSort(values, middle + 1, last);
    Merge(values, first, middle, middle + 1, last);
  }
}

comparison of sorting algorithms

Stability

Stable sort: 똑같은 요소의 순서를 보존해주는 sort(예 8,2,3,8을 sort했을때 먼저왔던 8이 여전히 먼저와야됨)
heapSort,quick은 stable이 아니니 알아둘 것.

Searching

Linear Searching: 처음부터 찾는 것
High-Probability Ordering: 찾을 확률이 높은 걸 앞에 두는 것
Key Ordering: 없는 데 찾지 않도록 해줌

Hashing

파이썬에 dictionary와 비슷한것이라고 생각하면 편하다.

보기와 같이 인덱스당 값들이 저장되고 값을 물으면 인덱스를 뱉는다. 저장할 때는 hash function을 통해 저장될 위치를 정한다.
그런데 저장할 위치에 이미 값이 존재하면 collision이 발생한다. 해결책은 다음과 같다.

• linear probing
  존재하는 자리 다음자리에 넣어주는 것, 그러면 찾을때는 linear search처럼 찾는다. 근데 만약 찾는 위치와 원래 있어야 할 위치사이의 값중 하나가 삭제되어 empty가 존재할경우 값을 찾을 수 없다는 문제가 있다.
• Rehasing
  quadratic probing, random probing 등 다른 해시함수를 통해 위치를 지정하는 것
• Buckets and chaining
  bucket은 어레이를 2차원으로 만들어서 자리를 늘리는 거고 chaining은 어레이를 linked list로 해서 자리를 늘리는 거

// This file contains the individual functions from the text.
// Note that there are two InsertItems
int ItemType::Hash() const
// Post: Returns an integer between 0 and MAX_ITEMS -1.
{
  return (idNum % MAX_ITEMS);
}
template<class ItemType>
void ListType<ItemType>::RetrieveItem(ItemType& item)
// Post: Returns the element in the array at position 
//       item.Hash().
{
  int location;

  location = item.Hash();
  item = info[location];
}
template<class ItemType>
void ListType<ItemType>::InsertItem(ItemType item)
// Post: item is stored in the array at position item.Hash().
{
  int location;

  location = item.Hash();
  info[location] = item;
  length++;
}
template<class ItemType>
void ListType<ItemType>::InsertItem(ItemType item)
// Post: item is stored in the array at position item.Hash()
//       or the next free spot.
{
  int location;
 
  location = item.Hash();
  while (info[location] != emptyItem)
    location = (location + 1) % MAX_ITEMS;
  info[location] = item;
  length++;
}
template<class ItemType>
void ListType<ItemType>::RetrieveItem(ItemType& item, bool& 
found)
{
  int location;
  int startLoc;
  bool moreToSearch = true;

  startLoc = item.Hash();
  location = startLoc;
  do
  {
    if (info[location] == item || info[location] == emptyItem)
      moreToSearch = false;
    else
      location = (location + 1) % MAX_ITEMS;
  } while (location != startLoc && moreToSearch);
  found = (info[location] == item);
  if (found)
    item = info[location];
}

Radix Sort

자릿수 끼리 정렬하는 것
ex) 3자릿수, 첫번째자리 정렬->두번째자리 정렬->세번째자리 정렬(queue 사용)

시간복잡도: O(n)

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