Sorting algorithms


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 9 of 9

Thread: Sorting algorithms

  1. #1
    Join Date
    May 2005
    Posts
    75

    Sorting algorithms

    I wrote this algorithm without looking at other methods and I'm curious if it's identical to any already out there...

    Code:
    public static void sort(int[] list){
    
         int loopStart = list.length - 1;
         int temp = 0;
    
         for(int i = loopStart; i >= 0; i--){
    
              for(int j = 0; j <= i; j++){
    
                   if(list[i] < list[j]){
    
                        temp = list[i];
                        list[i] = list[j];
                        list[j] = temp;
                   }
              }
         }
    }
    It sorts an array in ascending order. Thanks!

  2. #2
    Join Date
    Sep 2005
    Location
    istanbul / Turkey
    Posts
    133

  3. #3
    Join Date
    May 2005
    Posts
    75
    Quote Originally Posted by mr1yh1
    It's not bubble sort, the if statements are different as well as the nested for loop. I've actually compared this code with bubble sort and the one I posted does a lot less number swaps.

  4. #4
    Join Date
    Sep 2005
    Location
    istanbul / Turkey
    Posts
    133
    are you using same list while comparing them ?
    swap count depends, how well your list ordered by luck before sort, its not constant.

    you may count how much times loops worked. it will give same amount.
    but first you may change this:

    for(int i = loopStart; i >= 0; i--)
    for(int j = 0; j <= i; j++)


    with :
    for(int i = loopStart; i > 0; i--)
    for(int j = 0; j < i; j++)


    -"j" start from 0 ( zero ), so no need i >= 0 .
    -no need to compare j == i situation. ( j <= i )

    -------------------------------------------
    you may see different kinds of loops , its not important.
    they use "same logic" so all of them named as bubble sort.

    forexample i customed to use :
    for ( int i = 0 ; i < length -1 ; i++ )
    for ( int j = i+1 ; j < length ; j++ )

  5. #5
    Join Date
    May 2005
    Posts
    75
    I used the same array on my method and the official bubble sort method. Here was the output...

    The array has 76 integers

    Code:
    My sort:
    
    15 47 84 65 33 2 4 88 54 23 95 66 41 77 48 62 44 10 85 112 45 33 28 99 92 61 20 88 51 72 147 156 321 470 120 100 741 14 16 103 88 77 63 15 84 55 98 46 9 6 17 65 33 2 4 88 54 23 95 65 25 84 96 21 1 31 25 84 231 746 658 251 57 52 514 300
    
    1 2 2 4 4 6 9 10 14 15 15 16 17 20 21 23 23 25 25 28 31 33 33 33 41 44 45 46 47 48 51 52 54 54 55 57 61 62 63 65 65 65 66 72 77 77 84 84 84 84 85 88 88 88 88 92 95 95 96 98 99 100 103 112 120 147 156 231 251 300 321 470 514 658 741 746
    
    Comparisons: 2926, Swaps: 395
    
    ---------------
    
    Bubble sort:
    
    15 47 84 65 33 2 4 88 54 23 95 66 41 77 48 62 44 10 85 112 45 33 28 99 92 61 20 88 51 72 147 156 321 470 120 100 741 14 16 103 88 77 63 15 84 55 98 46 9 6 17 65 33 2 4 88 54 23 95 65 25 84 96 21 1 31 25 84 231 746 658 251 57 52 514 300
    
    1 2 2 4 4 6 9 10 14 15 15 16 17 20 21 23 23 25 25 28 31 33 33 33 41 44 45 46 47 48 51 52 54 54 55 57 61 62 63 65 65 65 66 72 77 77 84 84 84 84 85 88 88 88 88 92 95 95 96 98 99 100 103 112 120 147 156 231 251 300 321 470 514 658 741 746
    
    
    Comparisons: 2850, Swaps: 1262
    
    Press any key to continue . . .

  6. #6
    Join Date
    Sep 2005
    Posts
    74
    That's odd..it uses less comparisons, but has whole lot more swaps.

  7. #7
    Join Date
    May 2005
    Posts
    75
    Here is a visual of how my algorithm works. The only problem is that once the array is sorted it keeps looping until it has compared all of the values. For example, even though in my picture the array is sorted after just 4 loops, it will keep going until the the entire array is checked.

    http://images5.theimagehosting.com/array_visual.jpg

    I haven't been able to figure out how to stop the loop once it's sorted without increasing the number of comparisons tremendously. Also, each array will vary and I haven't seen a pattern in how soon the loop will sort.

  8. #8
    Join Date
    Sep 2005
    Location
    istanbul / Turkey
    Posts
    133
    yes there is a difference between which i use and you use.
    you have less swap counts.

    it seems thats a good idea to start opposite edges for swap and moving opposite directions. thanks you showed it.
    but still it's bubble sort, some places its defined in taht way :
    http://en.wikipedia.org/wiki/Bubble_sort

    mostly algorithms focused on comparation count,
    becos it make the real difference when n( array element count ) is getting bigger.

    note : if you make changes i told , you will get same comparation counts
    for(int i = loopStart; i > 0; i--)
    for(int j = 0; j < i; j++)

  9. #9
    Join Date
    Nov 2004
    Location
    Norway
    Posts
    1,560
    No doubt a bubble sort, the name comes from the notion that the values "bubble" up
    or down (depending on order) and the highest/lowest float up/down in the array
    depending on their "bubble size" or value.

    I tested it against the java.util.Collections sort with an array of 100000
    integers in the range 1-99999:
    Code:
    Bubble Sort complete, 100000 elements, used: 36484 millisec
    
    Collections Sort complete, 100000 elements, used: 250 millisec
    Last edited by sjalle; 10-31-2005 at 05:48 AM.
    eschew obfuscation

Similar Threads

  1. Replies: 3
    Last Post: 07-29-2005, 10:00 AM
  2. Replies: 1
    Last Post: 04-05-2002, 10:18 AM
  3. Algorithms
    By Jeremy in forum .NET
    Replies: 2
    Last Post: 04-05-2001, 07:15 PM
  4. Sorting for a JTable
    By Ramkumar in forum Java
    Replies: 1
    Last Post: 01-11-2001, 05:32 AM
  5. CrossBrowser DHTML table sorting problem
    By Joel Matto in forum Web
    Replies: 0
    Last Post: 05-02-2000, 03:58 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center