Sorting Algorithm

BinarySearch.cpp

#include <iostream>

using namespace std;


int binary_search(int array[], const int size, const int elem)
{
    int left = 0;
    int right = size;

    while (left < right)
    {
        const int mid = left + (right - left) / 2; // avoid (left + right) to be overflow.
        cout << "mid: " << mid << endl;
        if (array[mid] == elem)
        {
            return mid;
        }
        else if (array[mid] > elem)
        {
            right = mid;
        }
        else
        {
            left = mid + 1;
        }
    }
    return -1;
}

static int nums[100];

int main(int argc, char *argv[])
{
    int num;
    int count = 0;
    cin >> count;
    for (int i = 0; i < count; ++i)
    {
        cin >> nums[i];
    }

    int search_elem;
    cin >> search_elem;

    cout << "result:" << binary_search(nums, count, search_elem) << endl;
    
    return 0;
}

BubbleSort.cpp

template<typename T>
void swap(T& a, T& b)
{
    T tmp = a;
    a = b;
    b = tmp;
}


template<typename T>
void BubbleSort(T array[], const size_t size)
{
    for (int i = 0; i < size - 1; ++i)
    {
        for (int j = 0; j < size - i - 1; ++j)
        {
            if (array[j] > array[j + 1])
            {
                swap(array[j], array[j + 1]);
            }
        }
    }
}


struct ListNode
{
    ListNode* next;
    int data;
};

void BubbleSort(ListNode** node)
{
    int size = 0;
    ListNode* cur = *node;
    while (cur != NULL)
    {
        ++size;
        cur = cur->next;
    }

    ListNode** prev = NULL ;
    for (int i = 0; i < size - 1; ++i)
    {
        prev = node;
        for (int j = 0; j < size - i - 1; ++j, prev = &((*prev)->next))
        {
            cur = *prev;
            if (cur->data > cur->next->data)
            {
                *prev = cur->next;
                cur->next = (*prev)->next;
                (*prev)->next = cur;
            }
        }
    }    
}

BucketSort.cpp

#include <iostream>

using namespace std;


template<typename T>
void BucketSort(T array[], const int size, const int max)
{
    if (size < 2)
    {
        return;
    }

    const int range = max + 10; // ******
    T* count_array = new T[range];
    memset(count_array, 0, sizeof(T) * range);

    for (int i = 0; i < size; ++i)
    {
        ++count_array[array[i]];
    }

    for (int i = 0, index = 0; i < range; ++i)
    {
        for (int j = 0; j < count_array[i] ; ++j)
        {
            array[index++] = i;
        }
    }

    delete [] count_array;
}

struct Node
{
    Node* next;
    int data;

    Node(const int d, Node* n)
        : data(d), next(n)
    {}

    ~Node()
    {
        if (next != NULL)
        {
            delete next;
        }
    }
};


int value_cmp(const void* a, const void* b)
{
    return *(const int*)a - *(const int*)b;
}

void BucketSort(int array[], const int size, const int max)
{
    static const int SIZE = 100;
    static Node* buckets[SIZE + 10];
    memset(buckets, 0, sizeof(buckets));

    const int bucket_size = (max + SIZE - 1) / SIZE; // *****

    for (int i = size - 1; i >= 0; --i) // backward
    {
        const int bucket_num = array[i] / bucket_size;
        buckets[bucket_num] = new Node(array[i], buckets[bucket_num]);
    }

    int index = 0;
    for (int i = 0; i < SIZE + 10; ++i)
    {
        int count = 0;
        int start_index = index;
        Node* cur = buckets[i];
        while (cur != NULL)
        {
            array[index++] = cur->data;
            cur = cur->next;
            ++count;
        }
        if (count > 0)
            qsort(array + start_index, count, sizeof(array[0]), &value_cmp);
    }
}


const int MAX_SIZE = 100;
int input_nums[MAX_SIZE];

int main(int argc, char *argv[])
{
    int num;
    int count = 0;
    int max = 0;
    while (cin >> num && count < MAX_SIZE)
    {
        input_nums[count++] = num;
        if (num > max)
        {
            max = num;
        }
    }

    BucketSort(input_nums, count, max);

    for (int i = 0; i < count; ++i)
    {
        cout << input_nums[i] << ' ';
    }
    cout << endl;
    
    return 0;
}

