topbanner_forum
  *

avatar image

Welcome, Guest. Please login or register.
Did you miss your activation email?

Login with username, password and session length
  • Monday March 18, 2024, 10:10 pm
  • Proudly celebrating 15+ years online.
  • Donate now to become a lifetime supporting member of the site and get a non-expiring license key for all of our programs.
  • donate

Author Topic: two way bubble sort  (Read 6622 times)

h0meopathic

  • Participant
  • Joined in 2007
  • *
  • default avatar
  • Posts: 24
    • View Profile
    • Donate to Member
two way bubble sort
« on: September 07, 2008, 11:23 AM »
Code: Java [Select]
  1. public static void bubble( int a[] )
  2.   {
  3.     boolean done = false;
  4.     int temp;
  5.    
  6.     for( int forwardPass = 1; forwardPass < N && !done; forwardPass++ )
  7.     {
  8.       done = true;
  9.       for( int i = 0; i < N - forwardPass; i++ )
  10.       {
  11.         if( a[ i ] > a[ i + 1 ] )
  12.         {
  13.           temp = a[ i ];
  14.           a[ i ] = a[ i + 1 ];
  15.           a[ i + 1 ] = temp;
  16.          
  17.           if( a[ i ] < a[ i - 1 ] )
  18.             {
  19.               temp = a[ i ];
  20.               a[ i ] = a[ i - 1 ];
  21.               a[ i - 1 ] = temp;
  22.               done = false;
  23.             }      
  24.           done = false;
  25.         }
  26.       }
  27.     }
  28.   }

I'm trying to write a method that will sort some values that I've put into an array.

The first "if" statement does a bubble sort forwards and I know that works. I'm trying to get the bubble sort to sort backwards after the forward pass and the 2nd "if" statement is my attempt at doing so.

It seems to me that the code provided would work accordingly but it doesn't. I tried commenting out the first "if" statement and the program stops working at the 2nd "if" statement. However, if nothing is commented out then the program sorts like it should so maybe I'm testing it wrong.

VideoInPicture

  • Honorary Member
  • Joined in 2008
  • **
  • Posts: 467
    • View Profile
    • Circle Dock
    • Donate to Member
Re: two way bubble sort
« Reply #1 on: September 07, 2008, 11:57 AM »
You are accessing the array out of bounds when it hits the line
if ( a[ i ] < a[ i - 1 ] ) and you have i = 0
Author of Circle Dock: http://circledock.wikidot.com
Author of Video In Picture: http://videoinpicture.wikidot.com
Author of Webcam Signature: http://webcamsignature.wikidot.com
Author of Easy Unicode Paster: http://easyunicodepaster.wikidot.com

h0meopathic

  • Participant
  • Joined in 2007
  • *
  • default avatar
  • Posts: 24
    • View Profile
    • Donate to Member
Re: two way bubble sort
« Reply #2 on: September 07, 2008, 12:57 PM »
Code: C# [Select]
  1. public static void bubble( int a[] )
  2.   {
  3.     boolean done = false;
  4.     int temp;
  5.    
  6.     for( int forwardPass = 1; forwardPass < N && !done; forwardPass++ )
  7.     {
  8.       done = true;
  9.       for( int i = 0; i < N - forwardPass; i++ )
  10.       {
  11.         if( a[ i ] > a[ i + 1 ] )
  12.         {
  13.           temp = a[ i ];
  14.           a[ i ] = a[ i + 1 ];
  15.           a[ i + 1 ] = temp;        
  16.           done = false;
  17.         }
  18.       }
  19.     }
  20.   }

Please don't give me the answer but help walk me through it.

This is the code that makes the bubble sort keep making forward passes though the array until done = true (all the values in the array are sorted in a lowest to highest value order).
I am confused to hell as to how to make the sort make a forward pass and at the end make a backward pass and then forward again until all the values are in order.
Basically I'm trying to come up with the best algorithm of sorting to sort in the least amount of time using a bubble sort method (the one list above).