Sorting algorithms

 DevX Home Today's Headlines   Articles Archive   Tip Bank   Forums

1. Registered User
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. Registered User
Join Date
Sep 2005
Location
istanbul / Turkey
Posts
133

3. Registered User
Join Date
May 2005
Posts
75
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. Registered User
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. Registered User
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. Registered User
Join Date
Sep 2005
Posts
74
That's odd..it uses less comparisons, but has whole lot more swaps.

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

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

 FAQ Latest Articles Java .NET XML Database Enterprise