in reply to Re^3: Sorting challenge
in thread Sorting challenge

Sorry davido, I should have did it this way instead. Here are the specifications: 
Given the list of numbers, you are to sort them in non decreasing orde
+r.
Input

t – the number of numbers in list, then t lines follow [t <= 10^6].

Each line contains one integer: N [0 <= N <= 10^6]
Output

Output given numbers in non decreasing order.
Example

Input:

5
5
3
6
7
1

Output:

1
3
5
6
7

[download]
I should specify that the input is from a machine- not a human user. So prompting with messages will not give the correct answer either. The site I am working off of is codechef.com.

Replies are listed 'Best First'.
Re^5: Sorting challenge
by davido (Cardinal) on Jul 23, 2013 at 14:59 UTC

    This works, and I like that it uses as few explicit variables as I can manage while still chomping.

    use v5.10;

say for sort { $a <=> $b }
  map { chomp( my $i = <> ); $i } 1 .. <>;

    [download]

    Since it's just a throwaway, I suppose you could even rely on Perl's numification rules, eliminating chomp, and thus further eliminating the use of variables, making it as pure a "filter" as possible:

    print for sort { $a <=> $b }
  map { scalar <> } 1 .. <>;

    [download]

    I also kind of liked this one, but it's more verbose: 

    my $count = <>;
my @numbers;
while( $count-- ) {
  push @numbers, scalar <>;
}
print for sort { $a <=> $b } @numbers;

    [download]

    Dave

[reply]
[d/l]
[select]

      Why not just 

      <>; print sort { $a <=> $b } <>;

      [download]
[reply]
[d/l]

        Because he is supposed to limit input to a user-specified number. By ignoring that specific number, the test harness could throw in extra inputs to verify he's actually checking.


        Dave

[reply]
      Wow, nice davido. However, all of those still gave 'time limit exceeded'. Actually, all of the responses here did. Though they were all far better than my attempt! Here is the link explaining this message from the site:
      http://www.codechef.com/wiki/faq#Why_do_I_get_a_Time_Limit_Exceeded
[reply]

        The incoming list is potentially 10^6 integers long, correct? That's potentially 1_000_000 integers.

        This can be solved, it may involve packing your input into a huge string using pack, appending each int's packed representation onto the same string. Then manually implementing a sort that works in-place within the string, again using pack and unpack.

        Messy! I don't think I want to invest the time in it. :)

        Updated to correct math. ;)

        Actually, 1 million integers in an array shouldn't be a deal-breaker, unless they're severely limiting your memory. My while-loop solution ought to be the most memory friendly. The map solutions generate a list of 1 .. n before sorting the inputs, so you're holding 2M integers rather than 1M in memory.


        Dave

[reply]

In Section Seekers of Perl Wisdom