[cpp] sorting implementation

Selection Sort

• in-place sorting algorithm
• Time complexity of worst case: $O(n^2)$

#include <vector>
#include <algorithm> //for std::swap

void selectionSortRecursive(std::vector<int>& data)
{
    selectionSortRecursive(data, 0);
}

void selectionSortRecursive(std::vector<int>& data, int start)
{
    if (start < data.size()-1)
    {
    swap(data, start, findMinIdx(data, start));
    selectionSortRecursive(data, start+1);

    }
} 

void swap(std::vector<int>& data, int idx1, int min)
{
    if (idx1 != min)
    {
        int temp = data[idx1];
        data[idx1] = data[min];
        data[min] = temp;
    }
}

int findMinIdx(std::vector<int>& data, int start)
{
    int minIdx = start;
    for (int i = start; i < data.size(); ++i)
    {
        if (data[i] < data[minIdx])
        {
            minIdx = i;
        }
    }
    return minIdx;
}

Insertion Sort

• in-place sorting algorithm
• Time complexity of average/worst case: $O(n^2)$
• Time complexity of the best case: $O(n)$ if already sorted

#include <vector>

void insertionSort(std::vector<int>&data)
{
    for (int which=1; which<data.size(); ++which)
    {
        int val=data[which];
        int i=which-1;
        
        // Moving through the elements in the sorted part of the array
        while (i >= 0 && data[i] > val) {
            data[i + 1] = data[i]; // Shift the element to the right
            --i;                   // Move to the previous element
        }
        // 그 멈춘 idx의 +1 에 val값 넣기
        data[i+1] = val;
    }
}

Quick Sort

• divide-and-conquer algorithm
• Time complexity of best/average case: $O(nlog(n))$
• Time complexity of worst case: $O(n^2)$
  - Pivot 값에 따라 편향되게 분할될 때
• pivot을 중심으로 2 subset으로 나누어 pivot보다 왼쪽은 pivot보다 작은 값이 오도록, pivot보다 오른쪽은 pivot보다 큰 값이 오도록 한다.

#include <vector>
#include <iostream>

std::vector<int> quicksortSimple(std::vector<int>& data)
{
    // base case: 하나만 남으면 return!
    if (data.size() < 2)
    {
        return data;
    }
    int pivotIdx = data.size() / 2;
    int pivotValue = data[pivotIdx];

    int leftCount = 0;

    std::vector<int> left, right;

    // put data into the left/right array
    for (int i=0; i<data.size(); ++i){
        if (i==pivotIdx) continue;

        if (data[i] < pivotValue) {left.push_back(data[i]);}
        else {right.push_back(data[i]);}
    }

    left = quicksortSimple(left);
    right = quicksortSimple(right);

    left.push_back(pivotValue);  // Add the pivot to the end of 'left'
    left.insert(left.end(), right.begin(), right.end());

    return left;
}

