PERL HELP: List Sorter in Alphabetical Order

This is a program written in Perl

Page 1 of 1

5 Replies - 2656 Views - Last Post: 19 May 2010 - 01:47 PM

#1 Guest_Gerardo*


Reputation:

PERL HELP: List Sorter in Alphabetical Order

Posted 16 May 2010 - 12:42 PM

I'm learning a new language in class and I'm working on a program that takes the strings that the user inputs and adds them to an array. Then the array is sorted in alphabetical order WITHOUT USING the sort(). So really where I'm actually stuck is how to create the sort() from scratch. I already typed an idea as a nested for-loop but that only works for JAVA as I took the idea from it and changed it a bit to be read by Perl. I'm sure the nested for-loop can work with Perl, but I may be writing it in a way that Perl does not recognize it because every time I run the program is skips the for-loop and just prints the list. I'm not asking people to give me the code, but maybe if they can point out clues to where the errors may lie.

Here is the code:
#!/usr/bin/perl

# Asks user to make a list of words/letters
print "Welcome to the Auto-Arranger!\n
Please type your list of words/letters individually,
this program is Case-Sensitive.\n";
@lists = ();
@newLists = ();

#The do-until loop below asks the user to input 
#what they wish to push to a list
#stops asking for an input when the user types "Done".

do {
	print "Type your list, when you're done type 'Done':";
	chomp($element = <STDIN>);
	push(@lists, $element);
} until( $element eq "Done");
pop(@lists);
$lastIndex = scalar(@lists) - 1;

#The for-loop below sorts all elements in lists and
#pushes them to the new array.
for( $a = 0; $s < $lastIndex; $s++ ) {
	for( $b = $a + 1; $b < $lastIndex; $b++ ) {
		if( $lists[$a] cmp $lists[$b] > 0 ) {
			$tmp = $lists[$a];
			$lists[$a] = $lists[$b];
			$lists[$b] = $tmp;
		}
	}
}

print @lists;



Is This A Good Question/Topic? 0

Replies To: PERL HELP: List Sorter in Alphabetical Order

#2 dsherohman   User is offline

  • Perl Parson
  • member icon

Reputation: 227
  • View blog
  • Posts: 654
  • Joined: 29-March 09

Re: PERL HELP: List Sorter in Alphabetical Order

Posted 17 May 2010 - 05:14 AM

View PostGerardo, on 16 May 2010 - 07:42 PM, said:

I'm sure the nested for-loop can work with Perl, but I may be writing it in a way that Perl does not recognize it because every time I run the program is skips the for-loop and just prints the list.


No, actually, it doesn't (although it doesn't get to the end of the lists, but more on that in a minute). Put a print statement in the innermost loop and you'll see that it is executing the loop 2 times for N=3, 6 times for N=4, and 12 times for N=5 (where N is the number of items in the list). Like I said, though, you're not hitting the end of the lists, which is why you're getting (N-1)*(N-2) iterations instead of N*(N-1).

View PostGerardo, on 16 May 2010 - 07:42 PM, said:

I'm not asking people to give me the code, but maybe if they can point out clues to where the errors may lie.


