Problem 2.1. Write a merge sort in a bottom-up style (no recursive calls). Your code
should allow inputs of all lengths, that is, not just for inputs of 2k length.
Problem 2.2. (Slide no. 13 in the quicksort lecture) Implement a variant of quicksort
combining the skill of median-3 partition and using insertion sort on small subfiles.
The purpose is to decide the best parameter M.
When you submit your homework, you should include the following:
(a) Source code.
(b) A few examples (including a best case, a worst case and an average case;
also, inputs of different lengths for merge sort) and their sorting results, to
test the code’s accuracy.
(c) The environment that you work on, for instance, Borland C++, under
regular PC, etc.
(d) (For mergesort only) What is the complexity of your algorithm? Give your
answer as exact as possible (not just an asymptotical answer).
(e) (For quicksort only) The curve on the speed of your code vs. the choice of
M.

 

merge sort支援各種stl標準容器
quick sort v2只支援vector
quick sort v1支援各種stl標準容器,但慢v2約100倍
v3增加對一般陣列的支援
http://damody.googlecode.com/files/Algorithms_hw1.rar
http://damody.googlecode.com/files/Algorithms_hw1%20v2.rar
http://damody.googlecode.com/files/Algorithms_hw1v3.rar

使用方法

int a[8]  = {1,5,3,6,7,1,2,5};
merge_sort(a,a+8);
quick_sort(a,a+8);

merge_sort(vector.begin(),vector.end());
quick_sort(vector.begin(),vector.end());

非常直覺吧!
有參考看了stl的演算法實作,真的是詳細快速呀!

1. merge sort

#pragma once
#include <vector>

template< class Iterator >
void merge_sort(Iterator begin, Iterator end)
{
    typedef std::vector<typename std::iterator_traits<Iterator>::value_type> ObjVector;
    int step = 2;
    Iterator now, beg1, beg2, end2;
    ObjVector ovector;
    bool isStepBiggerThanSize = false;
    for (;!isStepBiggerThanSize;) // O(lg n)
    {
        now = begin;
        int index;
        isStepBiggerThanSize = true;
        for (;now != end;) // search left middle right's index O(n)
        {
            beg1 = now;
            beg2 = end;
            for (index = 0;now != end;now++)
            {
                if (index == step)
                    break;
                else if (index == step/2)
                {
                    isStepBiggerThanSize = false;
                    beg2 = now;
                }
                index++;
            }
            if (beg2 == end) break;
            end2 = now;
            merge(beg1, beg2, end2, ovector,  // O(step)
                std::less_equal< typename std::iterator_traits<Iterator>::value_type >()
                );
        }
        step*=2;
    }
    // O(lg n) * O(all step) = O(lg n) * O(n) = O(nlg n)
}

template< class Iterator, class Compare >
void merge(Iterator beg1, Iterator beg2, Iterator end2,
               std::vector<typename std::iterator_traits<Iterator>::value_type> ovector,
               Compare cmp)
{
    typedef std::vector<typename std::iterator_traits<Iterator>::value_type> ObjVector;
    ovector.clear();

    Iterator end1 = beg2, start = beg1;
    for (;beg1 != end1 && beg2 != end2;)
    {
        if (cmp(*beg1, *beg2))
            ovector.push_back(*beg1++);
        else
            ovector.push_back(*beg2++);
    }
    while (beg1 != end1)
        ovector.push_back(*beg1++);
    while (beg2 != end2)
        ovector.push_back(*beg2++);
    for (ObjVector::iterator it = ovector.begin();start != end2;it++)
        *start++ = *it;
}




2. quick sort

#pragma once
#include <functional>
#include <algorithm>
#include <iterator>

static int g_M = 5;
template<class _RanIt> inline
void Med3(_RanIt _First, _RanIt _Mid, _RanIt _Last)
{    // sort median of three elements to middle
    if ((*_Mid< *_First))
        std::iter_swap(_Mid, _First);
    if ((*_Last< *_Mid))
        std::iter_swap(_Last, _Mid);
    if (*_Mid< *_First)
        std::iter_swap(_Mid, _First);
}
template< class Iterator, class Compare>
inline void quick_sort_median_3_partition( Iterator beg, Iterator end, Compare cmp ) {
    if( beg != end && (end - beg) > 0) {
        Iterator left  = beg;
        Iterator right = end;
        Iterator pivot = left, pivot2 = right;
        Iterator mid = beg + (end-beg)/2;
        // easy sort pivot, pivot2, mid
        Med3(pivot, mid, pivot2);
        while( left != right ) {
            if( cmp( *left, *mid ) ) {
                ++left;
            } else {
                while( (right != left) && cmp( *mid, *right ) )
                    right--;
                if (right != left)
                    std::iter_swap( left, right );
            }
        }
        if (cmp( *mid, *left ))
            --left;
        if (cmp(*left, *beg))
            std::iter_swap( beg, left );
        if (left - beg < g_M)
            std::_Insertion_sort(beg, left);
        else
            quick_sort_median_3_partition( beg,  left, cmp );
        if (end - right < g_M)
            std::_Insertion_sort(right, end);
        else
            quick_sort_median_3_partition( right,  end, cmp);
    }
}
template< class Iterator >
inline void quick_sort( Iterator begin, Iterator end) {
    quick_sort_median_3_partition( begin, --end,
        std::less_equal< typename std::iterator_traits<Iterator>::value_type>()
        );
}





arrow
arrow
    全站熱搜

    讓地獄深紅的天亮 發表在 痞客邦 留言(2) 人氣()