manually sort array

[juggernot]

I was wondering if someone could show me how to do this. I attempted to do it already, but couldn't quite wrap my head around it If I had an array of random integers, lets say 100 integers, how would I sort them so that myarray(0) is the lowest, and the integers go in numerical order from there. My teacher was trying to show us how to do it, but is having problems himself. This was what he was trying to do:
For each integer in the array, compare myarray(0) to myarray(intcounter). If myarray(intcounter) < myarray(0), swap the values. This doesn't seem right to me, it seems ineffecient at best. I think it would work, but instead of swapping the values is there not just a way to insert a value at the top of an array, bumping all the other values? Any ideas?

 

[TechGnome]

That's a sorting method known as a "Bubble Sort" .... it's extremely fast and efficient for really small sets.... but there's a point of diminishing return with it. It's also called the Brute Force method. For larger sets, it becomes more effecient to use something called a "Binary Sort"... the Divide And Conquer method.

It sounds like he was trying to demonstrate the bubble sort.....

Basically it works like this:
let's say I have these 6 numbers:
45, 6, 76, 1, 56, 25

The way the bubble sort works is to make recursive loops through the list.... swaping numbers each time....

so on the first pass, 45 is greater thant 6, so it swaps them
6, 45, 76, 1, 56, 25

45 is now less than 76, so it doesn't swap... but 76 is greater than 1, so we swap again
6, 45, 1, 76, 56, 25

76 again is greater than 56, swap again...
6, 45, 1, 56, 76, 25

And 76 is greater than 25.... swap
6, 45, 1, 56, 25, 76


You can see how the largest number bubbled to the top (hence the name...)
And that's just the first pass.... for the second pass, since we now know that our largest number is in the last spot, we can ignore it and loop for (elements -1)

6, 45, 1, 56, 25, 76
6 is less than 45, so that's good.... 45 is greater than 1, so swap again
6, 1, 45, 56, 25, 76

45 is less than 56, so that's OK, but 56 is greater than 25, that's another swap.
6, 45, 1, 25, 56, 76

and that's pass 2....
repeat remaining passes until all elements have been sorted

1, 6, 25, 45, 56, 76

-tg

 

[cjard]

This doesn't seem right to me, it seems ineffecient at best.

Bubble sort is inefficient in most cases, but it is very simple to teach

Hoare's QuickSort or variations of it are usually among the fastest routines, with others such as ShellSort and HeapSort being popular.

I think it would work,

it does work..

but instead of swapping the values is there not just a way to insert a value at the top of an array, bumping all the other values? Any ideas?

Well, youre kinda asking like bubble sort is the only sort algorithm ever invented.. I think what youre thinking of is an Insertion Sort, which is a bit quicker than bubble..

Have a read of wikipedia bubble sort:
http://en.wikipedia.org/wiki/Bubble_sort

and see what you think..

 

[juggernot]

Thanks for the help guys. It makes sense now. My teacher didn't explain that after each pass we should exlude the sorted number, but I should have thought of that.

 

[TBryce311]

I suppose the concept is the most important part, but you don't have to do this manually in vb2005.

array.sort(YourArray) will sort this for you automatically.