Programming Forums - View Single Post - Question with Arrays

Sane · Jan 30th, 2008, 12:58 AM

This is an interesting problem to think about...

Just an aside from further thought. Even if you were to have the worst-case scenario of increasing input, causing the sift and shift to constantly happen to the left-most element, it's not that big a deal. Every time you insert a new value, it's only 5 elements searched to the left, and 5 elements shifted to the right.

This is roughly the equivilent of looking at 10 elements in an array. Generalize this further, and it's as though you were reading the entire array 10 times in a row. Unsurprisingly, reading an array 10 times is faster than sorting that entire array (unless the array is very small). So even if you were fed sorted input, in an attempt to slow down your algorithm, this "semi-sort" still seems more than optimal. But if you were to increase the size of your best array, to say... 25, then the factor increases to 50 array walkthroughs. At which point, you might want to start rethinking the choice of algorithm.

Jan 30th, 2008, 12:58 AM	#3
Sane Programming Guru Join Date: Apr 2005 Posts: 1,788 Rep Power: 5	Re: Question with Arrays - creating and updating 'top 5' list This is an interesting problem to think about... Just an aside from further thought. Even if you were to have the worst-case scenario of increasing input, causing the sift and shift to constantly happen to the left-most element, it's not that big a deal. Every time you insert a new value, it's only 5 elements searched to the left, and 5 elements shifted to the right. This is roughly the equivilent of looking at 10 elements in an array. Generalize this further, and it's as though you were reading the entire array 10 times in a row. Unsurprisingly, reading an array 10 times is faster than sorting that entire array (unless the array is very small). So even if you were fed sorted input, in an attempt to slow down your algorithm, this "semi-sort" still seems more than optimal. But if you were to increase the size of your best array, to say... 25, then the factor increases to 50 array walkthroughs. At which point, you might want to start rethinking the choice of algorithm.