公告版位
星落的瞬間!放棄的後悔是永遠!

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





創作者介紹

!壞人必需做好事!

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


留言列表 (2)

發表留言
  • novus
  • 呃....你這裡大多數的 inline 都是無意義的,編譯器不會幫你做。

    quick_sort_median_3_partition 有笨到,編譯期無法得知深度的遞迴是不可能 inline 的。你想想看用手工去消除這種遞迴要怎麼寫?如果你寫不出來,那麼編譯器當然也辦不到。


    這裡全部的 static 都是無意義的,我猜你的目的是防止其他人誤用內部的函數,不過一點用也沒有。

    你所有的 static 都會隨著 header 變成其他編譯單元的的一部份,在同一個編譯單元的其他程式碼仍然可以呼叫到這些 static 函數。如果想隱藏實作,應該用 namespace
  • 原來如此= =
    我再改改,等v4吧!

    讓地獄深紅的天亮 於 2010/04/06 00:56 回覆

  • 悄悄話
找更多相關文章與討論