Garbage Collection

塵も積もれば山

目次

Blog 利用状況

ニュース

C++とかC#とか数学ネタを投下していく予定です。

[その他のページ]
日々の四方山話を綴った日記出水の日記帳

書庫

日記カテゴリ

[アルゴリズム]はみだしシェアソート3

Sub 縦方向ソート()
    Dim i As Integer
    Dim waku As Range
    
    For i = 0 To columnmax - 1
        Set waku = Range(Cells(1, i + 1), Cells(rowmax, i + 1))
        waku.Sort key1:=Cells(1, i + 1), order1:=xlAscending, Orientation:=xlSortColumns
    Next
End Sub

Sub 横方向ソート()
    Dim i As Integer
    Dim waku As Range
    
    For i = 0 To rowmax - 1
        Set waku = Range(Cells(i + 1, 1), Cells(i + 1, columnmax))
        If i Mod 2 = 0 Then
            waku.Sort key1:=Cells(i + 1, 1), order1:=xlAscending, Orientation:=xlSortRows
        Else
            waku.Sort key1:=Cells(i + 1, 1), order1:=xlDescending, Orientation:=xlSortRows
        End If
    Next
End Sub

上はエクセルのマクロの抜粋です。
ごめんなさい、思いっきり手を抜きました。

ソートを作るんだから、既存のソート関数を使ってはいけないのですが、
思いっきりSortという文字が見えます。

今回は、縦ソート、横ソートに何を使うか考えてみます。

普通に考えればシェアソートを再帰する方法です。
ですが、シェアソートは順列(すでにソート済みの状態)であっても
交換が発生してしまうため、順列の検出が出来ません。

なお、縦ソート、横ソート共に交換が発生しなかったら終了という条件ですが、
実際には2回目以降なら縦ソートか横ソートのどちらかで順列を検出すればOKです。
なぜなら、縦ソート後は縦ソートをしても交換が発生しない状態だからです。

順列の検出といえばバブルソートです。
これを縦ソートに使ってやれば順列の検出が出来るし、
縦ソートはそれほど要素が変わらないため、
バブルソートでも十分速度が出ると考えられます。

ただし、横ソートにバブルソートを使った場合、
最大要素や最小要素が先頭や末尾に来ることが多いため
バブルソートの最悪パターンに陥りやすいため、不向きと言えるでしょう。
こちらはシェアソートを再帰させるべきです。

なお、最初の縦ソートに限っては、要素がバラバラである上
順列検出も必要ないため、こちらはシェアソートで十分に思えます。

あとは、要素が少ない場合はバブルソートでいいでしょう。
どこを閾値にするか難しいですが、一辺が3以下になる16未満としておきます。

よって、改良シェアソートのアルゴリズムは以下のようになります。

  1. 要素が16未満ならバブルソートを行い、終了する。
  2. シェアソートを使い、縦ソートを行う。
  3. 繰り返し回数を求める。( n = log(√n) )
  4. シェアソートを使い横ソートを行う。
    このとき、奇数行は昇順、偶数行は降順になるようにする。
  5. バブルソートを使い縦ソートを行う。
  6. 縦ソートで、すべての列で交換が発生しない場合、偶数行を反転して終了する。
  7. 4.~7.を回数分繰り返す。
  8. シェアソートを使い横ソートを行う。
    すべての行で昇順になるようにする。

なお、ここでバブルソートを使っていますが、
クイックソート等の高速ソートだとどうでしょうか。

結論から言うと、シェアソートとクイックソートを組み合わせるより
最初からクイックソートを使った方が速いです。

せっかく改良したのにまさに無駄骨です。

投稿日時 : 2008年9月23日 6:32

Feedback

# re: [アルゴリズム]はみだしシェアソート3 2008/09/24 13:43 凪瀬

>せっかく改良したのにまさに無駄骨です。
ちょww

# re: [アルゴリズム]はみだしシェアソート3 2008/09/25 1:08 出水

面白いソートではあるんだけど、面白いだけという不遇なソートです

# Great post but I was wondering if you could write a litte more on this subject? I'd be very thankful if you could elaborate a little bit more. Bless you! 2018/10/04 15:57 Great post but I was wondering if you could write

Great post but I was wondering if you could
write a litte more on this subject? I'd be very thankful if you
could elaborate a little bit more. Bless you!

# I think this is among the most significant information for me. And i'm glad reading your article. But want to remark on some general things, The site style is perfect, the articles is really great : D. Good job, cheers 2018/10/07 12:47 I think this is among the most significant informa

I think this is among the most significant information for me.
And i'm glad reading your article. But want to remark on some general things, The site style is perfect,
the articles is really great : D. Good job, cheers

# For most recent information you have to pay a quick visit internet and on web I found this web site as a best web site for hottest updates. 2018/10/26 6:04 For most recent information you have to pay a quic

For most recent information you have to pay
a quick visit internet and on web I found this web site as a best web site for hottest updates.

