Computer science people - question for you.

[sao123]

Sorting 10 elements 10 times is faster than sorting 100 elements once

actually what you proposed is slightly slower than doing the first 10 iterations of a bubble sort on the original 100 element array.

Sorting exactly 10 elements total is shorter than sorting 10 elements 10 times.

 

[sao123]

Heres how it is do it....

Example array. I want the top 3 numbers in this array of numbers.

Iteration 1
[0,1,7,5,2,8,3,9,4,(6)] Take the six and move it right until you reach a number higher than itself.
[0,1,7,5,2,8,3,(9),6,4] Now take the next number (the larger one which stopped it) and repeat.
[(9),0,1,7,5,2,8,3,6,4]

Iteration 2
[9,0,1,7,5,2,8,3,6,(4)] Take the four and move it right until you reach a number higher than itself.
[9,0,1,7,5,2,8,3,(6),4] Now take the six and move it right until you reach a number higher than itself.
[9,0,1,7,5,2,(8),6,3,4] Now take the eight and move it right until you reach a number higher than itself.
[9,(8),0,1,7,5,2,6,3,4]

Iteration 3
[9,8,0,1,7,5,2,6,3,(4)] Take the four and move it right until you reach a number higher than itself.
[9,8,0,1,7,5,2,(6),4,3] Take the six and move it right until you reach a number higher than itself.
[9,8,0,1,(7),6,5,2,4,3] Take the seven and move it right until you reach a number higher than itself.
[9,8,7,1,6,5,2,4,3]

I now have the 3 greatest numbers without sorting the entire list. I only sorted X which is the numerb of greatest elements i wanted.

 

[blahblah99]

Originally posted by: sao123
Heres how it is do it....

Example array. I want the top 3 numbers in this array of numbers.

Iteration 1
[0,1,7,5,2,8,3,9,4,(6)] Take the six and move it right until you reach a number higher than itself.
[0,1,7,5,2,8,3,(9),6,4] Now take the next number (the larger one which stopped it) and repeat.
[(9),0,1,7,5,2,8,3,6,4]

Iteration 2
[9,0,1,7,5,2,8,3,6,(4)] Take the four and move it right until you reach a number higher than itself.
[9,0,1,7,5,2,8,3,(6),4] Now take the six and move it right until you reach a number higher than itself.
[9,0,1,7,5,2,(8),6,3,4] Now take the eight and move it right until you reach a number higher than itself.
[9,(8),0,1,7,5,2,6,3,4]

Iteration 3
[9,8,0,1,7,5,2,6,3,(4)] Take the four and move it right until you reach a number higher than itself.
[9,8,0,1,7,5,2,(6),4,3] Take the six and move it right until you reach a number higher than itself.
[9,8,0,1,(7),6,5,2,4,3] Take the seven and move it right until you reach a number higher than itself.
[9,8,7,1,6,5,2,4,3]

I now have the 3 greatest numbers without sorting the entire list. I only sorted X which is the numerb of greatest elements i wanted.

Isn't that the bubble sort algorithm?

 

[sao123]

yes. Posted for Ihatemyjob because he originally thought what he was doing was bubblesort. Its different.

 

[blahblah99]

Originally posted by: sao123
yes. Posted for Ihatemyjob because he originally thought what he was doing was bubblesort. Its different.

Actually correct me if iI'm wrong, but doesn't that algorithm require you to have N loops within each other for N iterations? Like the example you used, there is 3 for loops for 3 iterations.

 

[sao123]

1 double loop
Outside loop is for N iterations. (how many numbers you need sunk-sorted)
Inside Loop is for 1 trip through the array.


void bubblesort(int array[], int size, int iterations)
{
:frown:for(int j=0; j<iterations; j++)
:frown:{//N iterations

:frown::frown:int temp;
:frown::frown:for(int k=size-1; k>0; k--)
:frown::frown:{//good for 1 trip through the array

:frown::frown::frown:if (array[k] > array[k-1])
:frown::frown::frown:{ //swap
:frown::frown::frown::frown:temp = array[k];
:frown::frown::frown::frown:array[k] = array[k-1];
:frown::frown::frown::frown:array[k-1] = temp;
:frown::frown::frown:}

:frown::frown:}

:frown:}

}



We really need code abilities in these forums.

 

[TheLonelyPhoenix]

Man, look at all this pent-up algorithm analysis energy. We really need to get that dedicated programming forum in gear.

 

[Armitage]

Originally posted by: sao123
1 double loop
Outside loop is for N iterations. (how many numbers you need sunk-sorted)
Inside Loop is for 1 trip through the array.


void bubblesort(int array[], int size, int iterations)
{
:frown:for(int j=0; j<iterations; j++)
:frown:{//N iterations

:frown::frown:int temp;
:frown::frown:for(int k=size-1; k>0; k--)
:frown::frown:{//good for 1 trip through the array

:frown::frown::frown:if (array[k] > array[k-1])
:frown::frown::frown:{ //swap
:frown::frown::frown::frown:temp = array[k];
:frown::frown::frown::frown:array[k] = array[k-1];
:frown::frown::frown::frown:array[k-1] = temp;
:frown::frown::frown:}

:frown::frown:}

:frown:}

}



We really need code abilities in these forums.

If this had been posted over in software where it belongs, you would have it.

 

[blahblah99]

Originally posted by: Armitage

Originally posted by: sao123
1 double loop
Outside loop is for N iterations. (how many numbers you need sunk-sorted)
Inside Loop is for 1 trip through the array.


void bubblesort(int array[], int size, int iterations)
{
:frown:for(int j=0; j<iterations; j++)
:frown:{//N iterations

:frown::frown:int temp;
:frown::frown:for(int k=size-1; k>0; k--)
:frown::frown:{//good for 1 trip through the array

:frown::frown::frown:if (array[k] > array[k-1])
:frown::frown::frown:{ //swap
:frown::frown::frown::frown:temp = array[k];
:frown::frown::frown::frown:array[k] = array[k-1];
:frown::frown::frown::frown:array[k-1] = temp;
:frown::frown::frown:}

:frown::frown:}

:frown:}

}



We really need code abilities in these forums.

If this had been posted over in software where it belongs, you would have it.

Good stuff....

I've implemented the 10 iteration bubble sort, and with a 500,000 element array, it pops out the top 10 largest numbers in ~14sec on my Pentium M 1.7Ghz. Not fast enough for use in dynamic html, but still usable in a daily update script. The application I'm using it for will have over 1+ million elements.

 

[Templeton]

Topic piqued my interest, so I wrote a quick java program to test the speed of 3 algorithms, simply sorting the entire array with quicksort, bubbling up the top 10, and going through linearly and adding to a 10 element sorted array. Each algorithm was tested with the same data, in random order, sorted ascending, and sorted descending.
results - 1GHz P3, each test performed 10 times and averaged:

bash-2.05b$ java SortTest 10 1000000 10
SortTest::bubbleSort
Random Array : 400.3ms
Ascending Array : 15.7ms
Descending Array: 415.3ms


SortTest::QuickSort
Random Array : 711.1ms
Ascending Array : 483.2ms
Descending Array: 472.8ms


SortTest::selectFind
Random Array : 14.0ms
Ascending Array : 221.4ms
Descending Array: 13.7ms

Results of course aren't exact, but they should give a good overall picture.

Source Code here