Perl 병합정렬 구현

1 개요[ | ]

Perl 병합정렬 구현
펄 병합정렬 구현

sub merge_sort {
    my ($a) = @_;
    $size = @$a;
    return if $size < 2;
    $bound = int $size/2;
    my @L = @$a[0 .. $bound-1];
    my @R = @$a[$bound .. $size-1];
    merge_sort( \@L );
    merge_sort( \@R );
    for $i (@$a) {
        $i = !@R ? shift @L : !@L ? shift @R
            : @R[0]<@L[0] ? shift @R : shift @L;
    }
}
@arr = (9,1,22,4,0,-1,1,22,100,10);
merge_sort( \@arr );
print join(',',@arr);
# -1,0,1,1,4,9,10,22,22,100

sub merge_sort {
    my ($a) = @_;
    return if @$a<2;
    my $bound = int @$a/2;
    my @L = @$a[ 0 .. $bound-1 ];
    my @R = @$a[ $bound .. $#$a ];
    merge_sort( \@L );
    merge_sort( \@R );
    merge( $a, \@L, \@R );
}
sub merge {
    my ($a, $L, $R) = @_;
    my ($i, $j, $r) = (0, 0, 0);
    while( $i<@$L and $j<@$R ) {
        if( @$L[$i] < @$R[$j] ) { @$a[$r++] = @$L[$i++]; }
        else { @$a[$r++] = @$R[$j++]; }
    }
    @$a[$r++] = @$L[$i++] while $i<@$L;
    @$a[$r++] = @$R[$j++] while $j<@$R;
}
@arr = (9,1,22,4,0,-1,1,22,100,10);
merge_sort( \@arr );
print join(',',@arr);
# -1,0,1,1,4,9,10,22,22,100

sub merge_sort {
    my @a = @_;
    return @a if @a < 2;
    my $k = int @a / 2;
    my @n1 = merge_sort(@a[0 .. $k - 1]);
    my @n2 = merge_sort(@a[$k .. $#a]);
    for $i (@a) {
        $i = !@n2              ? shift @n1
           : !@n1              ? shift @n2
           : $n2[0] >= $n1[0]  ? shift @n1
           :                     shift @n2;
    }
    return @a;
}

my @a = (9,1,22,4,0,-1,1,22,100,10);
printf("%s\n", join ',', merge_sort(@a));
#-1,0,1,1,4,9,10,22,22,100

2 같이 보기[ | ]