DieHard Wolfers Forum Index DieHard Wolfers
A Wolfenstein 3d Fan Community


  Hosted by: MCS & Areyep.com - Designed by: BrotherTank

Original Yahoo Forum - Die Hard Archives

AReyeP HomepageAreyep Homepage DieHard Wolfenstein BunkerDieHard Wolfenstein Bunker Log inLog in RegisterRegister Banlist FAQFAQ Search ForumsSearch

  Username:    Password:      Remember me       

Bubble sort algorithm
Page 1 of 1
DieHard Wolfers Forum Index -> Howling Wolfers View Previous TopicRefresh this PageAdd Topic to your Browser FavoritesSearch ForumsPrint this TopicE-mail TopicGoto Page BottomView Next Topic
Post new topicReply to topic
Author Message
Matthew
DieHard Officer
DieHard Officer


Joined: 02 Jul 2007
Last Visit: 02 Feb 2020

Topics: 103
Posts: 518

usa.gif

PostPosted: Fri May 17, 2019 10:54 pm
   Subject: Bubble sort algorithm
   [ IP : Logged ]
Reply with quote
Goto Top of PostsGoto Next PostGoto Bottom of Posts

The bubble sort algorithm is an algorithm widely used in computer programming for sorting a list.

I was looking at the Wikipedia article on it, and noticed something very strange:

It describes it as doing repeated passes, until no swaps are done.

It describes some ways of optimizing it, by reducing the number of items checked on subsequent passes.

But it is not necessary to do multiple passes at all.

All it needs to do is move back one step after a swap is done.

Here is C code that does this:



::: CODE :::
void sort(int *list, int count)
{
   if (count < 2)
      return;

   for (int *p = list; p != list + count - 1; )
      if (*(p + 1) < *p)
      {
         int i = *p;

         *p = *(p + 1);
         *(p + 1) = i;

         if (p == list)
            p++;
         else
            p--;
      }
      else
         p++;
}




I figured this out myself around 10 years ago.

But I don't see it mentioned anywhere. I did a Google search, and all the articles I found describe the algorithm using repeated passes, like the Wikipedia article.

The Wikipedia article says that the algorithm is very inefficient. But it is highly efficient the way I've written it.

I'd edit the article so it tells this, but Wikipedia doesn't allow original research. Smile

I've posted a message on the article's talk page about this.

Surely I'm not the first person to have discovered this?


Last edited by Matthew on Sat May 18, 2019 6:02 pm; edited 2 times in total
Arno
Don't Hurt Me
Don't Hurt Me


Joined: 26 Oct 2017
Last Visit: 16 Jan 2020

Topics: 2
Posts: 62
Location: Netherlands
netherlands.gif

PostPosted: Sat May 18, 2019 5:33 am
   Subject: Bubble sort algorithm
   [ IP : Logged ]
Reply with quote
Goto Top of PostsGoto Previous PostGoto Next PostGoto Bottom of Posts

Probably in a lot of cases your modified algorithm would work more efficient than the standard bubble sort algorithm.
But in the worst case scenario, where initially all elements are in reverse order, I don't think there is any difference in efficiency. You would still have to repeatedly go forward and backward through the list to get all elements in the correct order.
Matthew
DieHard Officer
DieHard Officer


Joined: 02 Jul 2007
Last Visit: 02 Feb 2020

Topics: 103
Posts: 518

usa.gif

PostPosted: Sat May 18, 2019 6:28 pm
   Subject: Bubble sort algorithm
   [ IP : Logged ]
Reply with quote
Goto Top of PostsGoto Previous PostGoto Next PostGoto Bottom of Posts

My version of the algorithm always does fewer iterations, unless no items are swapped at all.

If all the numbers in the list are random, it does about half as many iterations as the other version.



Arno wrote:
But in the worst case scenario, where initially all elements are in reverse order, I don't think there is any difference in efficiency. You would still have to repeatedly go forward and backward through the list to get all elements in the correct order.


Even in this case, it does fewer iterations. The difference is 1 less than the number of items in the list.
Tricob
Moderator
<B>Moderator</B>


Joined: 14 Mar 2005
Last Visit: 4:19 ago.

Topics: 168
Posts: 8511
Location: Neo-traditions, Inc.
usa.gif

PostPosted: Sat May 18, 2019 6:48 pm
   Subject: Re: Bubble sort algorithm
   [ IP : Logged ]
Reply with quote
Goto Top of PostsGoto Previous PostGoto Bottom of Posts

I've seen the bubble sort algorithm in action before, and came across to me as inefficient, also. Of course, it was decades old even when I first saw it (the mid-1980s). It makes sense that people out there can come up with more efficient methods over time. Smile
Display posts from previous:   
Post new topicReply to topic Time synchronized with the forum server time
DieHard Wolfers Forum Index -> Howling Wolfers View Previous TopicRefresh this PageAdd Topic to your Browser FavoritesSearch ForumsPrint this TopicE-mail TopicGoto Page TopView Next Topic
Page 1 of 1
Jump to:  

Related topics
 Topics   Replies   Views   Last Post 
No new posts Announcement: Back by Demand - With Stipulations!
Author: BrotherTank
1 4770 Wed Mar 31, 2004 11:24 pm
AReyeP View latest post
No new posts Return Fire 2 soundtrack
Author: Ringman
1 1528 Wed Mar 29, 2006 8:02 am
Ringman View latest post
No new posts The first time im EVER coloring on Adobe.
Author: Blitzkrieg
0 1443 Thu Jan 26, 2006 6:55 pm
Blitzkrieg View latest post
No new posts Return to Castle Wolfenstien 2
Author: ChiefRebelAngel
9 3130 Wed Nov 23, 2005 3:32 pm
Soldat 555 View latest post
No new posts I'm Back
Author: Sockdude
6 3006 Sun Jul 24, 2005 6:35 pm
Tricob View latest post
 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
   You cannot delete your posts in this forum
You cannot vote in polls in this forum


Copyright ©2003-2008 DieHard Wolfers
A Modified subBunker Theme by BrotherTank
Powered by phpBB © 2001, 2005 phpBB Group