Sorting algorithms

[srekcus]

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

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!

[mr1yh1]

yes its bubble sort algorithm
http://linux.wku.edu/~lamonml/algor/sort/bubble.html

[srekcus]

yes its bubble sort algorithm
http://linux.wku.edu/~lamonml/algor/sort/bubble.html

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.

[mr1yh1]

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++ )

[srekcus]

I used the same array on my method and the official bubble sort method. Here was the output...

The array has 76 integers

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 . . .

[Dark Rain]

That's odd..it uses less comparisons, but has whole lot more swaps.

[srekcus]

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.

[mr1yh1]

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++)

[sjalle]

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:

Bubble Sort complete, 100000 elements, used: 36484 millisec

Collections Sort complete, 100000 elements, used: 250 millisec