With this ascii output, we see without any difficulty how is make the basic
bubble sort :
*********************************
* Test original bubble_sort algo *
**********************************
(nbiter=1, size=16)
presorted : 5 -101 (77) -90 -46 124 -67 -39 30 123 -41 -105 -6 -69 -8 120
presorted : 5 -101 -90 (77) -46 124 -67 -39 30 123 -41 -105 -6 -69 -8 120
presorted : 5 -101 -90 -46 (77) 124 -67 -39 30 123 -41 -105 -6 -69 -8 120
presorted : 5 -101 -90 -46 77 -67 (124) -39 30 123 -41 -105 -6 -69 -8 120
presorted : 5 -101 -90 -46 77 -67 -39 (124) 30 123 -41 -105 -6 -69 -8 120
presorted : 5 -101 -90 -46 77 -67 -39 30 (124) 123 -41 -105 -6 -69 -8 120
presorted : 5 -101 -90 -46 77 -67 -39 30 123 (124) -41 -105 -6 -69 -8 120
presorted : 5 -101 -90 -46 77 -67 -39 30 123 -41 (124) -105 -6 -69 -8 120
presorted : 5 -101 -90 -46 77 -67 -39 30 123 -41 -105 (124) -6 -69 -8 120
presorted : 5 -101 -90 -46 77 -67 -39 30 123 -41 -105 -6 (124) -69 -8 120
presorted : 5 -101 -90 -46 77 -67 -39 30 123 -41 -105 -6 -69 (124) -8 120
presorted : 5 -101 -90 -46 77 -67 -39 30 123 -41 -105 -6 -69 -8 (124) 120
presorted : 5 -101 -90 -46 77 -67 -39 30 123 -41 -105 -6 -69 -8 120 (124)
presorted : 5 -101 -90 -46 77 -67 -39 30 123 -41 -105 (-69) -6 -8 120 124
presorted : 5 -101 -90 -46 77 -67 -39 30 123 (-105) -41 -69 -6 -8 120 124
presorted : 5 -101 -90 -46 77 -67 -39 30 (-105) 123 -41 -69 -6 -8 120 124
presorted : 5 -101 -90 -46 77 -67 -39 (-105) 30 123 -41 -69 -6 -8 120 124
presorted : 5 -101 -90 -46 77 -67 (-105) -39 30 123 -41 -69 -6 -8 120 124
presorted : 5 -101 -90 -46 77 (-105) -67 -39 30 123 -41 -69 -6 -8 120 124
presorted : 5 -101 -90 -46 (-105) 77 -67 -39 30 123 -41 -69 -6 -8 120 124
presorted : 5 -101 -90 (-105) -46 77 -67 -39 30 123 -41 -69 -6 -8 120 124
presorted : 5 -101 (-105) -90 -46 77 -67 -39 30 123 -41 -69 -6 -8 120 124
presorted : 5 (-105) -101 -90 -46 77 -67 -39 30 123 -41 -69 -6 -8 120 124
presorted : (-105) 5 -101 -90 -46 77 -67 -39 30 123 -41 -69 -6 -8 120 124
presorted : -105 -101 (5) -90 -46 77 -67 -39 30 123 -41 -69 -6 -8 120 124
presorted : -105 -101 -90 (5) -46 77 -67 -39 30 123 -41 -69 -6 -8 120 124
presorted : -105 -101 -90 -46 (5) 77 -67 -39 30 123 -41 -69 -6 -8 120 124
presorted : -105 -101 -90 -46 5 -67 (77) -39 30 123 -41 -69 -6 -8 120 124
presorted : -105 -101 -90 -46 5 -67 -39 (77) 30 123 -41 -69 -6 -8 120 124
presorted : -105 -101 -90 -46 5 -67 -39 30 (77) 123 -41 -69 -6 -8 120 124
presorted : -105 -101 -90 -46 5 -67 -39 30 77 -41 (123) -69 -6 -8 120 124
presorted : -105 -101 -90 -46 5 -67 -39 30 77 -41 -69 (123) -6 -8 120 124
presorted : -105 -101 -90 -46 5 -67 -39 30 77 -41 -69 -6 (123) -8 120 124
presorted : -105 -101 -90 -46 5 -67 -39 30 77 -41 -69 -6 -8 (123) 120 124
presorted : -105 -101 -90 -46 5 -67 -39 30 77 -41 -69 -6 -8 120 (123) 124
presorted : -105 -101 -90 -46 5 -67 -39 30 77 -41 -69 (-8) -6 120 123 124
presorted : -105 -101 -90 -46 5 -67 -39 30 77 (-69) -41 -8 -6 120 123 124
presorted : -105 -101 -90 -46 5 -67 -39 30 (-69) 77 -41 -8 -6 120 123 124
presorted : -105 -101 -90 -46 5 -67 -39 (-69) 30 77 -41 -8 -6 120 123 124
presorted : -105 -101 -90 -46 5 -67 (-69) -39 30 77 -41 -8 -6 120 123 124
presorted : -105 -101 -90 -46 5 (-69) -67 -39 30 77 -41 -8 -6 120 123 124
presorted : -105 -101 -90 -46 (-69) 5 -67 -39 30 77 -41 -8 -6 120 123 124
presorted : -105 -101 -90 (-69) -46 5 -67 -39 30 77 -41 -8 -6 120 123 124
presorted : -105 -101 -90 -69 -46 -67 (5) -39 30 77 -41 -8 -6 120 123 124
presorted : -105 -101 -90 -69 -46 -67 -39 (5) 30 77 -41 -8 -6 120 123 124
presorted : -105 -101 -90 -69 -46 -67 -39 5 30 -41 (77) -8 -6 120 123 124
presorted : -105 -101 -90 -69 -46 -67 -39 5 30 -41 -8 (77) -6 120 123 124
presorted : -105 -101 -90 -69 -46 -67 -39 5 30 -41 -8 -6 (77) 120 123 124
presorted : -105 -101 -90 -69 -46 -67 -39 5 (-41) 30 -8 -6 77 120 123 124
presorted : -105 -101 -90 -69 -46 -67 -39 (-41) 5 30 -8 -6 77 120 123 124
presorted : -105 -101 -90 -69 -46 -67 (-41) -39 5 30 -8 -6 77 120 123 124
presorted : -105 -101 -90 -69 (-67) -46 -41 -39 5 30 -8 -6 77 120 123 124
presorted : -105 -101 -90 -69 -67 -46 -41 -39 5 -8 (30) -6 77 120 123 124
presorted : -105 -101 -90 -69 -67 -46 -41 -39 5 -8 -6 (30) 77 120 123 124
presorted : -105 -101 -90 -69 -67 -46 -41 -39 (-8) 5 -6 30 77 120 123 124
presorted : -105 -101 -90 -69 -67 -46 -41 -39 -8 -6 (5) 30 77 120 123 124
0.000 seconds
(56 swaps per iterations)
Ordered data (16 values) : -105 -101 -90 -69 -67 -46 -41 -39 -8 -6 5 30 77 120
123 124
And with this output, it seem me evident that the new sort is very more
efficient :)
*********************************
*Test modified bubble_sort algo *
*********************************
(nbiter=1, size=16, nsorted=(8+8)
presorted : -105 [77 -101 -90 -46 124 -67 -39 30 123 -41 (5) -6 -69 -8 120 ]
presorted : -105 -101 [(77) -90 -46 124 -67 -39 30 123 -41 5 -6 -69 -8 120 ]
presorted : -105 -101 -90 [(77) -46 124 -67 -39 30 123 -41 5 -6 -69 -8 120 ]
presorted : -105 -101 -90 -69 [-46 124 -67 -39 30 123 -41 5 -6 (77) -8 120 ]
presorted : -105 -101 -90 -69 -67 [124 (-46) -39 30 123 -41 5 -6 77 -8 120 ]
presorted : -105 -101 -90 -69 -67 -46 [(124) -39 30 123 -41 5 -6 77 -8 120 ]
presorted : -105 -101 -90 -69 -67 -46 -41 [-39 30 123 (124) 5 -6 77 -8 120 ]
presorted : [-105 -101 -90 -69 -67 -46 -41 -39 30 123 (120) 5 -6 77 -8 ] 124
presorted : [-105 -101 -90 -69 -67 -46 -41 -39 30 (-8) 120 5 -6 77 ] 123 124
presorted : [-105 -101 -90 -69 -67 -46 -41 -39 30 -8 (77) 5 -6 ] 120 123 124
presorted : [-105 -101 -90 -69 -67 -46 -41 -39 30 -8 (-6) 5 ] 77 120 123 124
presorted : [-105 -101 -90 -69 -67 -46 -41 -39 (5) -8 -6 ] 30 77 120 123 124
presorted : [-105 -101 -90 -69 -67 -46 -41 -39 (-6) -8 ] 5 30 77 120 123 124
presorted : [-105 -101 -90 -69 -67 -46 -41 -39 (-8) ] -6 5 30 77 120 123 124
0.000 seconds
(14 swaps per iteration)
Ordered data at the begin (8 values) : -105 -101 -90 -69 -67 -46 -41 -39
No ordered data (0 values) :
Ordered data at end (8 values) : -8 -6 5 30 77 120 123 124
At the beginning, this algo add the next ordered value a each step and after the
middle of the array this algo make the same thing from the end
And we can stop the process if we want only a limited number of the firsts
ordered values ...
(the same thing can be make on the other side with a inversion of the order of
witch the algo treat the begin and the end, cf. ony to modify the algo for to
treat the end before the begin)
@+
Yannoo
----- Message transféré de LE PETITCORPS Yann <yann.lepetitco...@free.fr> -----
Date : Fri, 18 May 2012 18:24:19 +0200
De : LE PETITCORPS Yann <yann.lepetitco...@free.fr>
Adresse de retour :LE PETITCORPS Yann <yann.lepetitco...@free.fr>
Sujet : [Schrodinger-devel] Possible optimsation of the sort_u8() into
schrofilter.c
À : schrodinger-devel@lists.sourceforge.net
Hi,
I see that the sort_u8() func into schrofilter.c use a basic bubble
sort scheme
=> is it volontary ?
I have make a benchmark between this sort_u8() routine and the standard
qsort() C func and found that the qsort() routine have betters
performances whis big data arrays but lowers performances when it is
used very frequently with very littles arrays to sort
On another side, I have implemented a bubblesort2() func that is
relatively similar to sort_u8() but that seem more performant than
qsort() and sort_u8() when it is very frequently used with a data array
on the range of 32 to 1024 bytes
=> what is the more usual /more frequently array data range that is used
with the sort_u8() func ?
If the data size to sort is lesser than 32, the sort_8() func is
generally the fastest
If the date size to sort is more than 1024, the qsort() func is
generally the fastet
And between this two extremes, my bubblesort2() routine seem generally
outperform the last twos :)
Here is the new function :
static void sort_u8_ext(uint8_t * d, int n, int firsts)
{
int i, j, k;
int x;
int lower, upper, toswap;
int swapped = 0;
if ( (n < 2) || ( firsts < 1) )
return;
if ( firsts >= n )
{
firsts = n -1 ;
}
for (i = 0; i < firsts ; i++)
{
toswap = 0;
lower = d[i];
for( j = i+1; j < n ; j++)
{
if (d[j] < lower )
{
toswap = j;
lower = d[j];
}
}
if ( toswap )
{
x = d[i];
d[i] = d[toswap];
d[toswap] = x;
}
}
for (i = n -1 ; i >= (n - firsts) ; i--)
{
toswap = 0;
upper = d[i];
for( j = i-1 ; j >= firsts ; j--)
{
if (d[j] > upper )
{
toswap = j;
upper = d[j];
}
}
if ( toswap )
{
x = d[i];
d[i] = d[toswap];
d[toswap] = x;
}
}
}
We can set the number of values that we only want to sort at the
beginning and at the end, using the "firsts" variable
(in this case, only the middle of the array isn't sorted, but maximums
and minimums values are automatically sorted first by this func)
Note that the variable "firsts" can too be automatically set to n/2
outside this func for to force this routine to reorder entirely the
array to sort
(and not only the firsts lessers and greaters values of the array)
@+
Yannoo
------------------------------------------------------------------------------
Live Security Virtual Conference
Exclusive live event will cover all the ways today's security and
threat landscape has changed and how IT managers can respond. Discussions
will include endpoint security, mobile security and the latest in malware
threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/
_______________________________________________
Schrodinger-devel mailing list
Schrodinger-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/schrodinger-devel
----- Fin du message transféré -----
------------------------------------------------------------------------------
Live Security Virtual Conference
Exclusive live event will cover all the ways today's security and
threat landscape has changed and how IT managers can respond. Discussions
will include endpoint security, mobile security and the latest in malware
threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/
_______________________________________________
Schrodinger-devel mailing list
Schrodinger-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/schrodinger-devel