# I just could not leave your web site prior to suggesting that I extremely loved the usual information an individual provide for your visitors? Is gonna be back regularly to check out new posts 2018/11/17 3:35 I just could not leave your web site prior to sugg

I just could not leave your web site prior to suggesting that I extremely
loved the usual information an individual provide for your visitors?
Is gonna be back regularly to check out new posts

# Can I just say what a relief to find a person that really knows what they're discussing over the internet. You definitely realize how to bring an issue to light and make it important. A lot more people really need to check this out and understand this 2018/11/18 23:31 Can I just say what a relief to find a person that

Can I just say what a relief to find a person that really knows what they're
discussing over the internet. You definitely realize how to bring an issue to light and
make it important. A lot more people really need to check this out and understand
this side of your story. It's surprising you
are not more popular given that you certainly have the gift.

# Hi there! I realize this is sort of off-topic however I needed to ask. Does operating a well-established website such as yours require a massive amount work? I am completely new to operating a blog but I do write in my diary on a daily basis. I'd like to 2021/08/23 19:26 Hi there! I realize this is sort of off-topic howe

Hi there! I realize this is sort of off-topic however I needed to
ask. Does operating a well-established website such as yours require a massive amount work?

I am completely new to operating a blog but I do write in my
diary on a daily basis. I'd like to start a blog so I will be able to share my personal experience and thoughts online.
Please let me know if you have any kind of suggestions or tips
for new aspiring bloggers. Thankyou!

# Hi there! I realize this is sort of off-topic however I needed to ask. Does operating a well-established website such as yours require a massive amount work? I am completely new to operating a blog but I do write in my diary on a daily basis. I'd like to 2021/08/23 19:27 Hi there! I realize this is sort of off-topic howe

Hi there! I realize this is sort of off-topic however I needed to
ask. Does operating a well-established website such as yours require a massive amount work?

I am completely new to operating a blog but I do write in my
diary on a daily basis. I'd like to start a blog so I will be able to share my personal experience and thoughts online.
Please let me know if you have any kind of suggestions or tips
for new aspiring bloggers. Thankyou!

# Hi there! I realize this is sort of off-topic however I needed to ask. Does operating a well-established website such as yours require a massive amount work? I am completely new to operating a blog but I do write in my diary on a daily basis. I'd like to 2021/08/23 19:28 Hi there! I realize this is sort of off-topic howe

Hi there! I realize this is sort of off-topic however I needed to
ask. Does operating a well-established website such as yours require a massive amount work?

I am completely new to operating a blog but I do write in my
diary on a daily basis. I'd like to start a blog so I will be able to share my personal experience and thoughts online.
Please let me know if you have any kind of suggestions or tips
for new aspiring bloggers. Thankyou!

# Hi there! I realize this is sort of off-topic however I needed to ask. Does operating a well-established website such as yours require a massive amount work? I am completely new to operating a blog but I do write in my diary on a daily basis. I'd like to 2021/08/23 19:29 Hi there! I realize this is sort of off-topic howe

Hi there! I realize this is sort of off-topic however I needed to
ask. Does operating a well-established website such as yours require a massive amount work?

I am completely new to operating a blog but I do write in my
diary on a daily basis. I'd like to start a blog so I will be able to share my personal experience and thoughts online.
Please let me know if you have any kind of suggestions or tips
for new aspiring bloggers. Thankyou!

# Hi, after reading this amazing post i am too glad to share my experience here with friends. 2021/08/24 15:20 Hi, after reading this amazing post i am too glad

Hi, after reading this amazing post i am too glad to share my experience here with friends.

# Hi my loved one! I want to say that this post is awesome, great written and include approximately all vital infos. I would like to look extra posts like this . 2021/08/25 20:46 Hi my loved one! I want to say that this post is a

Hi my loved one! I want to say that this post is awesome, great written and include
approximately all vital infos. I would like to look extra
posts like this .

# Hi my loved one! I want to say that this post is awesome, great written and include approximately all vital infos. I would like to look extra posts like this . 2021/08/25 20:47 Hi my loved one! I want to say that this post is a

Hi my loved one! I want to say that this post is awesome, great written and include
approximately all vital infos. I would like to look extra
posts like this .

# Hi my loved one! I want to say that this post is awesome, great written and include approximately all vital infos. I would like to look extra posts like this . 2021/08/25 20:48 Hi my loved one! I want to say that this post is a

Hi my loved one! I want to say that this post is awesome, great written and include
approximately all vital infos. I would like to look extra
posts like this .

# Hi my loved one! I want to say that this post is awesome, great written and include approximately all vital infos. I would like to look extra posts like this . 2021/08/25 20:49 Hi my loved one! I want to say that this post is a

Hi my loved one! I want to say that this post is awesome, great written and include
approximately all vital infos. I would like to look extra
posts like this .

# Have you ever considered creating an e-book or guest authoring on other websites? I have a blog based on the same subjects you discuss and would love to have you share some stories/information. I know my visitors would value your work. If you're even re 2021/09/01 18:33 Have you ever considered creating an e-book or gue