CountingSort.cpp

#include <iostream>

using namespace std;


template<typename T>
void CountingSort(T array[], const int size, const int max)
{
    if (size < 2)
    {
        return;
    }

    const int range = max + 10; // ******
    T* count_array = new T[range];
    T* tmp_output = new T[size];
    memset(count_array, 0, sizeof(T) * range);

    for (int i = 0; i < size; ++i)
    {
        ++count_array[array[i]];
    }

    int total = 0;
    int old_total = 0;
    for (int i = 0; i < range; ++i)
    {
        old_total = count_array[i];
        count_array[i] = total;
        total += old_total;
    }

    for (int i = 0; i < size; ++i)
    {
        tmp_output[count_array[array[i]]] = array[i];
        ++count_array[array[i]];
    }

    for (int i = 0; i < size; ++i)
    {
        array[i] = tmp_output[i];
    }
    
    delete [] count_array;
    delete [] tmp_output;
}

const int MAX_SIZE = 100;
int input_nums[MAX_SIZE];

int main(int argc, char *argv[])
{
    int num;
    int count = 0;
    int max = 0;
    while (cin >> num && count < MAX_SIZE)
    {
        input_nums[count++] = num;
        if (num > max)
        {
            max = num;
        }
    }

    CountingSort(input_nums, count, max);

    for (int i = 0; i < count; ++i)
    {
        cout << input_nums[i] << ' ';
    }
    cout << endl;
    
    return 0;
}

HeapSort.cpp

// start at 0

int left_child(const int i)
{
    return i * 2 + 1;
}

int right_child(const int i)
{
    return (i + 1) * 2;
}

int parent(const int i)
{
    return (i - 1) >> 1;
}

void max_heapify(vector<int>& nums, int i, const int size)
{
    while (i < size)
    {
        const int left = left_child(i);
        const int right = right_child(i);
        
        int max = i;
        if (left < size && nums[max] < nums[left])
        {
            max = left;
        }
        if (right < size && nums[max] < nums[right])
        {
            max = right;
        }
        
        if (max != i)
        {
            std::swap(nums[max], nums[i]);
            i = max;
        }
        else
        {
            return;
        }
    }
}

void make_heap(vector<int>& nums)
{
    const int max = parent(nums.size() - 1);
    
    for (int i = max; i >= 0; --i)
    {
        max_heapify(nums, i, nums.size());
    }
}

void heapsort(vector<int>& nums)
{
    for (int i = nums.size() - 1; i > 0; --i)
    {
        std::swap(nums[i], nums[0]);
        max_heapify(nums, 0, i);
    }
}

void heap_increase(vector<int>& nums, int i, const int new_key)
{
    if (nums[i] < new_key)
    {
        nums[i] = new_key;
        int pa = 0;
        while (i > 0 && nums[pa = parent(i)] < nums[i])
        {
            std::swap(nums[pa], nums[i]);
            i = pa;
        }
    }
}

void heap_insert(vector<int>& nums, int n)
{
    nums.push_back(n);
    if (nums.size() == 1)
    {
        return;
    }
    nums.back() = std::min(n, nums[parent(nums.size() - 1)] - 1);
    heap_increase(nums, nums.size() - 1, n);
}

int heap_pop_max(vector<int>& nums)
{
    int max = nums[0];
    if (nums.size() > 0)
    {
        nums[0] = nums.back();
        nums.pop_back();
        max_heapify(nums, 0, nums.size());
    }
    
    return max;
}

ListBucketSort.cpp

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;


struct Node
{
    Node(const int d)
        : data(d), next(NULL)
    {}

    ~Node()
    {
        if (next != NULL)
        {
            delete next;
        }
    }

    int data;
    Node* next;
};


void Dump(Node* list)
{
    for (Node* cur = list; cur != NULL; cur = cur->next)
    {
        cout << cur->data << ' ';
    }
    cout << endl;
}

