[perl] 정렬 알고리즘

26 Dec 2023

perl

이 블로그 포스트에서는 Perl을 사용하여 다양한 정렬 알고리즘을 구현하는 방법에 대해 알아보겠습니다. Perl을 사용하여 각 알고리즘을 구현하고, 각 알고리즘의 장단점과 성능 특성을 비교할 것입니다.

버블 정렬

버블 정렬은 인접한 두 원소를 비교하여 정렬하는 알고리즘입니다. Perl을 사용하여 버블 정렬을 구현하는 것은 간단합니다.

sub bubble_sort {
    my @array = @_;
    my $n = scalar @array;
    for my $i (0 .. $n-1) {
        my $swapped = 0;
        for my $j (0 .. $n-$i-2) {
            if ($array[$j] > $array[$j+1]) {
                ($array[$j], $array[$j+1]) = ($array[$j+1], $array[$j]);
                $swapped = 1;
            }
        }
        last unless $swapped;
    }
    return @array;
}

선택 정렬

선택 정렬은 주어진 리스트에서 최소값을 찾아 알맞은 위치로 옮기는 과정을 반복하여 정렬하는 알고리즘입니다. Perl을 사용하여 이 알고리즘을 구현해보겠습니다.

sub selection_sort {
    my @array = @_;
    my $n = scalar @array;
    for my $i (0 .. $n-1) {
        my $min_idx = $i;
        for my $j ($i+1 .. $n-1) {
            $min_idx = $j if $array[$j] < $array[$min_idx];
        }
        ($array[$i], $array[$min_idx]) = ($array[$min_idx], $array[$i]) if ($i != $min_idx);
    }
    return @array;
}

삽입 정렬

삽입 정렬은 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누고, 정렬되지 않은 부분의 원소를 정렬된 부분의 올바른 위치에 삽입하는 과정을 반복하는 알고리즘입니다. Perl을 사용하여 삽입 정렬을 구현해보겠습니다.

sub insertion_sort {
    my @array = @_;
    for my $i (1 .. $#array) {
        my $key = $array[$i];
        my $j = $i - 1;
        while ($j >= 0 && $array[$j] > $key) {
            $array[$j + 1] = $array[$j];
            $j--;
        }
        $array[$j + 1] = $key;
    }
    return @array;
}

병합 정렬

병합 정렬은 분할 정복 알고리즘의 일종으로, 리스트를 반으로 나누어 각각을 정렬하고, 정렬된 부분 리스트를 병합하는 과정을 반복하여 정렬을 완성하는 알고리즘입니다. Perl을 사용하여 병합 정렬을 구현해보겠습니다.

sub merge_sort {
    my @array = @_;
    my $n = scalar @array;
    return @array if $n <= 1;
    my $mid = int($n / 2);
    my @left = merge_sort(@array[0 .. $mid-1]);
    my @right = merge_sort(@array[$mid .. $n-1]);
    return merge(\@left, \@right);
}

sub merge {
    my ($left, $right) = @_;
    my @result;
    while (@$left && @$right) {
        if ($left->[0] <= $right->[0]) {
            push @result, shift @$left;
        } else {
            push @result, shift @$right;
        }
    }
    push @result, @$left if @$left;
    push @result, @$right if @$right;
    return @result;
}

퀵 정렬

퀵 정렬은 분할 정복 알고리즘의 일종으로, 피벗을 기준으로 작은 원소들과 큰 원소들을 분할하여 각각을 정렬하는 알고리즘입니다. Perl을 사용하여 퀵 정렬을 구현해보겠습니다.

sub quick_sort {
    my @array = @_;
    return @array if @array <= 1;
    my $pivot = shift @array;
    my @smaller = grep {$_ < $pivot} @array;
    my @greater = grep {$_ >= $pivot} @array;
    return (quick_sort(@smaller), $pivot, quick_sort(@greater));
}

마무리

이제 Perl을 사용하여 다양한 정렬 알고리즘을 구현하는 방법에 대해 살펴보았습니다. 각 알고리즘의 성능과 특성에 대해 이해한 후, 실제 문제에 적용하여 효율적인 정렬을 수행할 수 있을 것입니다.

목차

버블 정렬

선택 정렬

삽입 정렬

병합 정렬

퀵 정렬

마무리