int main() {
    // Example vector with unsorted data
    std::vector<int> data = {10, 3, 5, 7, 2, 9, 1, 6};

    // Call the quicksort function
    std::vector<int> sortedData = quicksortSimple(data);

    // Print the sorted data
    std::cout << "Sorted Data: ";
    for (int num : sortedData) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Merge Sort

• divide-and-conquer algorithm
• Time complexity of best/average/worst case: $O(n log(n))$
• Disadvantage: additional memory of $O(n)$ for new array!

#include <vector>
#include <iostream>

std::vector<int> mergee(std::vector<int>& data, std::vector<int>& left, std::vector<int>& right)
{
    int lidx=0, ridx=0;
    std::vector<int> dest;
    
    while (lidx<left.size() && ridx<right.size())
    {
        if (left[lidx] < right[ridx])
        {
            dest.push_back(left[lidx++]);
        }else{
            dest.push_back(right[ridx++]);
        }
    }
    while (lidx < left.size()){ dest.push_back(left[lidx++]);}
    while (ridx < right.size()){ dest.push_back(right[ridx++]);}
    return dest;
}

std::vector<int> mergeSort(std::vector<int>& data)
{
    if (data.size() < 2)
    {
        return data;
    }

    // split data into two subarrays of approx equal size
    int mid = data.size()/2;
    std::vector<int> left, right;

    for (int i=0; i<data.size(); ++i){
        if (i<mid){ left.push_back(data[i]); }
        else{ right.push_back(data[i]); }
    }

    left = mergeSort(left);
    right = mergeSort(right);

    std::vector<int> result = mergee(data, left, right);
    return result;
}

int main() {
    // Example vector with unsorted data
    std::vector<int> data = {10, 3, 5, 7, 2, 9, 1, 6};

    // Call the quicksort function
    std::vector<int> sortedData = mergeSort(data);

    // Print the sorted data
    std::cout << "Sorted Data: ";
    for (int num : sortedData) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

• Keypoint! while문으로 나머지 원소들 처리가 가능한 이유?

mergeSort(left) 안의

    while (lidx < left.size()){ dest.push_back(left[lidx++]);}
    while (ridx < right.size()){ dest.push_back(right[ridx++]);}

에서 나머지 원소들을 final array인 dest에 넣어준다. 이는, left/right는 이미 "정렬된 상태"의 array이기 때문에 가능하다!

Stable Selection Sort

• What is the definition of stable sort?
  - sort that preserves the input ordering of elements with equal keys!
• array 기반의 in-place algorithm으로 구현할 시, inserting을 하는 방법으로 구현할 수 있지만 이때는 $O(n^2)$의 시간복잡도를 가질 수 있다.

  • KEYPOINT! inserting을 할 때에도 시간복잡도를 $O(1)$으로 유지하기 위해, array 기반에서 linked list 기반의 구현으로 바꾸어준다!

#include <iostream>
#include <list>
#include <iterator>
#include <algorithm>

template <typename T>
typename std::list<T>::iterator getMinimum(std::list<T>& data, typename std::list<T>::iterator start) {
    auto minIt = start;
    for (auto it = std::next(start); it != data.end(); ++it) {
        if (*it < *minIt) {
            minIt = it;
        }
    }
    return minIt;
}

template <typename T>
void selectionSortStable(std::list<T>& data) {
    for (auto sortedBoundary = data.begin(); sortedBoundary != data.end();) {
        auto minIt = getMinimum(data, sortedBoundary);
        if (minIt != sortedBoundary) {
            //! splice를 통해, sortedBoundary가 가리키는 곳 앞에 data의 minIt가 가리키는 원소를 잘라 붙인다.
            //! 따라서 splice를 한 이후에도 다시 sortedBoundary가 가리키는 곳을 비교해야하므로 sortedBoundary는 그대로여야
            data.splice(sortedBoundary, data, minIt);
        }else{
        	// 최솟값이 그대로라면, 주소값 +1
            sortedBoundary++;
        }
    }
}


int main() {
    std::list<int> data = {10, 9, 5, 7, 2, 3, 1, 6};

    selectionSortStable(data);

    for (const auto& num : data) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

Multi-Key Sort

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

class Employee{
    public:
        std::string extension;
        std::string givenname;
        std::string surname;

        Employee(std::string ext, std::string given, std::string sur): extension(ext), givenname(given), surname(sur){}
};

bool compareEmployees(const Employee& a, const Employee& b)
{
    if (a.surname == b.surname)
    {
        return a.givenname < b.givenname;
    }
    return a.surname < b.surname;
}

int main()
{
    std::vector<Employee> employee_list = 
    {
        {"1234", "John", "Doe"},
        {"5678", "Alice", "Johnson"},
        {"9101", "Bob", "Doe"}
    };

    std::sort(employee_list.begin(), employee_list.end(), compareEmployees);

    for (const auto& employee : employee_list)
    {
        std::cout << employee.surname << " " << employee.givenname << " - " <<employee.extension << std::endl;
    }
    return 0;  
}

In-place Quick Sort

올바른 코드

#include <vector>
#include <iostream>

void swap(std::vector<int>&data, int idx, int destIdx)
{
    int tmp = data[destIdx];
    data[destIdx] = data[idx];
    data[idx] = tmp;
}

void quicksortSwappingRecursive(std::vector<int>& data, int start, int len)
{
    if (len < 2) return; // nothing to sort!

    int pivotIdx = start+len/2;
    int pivotValue = data[pivotIdx];
    int end = start+len;
    int curr = start;

    // swap the pivot to the end
    swap(data, pivotIdx, --end);

    // partition the rest of the array
    while (curr < end)
    {
        if (data[curr] < pivotValue)
        {
            curr++;
        }else{
            swap(data, curr, --end);
        }
    }
    // swap the pivot back to its final destination
    swap(data, end, start+len-1);

    // swap recursively
    int llen = end - start;
    int rlen = len - llen - 1;  // -1은 pivot을 빼기 위해

    if (llen >1)
    {
        quicksortSwappingRecursive(data, start, llen);
    }
    if (rlen >1)
    {
        quicksortSwappingRecursive(data, end+1, rlen);
    }
}

void quicksortSwapping(std::vector<int>& data)
{
    quicksortSwappingRecursive(data, 0, data.size());
}

int main(){
    std::vector<int> data = {10, 9, 5, 7, 2, 3, 1, 6};

    quicksortSwapping(data);

    for (const auto& num: data)
    {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

시행착오 및 주의할 점

• 최종적으로, swap함수에서 pivot을 final destination에 위치 시킨다. 이 때, 이전 end position의 계산이 잘못되어있으면 마지막 위치에 잘못들어갈 수 있다.

    // swap the pivot back to its final destination
    swap(data, end, start+len-1);

잘못된 코드 예시

잘못된 코드 부분
swap(data, pivotIdx, end--);
swap(data, curr, end--);

• 해당 예시에서는 pivot을 swap해준 후, end-- 계산을 해주는데, 이렇게 되면, final final (recursive하게 함수를 돌 때 찐 최종 end pointer는 마지막 올바른 pivotIdx의 position이 아닌 (pivotIdx-1)에 위치한다..!

void quicksortSwappingRecursive(std::vector<int>& data, int start, int len)
{
    if (len < 2) return; // nothing to sort!

    int pivotIdx = start+len/2;
    int pivotValue = data[pivotIdx];
    int end = start+len-1;
    int curr = start;

    // swap the pivot to the end
    swap(data, pivotIdx, end--);

    std::cout << "inside recursive: " << "pivotValue: " << pivotValue << " curr: " << curr << " end: " << end << std::endl;
    for (const auto& num: data)
    {
        std::cout << num << " -> ";
    }
    std::cout << std::endl;

    // partition the rest of the array
    while (curr < end)
    {
        if (data[curr] < pivotValue)
        {
            std::cout << "not swapping" << std::endl;
            curr++;
        }else{
            swap(data, curr, end--);
        }
    }
    .
    .
    .
    // rest of them are the same

잘못된 코드 예시 결과

int main(){
    std::vector<int> data = {10, 9, 5, 7, 2, 3, 1, 6};

    quicksortSwapping(data);

    for (const auto& num: data)
    {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

결과: 1 2 3 5 6 7 9 10