Node* Reverse(Node* node, Node* result_list)
{
    if (node->next == NULL)
    {
        node->next = result_list;
        return node;
    }
    else
    {
        Node* next = node->next;
        node->next = result_list;
        return Reverse(next, node);
    }
}

// iterative reverse

Node* Reverse(Node* list)
{
    Node* result = NULL;
    Node* cur = list;
    Node* next = NULL;
    while (cur != NULL)
    {
        next = cur->next;
        cur->next = result;
        result = cur;
        cur = next;
    }
    return result;
}

Node* BucketSort(Node* node, const int max)
{
    if (node == NULL || node->next == NULL)
    {
        return node;
    }
    
    // reverse the linked list
    Node* list = Reverse(node, NULL);
    Dump(list);
    static const int MAXN = 100;
    static Node* buckets[MAXN];
    memset(buckets, 0, (max + 1) * sizeof(Node*));
    for (Node* cur = list; cur != NULL;)
    {
        const int cur_value = cur->data;
        Node* tmp = cur;
        cur = cur->next;
        tmp->next = buckets[cur_value];
        buckets[cur_value] = tmp;
    }
    
    Node* new_list = NULL;
    Node** cur_ptr = &new_list;
    for (int i = 0; i < max + 1; ++i)
    {
        if (buckets[i] != NULL)
        {
            *cur_ptr = buckets[i];
            while (*cur_ptr != NULL)
            {
                cur_ptr = &((*cur_ptr)->next);
            }
        }
    }
    return new_list;
}

int main(int argc, char *argv[])
{
    Node* list = NULL;
    Node** cur_ptr = &list;
    int num;
    while (cin >> num)
    {
        Node* node = new Node(num);
        *cur_ptr = node;
        cur_ptr = &((*cur_ptr)->next);
    }

    list = BucketSort(list, 100);

    Dump(list);

    delete list;
    
    return 0;
}

QuickSort.cpp

int partition(vector<int>& nums, int begin, int end)
{
    int pivot = begin;
    int less_index = begin + 1;
    for (int i = less_index; i <= end; ++i)
    {
        if (nums[i] < nums[pivot])
        {
            std::swap(nums[less_index], nums[i]);
            ++less_index;
        }
    }
    std::swap(nums[less_index - 1], nums[pivot]);
    return less_index - 1;
}

void dutch_partition(vector<int>& nums, int begin, int end, int& pivot_begin, int& pivot_end)
{
    int pivot = begin;
    int less_index = begin + 1;
    int greater_index = end;
    for (int i = less_index; i <= greater_index; )
    {
        if (nums[i] < nums[pivot])
        {
            std::swap(nums[less_index], nums[i]);
            ++less_index;
            ++i;
        }
        else if (nums[i] > nums[pivot])
        {
            std::swap(nums[greater_index], nums[i]);
            --greater_index;
        }
        else // equal
        {
            ++i;
        }
    }
    std::swap(nums[less_index - 1], nums[pivot]);
    pivot_begin = less_index - 1;
    pivot_end = greater_index;
}

void quicksort_impl(vector<int>& nums, int begin, int end)
{
    if (end - begin > 0)
    {
        int pivot = partition(nums, begin, end);
        quicksort_impl(nums, begin, pivot - 1);
        quicksort_impl(nums, pivot + 1, end);
        
        // or using dutch_partition
        //int pivot_begin = 0, pivot_end = 0;
        //dutch_partition(nums, begin, end, pivot_begin, pivot_end);
        //quicksort_impl(nums, begin, pivot_begin - 1);
        //quicksort_impl(nums, pivot_end + 1, end);
    }
}

void quicksort(vector<int>& nums)
{
    quicksort_impl(nums, 0, nums.size() - 1);
}

struct Cmp
{
    int m_v;
    Cmp(int v) : m_v(v) {}
    bool operator()(int v)
    {
        return v < m_v;
    }
};

int std_partition(vector<int>& nums, int begin, int end)
{
    int pivot = begin;
    if (end - begin > 0)
    {
        Cmp cmp(nums[begin]);
        int pivot = std::partition(nums.begin() + begin + 1, nums.begin() + end + 1, cmp) - nums.begin() - 1;
        std::swap(nums[begin], nums[pivot]);
    }
    return pivot;
}