#!/usr/bin/perl -w #################### #Shpatserman Maria #28.05.2009 #Quick Sort Algoritm #################### use strict; use warnings; ###Function for sorting sub array from L_index to H_index### sub quicksort { my ($array, $L_index, $H_index) = @_; if (($H_index - $L_index) <=0) { return;} elsif (($H_index - $L_index)== 1) { if ($array->[$H_index] < $array->[$L_index]) { ($array->[$H_index], $array->[$L_index]) = ($array->[$L_index], $array->[$H_index]); return; } } my $pivot_index =int(($H_index+$L_index)/2); my $pivot = $array->[$pivot_index]; my $i = $L_index; my $j = $H_index; do { while ($array->[$i] < $pivot) { $i++; } while ($array->[$j] > $pivot) { $j--; } if ($i < $j ) { if (($i != $pivot_index) && ($j != $pivot_index)) { ($array->[$i], $array->[$j]) = ($array->[$j], $array->[$i]); $i++; $j--; } elsif ($i == $pivot_index) { splice (@$array, $L_index, 0, $array->[$j]); splice (@$array, $j+1, 1); $pivot_index++; $i++; } elsif ($j == $pivot_index) { splice (@$array, $H_index+1, 0, $array->[$i]); splice (@$array, $i, 1); $pivot_index--; $j--; } } } while ($i < $j); if ($L_index < ($pivot_index - 1)) { quicksort($array, $L_index, $pivot_index-1); } if ($H_index > ($pivot_index +1)) { quicksort($array, $pivot_index+1, $H_index); } } ###Filling array with data from file. ###First string in the file is number of the elements ###Second string consists numbers wich are delimited with "," or arbitrary number of spaces sub read_array { my ($array, $file_name) = @_; open (INPUT_FILE, "$file_name") || die "Could not open $file_name file\n"; my $Lenght = ; chomp($Lenght); my $line = ; chomp($line); my $i=0; while (($line =~ /(\d+)/g )&&($i<$Lenght)) { $array->[$i]=$1; $i++; } close INPUT_FILE; } ###Filling output file with sorting data sub print_file { my ($array, $file_name, $H_index) = @_; open (OUTPUT_FILE, ">$file_name") || die "Could not open $file_name file\n"; for(my $i=0;$i<=$H_index;$i++){ print OUTPUT_FILE "$array->[$i]\n"; } close OUTPUT_FILE; } my @data_array ; ###Filling data_array with data from file read_array(\@data_array, "input.txt"); ###Applying quicksort algorithm to elements in data_array quicksort(\@data_array,0 , $#data_array); ###Printing results to output file print_file(\@data_array, "output.txt", $#data_array);