You can get some very good clues by adding "use warnings" at the start of your code. Among other things, this tells us
Argument "foo" isn't numeric in numeric gt (>) at...
and the line number of this line:
if( $lists[$a] cmp $lists[$b] > 0 ) {


Your core problem, then, is operator precedence. That line parses as "if( $lists[$a] cmp ($lists[$b] > 0) )" instead of "if( ($lists[$a] cmp $lists[$b]) > 0 )". Adding some parentheses to force cmp to be evaluated before > instead of after it gets you a working sort!

Mostly.

There's still that issue with not reaching the end of the lists, thanks to those damnable C-style loops and their tendency to produce off-by-one errors. Thankfully, in Perl, you (almost?) never need to use a C-style loop, but can instead use the range operator ("..") and the list iterator form of "for", which is much less prone to such issues:
for my $a (0 .. $lastIndex) {
First the range operator generates a list of consecutive integers starting at 0 and ending at $lastIndex, then the for loops over that list. Changing both loops to this form gives you a completely working sort (and one in much more idiomatic Perl).

A few other general points:
  • In addition to warnings, you should also always "use strict". This will, among other things, require you to declare all your variables by putting "my" before their first appearance.
  • The variables $a and $b are magical (the built-in "sort" uses them), so you should get in the habit of not using those names unless you want to have weird, impossible-to-find bugs once you start using the standard sort.
  • Arrays don't need to be initialized to empty.
  • @newLists was never used, so can be omitted.
  • Normal style in Perl variable naming is to use $all_lower_case_with_underscores rather than camelCase. (Which is kind of odd when you consider that Perl's semi-official mascot is the camel...)
  • If you chomp the newlines off your input, you need to add them back to your output.
  • You can get the last index in an array with $#array rather than (scalar @array - 1).
  • Since you're only checking which of two strings has the greater value, you can use "gt" rather than cmp and >, which avoids your operator precedence issue entirely.
  • You can swap two values using the list assignment ( $a, $b ) = ( $b, $a ) without needing a temp variable.


So, taking all that into account, an idiomatic Perl version of your code. The algorithm and functionality are identical, only the coding style has been changed to protect the innocent:
#!/usr/bin/perl

use strict;
use warnings;

# Asks user to make a list of words/letters
print "Welcome to the Auto-Arranger!\n
Please type your list of words/letters individually,
this program is Case-Sensitive.\n";
my @list;

#The while loop below asks the user to input 
#what they wish to push to a list
#stops asking for an input when the user types "Done".

while (1) {
  print "Type your list, when you're done type 'Done':";
  my $element = <STDIN>;
  last if $element eq "Done\n";
  push(@list, $element);
}
my $lastIndex = $#list;

#The for-loop below sorts all elements in list and
#pushes them to the new array.
for my $i (0 .. $lastIndex) {
  for my $j ($i + 1 .. $lastIndex) {
    if( $list[$i] gt $list[$j] ) {
      # Using array slices because they're more convenient
      # than ($list[$i], $list[$j]) = ($list[$j], $list[$i])
      @list[$i, $j] = @list[$j, $i];
    }
  }
}

print @list;



And sorry if I've given too much information and didn't leave you enough to work out on your own... I have so much fun reviewing people's Perl code on here (and I feel so strongly about teaching good Perl style) that I tend to get a bit carried away...
Was This Post Helpful? 0
  • +
  • -

#3 Guest_Gerardo*


Reputation:

Re: PERL HELP: List Sorter in Alphabetical Order

Posted 17 May 2010 - 08:54 AM

Thank you so much for your help, even though you solved the problem for me I can still learn of my errors by comparing my code to yours. Plus I have the notes that you've written which helps a lot! I just have some questions to clear up that puts me on the confused side...

The code below does the actual swapping if I'm correct? I'm not sure if I'm reading correctly but what this code means is the element from $i to $j is swapped with the code from $j to $i?
@list[$i, $j] = @list[$j, $i];



Putting a 1 in the while loop doesn't really make a difference right? Any number could be put there so that the loop continues to go around until the input is "Done\n" correct? I could have put like a 10 or 50?
while (1) {



Thank you for your time and your help!
Was This Post Helpful? 0

#4 dsherohman   User is offline

  • Perl Parson
  • member icon

Reputation: 227
  • View blog
  • Posts: 654
  • Joined: 29-March 09

Re: PERL HELP: List Sorter in Alphabetical Order

Posted 18 May 2010 - 02:55 AM

View PostGerardo, on 17 May 2010 - 03:54 PM, said:

The code below does the actual swapping if I'm correct? I'm not sure if I'm reading correctly but what this code means is the element from $i to $j is swapped with the code from $j to $i?
@list[$i, $j] = @list[$j, $i];



Close, but not quite. "$i, $j" and "$j, $i" are lists of specific indexes, not ranges, so that line will always swap exactly two elements. Perl will only build a range in an array slice if you use the range operator that I mentioned earlier (".."). Compare:
#!/usr/bin/perl

use strict;
use warnings;

my @array = qw( a b c d e f g h i );

print @array[2, 5], "\n";   # prints cf
print @array[2 .. 5], "\n"; # prints cdef

print @array[5, 2], "\n";   # prints fc
print @array[5 .. 2], "\n"; # prints nothing
print @array[reverse 2 .. 5], "\n"; # prints fedc


(The second-to-last one prints nothing because the range operator only counts up, not down, and 5 > 2. To get a descending range, you need to build the ascending range and reverse it as in the last example.)


View PostGerardo, on 17 May 2010 - 03:54 PM, said:

Putting a 1 in the while loop doesn't really make a difference right? Any number could be put there so that the loop continues to go around until the input is "Done\n" correct? I could have put like a 10 or 50?


Any true value will work, so 10 or 50 would be fine. You could also use "while ('the earth supports life')" if you wanted. :D Anything other than the number 0, the strings '' or '0', or undef (an undefined value) will work. Using 1 in that context is just a matter of convention because the language itself will represent truth as either 1 or -1, depending on the language you're using:
#!/usr/bin/perl

use strict;
use warnings;

print 5 > 2, "\n"; # prints 1

Was This Post Helpful? 0
  • +
  • -

#5 Guest_Gerardo*


Reputation:

Re: PERL HELP: List Sorter in Alphabetical Order

Posted 18 May 2010 - 10:00 PM

Thank you very much, I managed to add a File IO on it as well! Now the only buggy part is when i put a 10 on the txt file it's read as a number 1...
Was This Post Helpful? 0

#6 Guest_Gerardo*


Reputation:

Re: PERL HELP: List Sorter in Alphabetical Order

Posted 19 May 2010 - 01:47 PM

View PostGerardo, on 18 May 2010 - 09:00 PM, said:

Thank you very much, I managed to add a File IO on it as well! Now the only buggy part is when i put a 10 on the txt file it's read as a number 1...


Nevermind, I was told why it did this. Thank you very much for all your assistance.
Was This Post Helpful? 0

Page 1 of 1