Have you ever considered creating an e-book
or guest authoring on other websites? I have a blog based on the same subjects you discuss and would love
to have you share some stories/information. I know my visitors would value your work.
If you're even remotely interested, feel free
to send me an e mail.

# Have you ever considered creating an e-book or guest authoring on other websites? I have a blog based on the same subjects you discuss and would love to have you share some stories/information. I know my visitors would value your work. If you're even re 2021/09/01 18:34 Have you ever considered creating an e-book or gue

Have you ever considered creating an e-book
or guest authoring on other websites? I have a blog based on the same subjects you discuss and would love
to have you share some stories/information. I know my visitors would value your work.
If you're even remotely interested, feel free
to send me an e mail.

# Have you ever considered creating an e-book or guest authoring on other websites? I have a blog based on the same subjects you discuss and would love to have you share some stories/information. I know my visitors would value your work. If you're even re 2021/09/01 18:35 Have you ever considered creating an e-book or gue

Have you ever considered creating an e-book
or guest authoring on other websites? I have a blog based on the same subjects you discuss and would love
to have you share some stories/information. I know my visitors would value your work.
If you're even remotely interested, feel free
to send me an e mail.

# Have you ever considered creating an e-book or guest authoring on other websites? I have a blog based on the same subjects you discuss and would love to have you share some stories/information. I know my visitors would value your work. If you're even re 2021/09/01 18:36 Have you ever considered creating an e-book or gue

Have you ever considered creating an e-book
or guest authoring on other websites? I have a blog based on the same subjects you discuss and would love
to have you share some stories/information. I know my visitors would value your work.
If you're even remotely interested, feel free
to send me an e mail.

# This page definitely has all the information and facts I wanted concerning this subject and didn't know who to ask. 2021/09/05 1:48 This page definitely has all the information and f

This page definitely has all the information and facts I
wanted concerning this subject and didn't know who to ask.

# This page definitely has all the information and facts I wanted concerning this subject and didn't know who to ask. 2021/09/05 1:49 This page definitely has all the information and f

This page definitely has all the information and facts I
wanted concerning this subject and didn't know who to ask.

# This page definitely has all the information and facts I wanted concerning this subject and didn't know who to ask. 2021/09/05 1:50 This page definitely has all the information and f

This page definitely has all the information and facts I
wanted concerning this subject and didn't know who to ask.

# This page definitely has all the information and facts I wanted concerning this subject and didn't know who to ask. 2021/09/05 1:51 This page definitely has all the information and f

This page definitely has all the information and facts I
wanted concerning this subject and didn't know who to ask.

# Pretty great post. I just stumbled upon your weblog and wished to say that I have truly enjoyed surfing around your weblog posts. After all I'll be subscribing on your feed and I'm hoping you write once more soon! 2021/09/05 23:19 Pretty great post. I just stumbled upon your weblo

Pretty great post. I just stumbled upon your weblog
and wished to say that I have truly enjoyed surfing around your weblog posts.
After all I'll be subscribing on your feed and I'm hoping you write once more soon!

# Pretty great post. I just stumbled upon your weblog and wished to say that I have truly enjoyed surfing around your weblog posts. After all I'll be subscribing on your feed and I'm hoping you write once more soon! 2021/09/05 23:20 Pretty great post. I just stumbled upon your weblo

Pretty great post. I just stumbled upon your weblog
and wished to say that I have truly enjoyed surfing around your weblog posts.
After all I'll be subscribing on your feed and I'm hoping you write once more soon!

# Pretty great post. I just stumbled upon your weblog and wished to say that I have truly enjoyed surfing around your weblog posts. After all I'll be subscribing on your feed and I'm hoping you write once more soon! 2021/09/05 23:21 Pretty great post. I just stumbled upon your weblo

Pretty great post. I just stumbled upon your weblog
and wished to say that I have truly enjoyed surfing around your weblog posts.
After all I'll be subscribing on your feed and I'm hoping you write once more soon!

# Pretty great post. I just stumbled upon your weblog and wished to say that I have truly enjoyed surfing around your weblog posts. After all I'll be subscribing on your feed and I'm hoping you write once more soon! 2021/09/05 23:22 Pretty great post. I just stumbled upon your weblo

Pretty great post. I just stumbled upon your weblog
and wished to say that I have truly enjoyed surfing around your weblog posts.
After all I'll be subscribing on your feed and I'm hoping you write once more soon!

# Your style is really unique compared to other people I have read stuff from. Thanks for posting when you've got the opportunity, Guess I will just bookmark this blog. 2021/10/25 20:46 Your style is really unique compared to other peop

Your style is really unique compared to other people I have
read stuff from. Thanks for posting when you've got the opportunity, Guess
I will just bookmark this blog.

# This piece of writing will help the internet users for setting up new website or even a blog from start to end. 2022/03/24 3:58 This piece of writing will help the internet users

This piece of writing will help the internet users for setting up new website
or even a blog from start to end.

タイトル
名前
Url
コメント