정렬: 배열에 저장된 요소들을 오름차순이나 내림차순으로 재배치하는 과정.

Selection sort( 선택정렬 )

배열을 정렬된 부분과 정렬되지 않은 부분으로 나눠서 매 회차마다 정렬되지 않은 부분에서 가장 작은 요소를 찾아서 정렬된 부분의 끝에 추가함. 시간복잡도 O(N^2)

template <class ItemType>
int MinIndex(ItemType values[], int start, int end)
// Post: Function value = index of the smallest value
// in values [start] . . values [end].
{
    int indexOfMin = start;
    for (int index = start + 1; index <= end; index++)
        if (values[index] < values[indexOfMin])
            indexOfMin = index;
    return indexOfMin;
}

template <class ItemType>
void SelectionSort(ItemType values[], int numValues)
// Post: Sorts array values[0 . . numValues-1 ]
// into ascending order by key
{
    int endIndex = numValues - 1;
    for (int current = 0; current < endIndex; current++)
        Swap(values[current], values[MinIndex(values, current, endIndex)]);
}

Bubble sort

배열의 인접한 요소들을 비교하고 필요에 따라 교환하여 정렬하는 알고리즘. 가장 큰 요소가 배열의 끝으로 버블링되어 올라간다. 시간복잡도 O(N^2)

template <class ItemType> void BubbleSort(ItemType values[], int numValues) {
    int current = 0;
    while (current < numValues - 1) {
        BubbleUp(values, current, numValues - 1);
        current++;
    }
}

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

Insertion Sort

삽입정렬은 배열의 요소를 하나씩 정렬된 부분에 삽입하여 정렬하는 방법. 카드게임에서 카드를 정렬하는 방식과 유사함. 시간복잡도 O(N^2)

template <class ItemType>
void InsertItem(ItemType values[], int start, int end) {
    bool finished = false;
    int current = end;
    bool moreToSearch = (current != start);
    while (moreToSearch && !finished) {
        if (values[current] < values[current - 1]) {
Swap(values[current], values[current - 1]);
current--;
moreToSearch = (current != start);
        } else
            finished = true;
    }
}
template <class ItemType> void InsertionSort(ItemType values[], int numValues) {
    // ascending order by key
    for (int count = 0; count < numValues; count++)
        InsertItem(values, 0, count);
}

Complex Sorts

선택, 버블, 삽입정렬은 simple한 sort알고리즘으로 시간복잡도가 O(N^2)이지만 Quick, Merge, Heap Sort는 O(nlogn)이다.

Heap Sort

힙 정렬은 힙 자료구조를 사용해서 배열을 정렬한다.

1. 루트를 배열의 끝에 있는 정렬된 부분으로 이동시킨다. 이를 위해서 루트 element를 배열의 마지막 요소와 교환한다.
2. 루트에 있는 요소를 제거한 후 나머지 요소로 힙을 재구성한다. 이 과정에서 새로운 루트가 올바른 위치로 이동한다→ 다음으로 큰 요소가 루트에 온다
3. 이 과정을 정렬되지 않은 요소가 없을때까지 반복한다.

힙 정렬은 추가적인 메모리 공간 없이 정렬이 가능하다.