Velocity Reviews > Ranking an array (with ties and tollerances)

# Ranking an array (with ties and tollerances)

BartC
Guest
Posts: n/a

 08-19-2011
"Eric Sosman" <(E-Mail Removed)> wrote in message
news:j2hnf3\$8pm\$(E-Mail Removed)...
> On 8/17/2011 4:21 PM, Michael Angelo Ravera wrote:

>> Once sorted, the common case *looks* linear, but I think that the *worst*
>> case is still O(N**2). Maybe you can compare forward testing for equality
>> (or tollerance) and never do any retracing.

>
> Linear.
>
> for (int bgn = 0, end; bgn < size; bgn = end) {
> for (end = bgn; ++end < size; ) {
> ... suitable tests and `break' ...
> }
> }
>
> Visits each array element once and once only, hence linear.

I suppose you could visit each element twice (or a hundred times) and it
would still be linear?

--
Bartc

Eric Sosman
Guest
Posts: n/a

 08-19-2011
On 8/19/2011 5:54 AM, BartC wrote:
> "Eric Sosman" <(E-Mail Removed)> wrote in message
> news:j2hnf3\$8pm\$(E-Mail Removed)...
>> On 8/17/2011 4:21 PM, Michael Angelo Ravera wrote:

>
>>> Once sorted, the common case *looks* linear, but I think that the
>>> *worst* case is still O(N**2). Maybe you can compare forward testing
>>> for equality (or tollerance) and never do any retracing.

>>
>> Linear.
>>
>> for (int bgn = 0, end; bgn < size; bgn = end) {
>> for (end = bgn; ++end < size; ) {
>> ... suitable tests and `break' ...
>> }
>> }
>>
>> Visits each array element once and once only, hence linear.

>
> I suppose you could visit each element twice (or a hundred times) and it
> would still be linear?

Yes. The point is that the leading term in the number of
visits is C*size for some constant C, not the C*size*size the
O.P. feared.

--
Eric Sosman
http://www.velocityreviews.com/forums/(E-Mail Removed)d

Kenny McCormack
Guest
Posts: n/a

 08-19-2011
In article <j2jrq8\$gnh\$(E-Mail Removed)>,
John Gordon <(E-Mail Removed)> wrote:
>In <j2jrdq\$ibr\$(E-Mail Removed)> (E-Mail Removed) (Kenny
>McCormack) writes:
>
>> >server (I use eternal-september.org). Google Groups is useful for
>> >searching, and find for its own non-Usenet groups, but horrible for
>> >reading and posting to Usenet.

>
>> If it is (so) horrible, then why do so many people use it?

>
>Perhaps because many people don't want to go to the effort of getting
>and using a real newsreader, or are simply unaware that better options
>exist.
>
>Surely you do not mean to imply that popularity equals worth.

What I am saying is that it doesn't do any more good to tell the GG folks
that what they are using is crap than it does to tell the DWTS folks that
they are watching crap. There's a whole lot more of them than there are of
us - and they aren't listening to anything we say.

--
"Remember when teachers, public employees, Planned Parenthood, NPR and PBS
crashed the stock market, wiped out half of our 401Ks, took trillions in
TARP money, spilled oil in the Gulf of Mexico, gave themselves billions in
bonuses, and paid no taxes? Yeah, me neither."

Michael Angelo Ravera
Guest
Posts: n/a

 08-21-2011
OK, so I did an index sort (I used a student's sort for the particular example, but I will do something more effcient later) and then went on to rank and process ties. It looks like I recompared the values for each contestantno more than twice. So, the ranking and reprocessing for ties is linear.

for (temp_idx = 0; temp_idx < SiZe; temp_idx ++)
{
for (num_ties = 0;
(((temp_idx + num_ties + 1) < SiZe) &&
(team_totals [team_index_ranks [temp_idx]] ==
team_totals [team_index_ranks [temp_idx + 1 + num_ties]]));
num_ties ++)
;
for (name_team = 0; name_team <= num_ties; name_team ++)
{
team_total_ranks [team_index_ranks [temp_idx + name_team]] = temp_idx+ 1;
team_total_ties [team_index_ranks [temp_idx + name_team]] = num_ties;
}
temp_idx += num_ties;
}