개요

사내의 crowi에 붙이고 있던 기사를 모처럼이므로 이쪽으로 이동했습니다.

1년 반전 정도에 알고리즘의 공부를 하고 있을 때의 남은 이름입니다.
「프로그래밍 콘테스트 공략을 위한 알고리즘과 데이터 구조」를 참고로 그림을 작성해 프로그램을 썼습니다만, 솔직히, 「참고」에 붙인 어플리케이션 쪽이 알기 쉽습니다.

선택 정렬

A[N]
N 개의 정수로 구성된 배열


i
정렬되지 않은 부분의 시작을 나타내는 루프 변수로 배열의 시작에서 끝까지 이동

minj
각 루프의 처리에서 i 번째부터 N-1 번째까지의 요소 중 최소값의 위치

j
정렬되지 않은 부분에서 최소값의 위치 (minj)를 찾는 루프 변수


정렬되지 않은 부분에서 최소값의 위치를 ​​찾고 그 위치의 요소와 정렬되지 않은 부분의 첫 번째 요소를 교환합니다.
교환되어 선두에 온 것은 소트 끝난 것으로 한다.
이것을 반복하여, 배열의 선두로부터 작은 순서로 결정된다.

선택 정렬은 분리 된 요소를 교환하기 위해 안정적인 정렬이 아닌가? (여기 좀 모르겠어)

계산량

정렬되지 않은 부분의 최소값을 찾기 위해 각 루프에서 N-1 회, N-2 회, N-3, ..., 1 회 비교가 수행됩니다.
따라서, 항상 (N^2 - N)/2회의 비교가 행해진다.
N^2에 비해 N은 충분히 작기 때문에 무시할 수 있고, 상수인 1/2도 무시할 수 있으므로, 선택 소트는 N^2에 비례한다고 할 수 있다.

문제

입력은 1 행째에 수열의 길이를 나타내는 정수 N, 2 행째에 N 개의 정수가 공백으로 구분되어 주어진다.
출력은, 1행째에 정렬된 수열의 요소를 공백으로 단락지어, 2행째에 교환 횟수를 출력한다.

입력값

6
5 6 4 2 1 3

프로그램

<?php
$arrayCount = trim(fgets(STDIN));
$array = explode(' ', trim(fgets(STDIN)));

list($sortedArray, $sortedCount) = selectSort($arrayCount, $array);

foreach ($sortedArray as $value) {
    echo $value.' ';
}
echo PHP_EOL, $sortedCount, PHP_EOL;

function selectSort($arrayCount, $array)
{
    $sortedCount = 0;
    for ($i = 0; $i < $arrayCount; $i++) {
        $minj = $i;
        for ($j = $i; $j < $arrayCount; $j++) {
            if ($array[$j] < $array[$minj]) {
                $minj = $j;
            }
        }

        $temporary = $array[$i];
        $array[$i] = $array[$minj];
        $array[$minj] = $temporary;
        if ($minj !== $i) {
            $sortedCount++;
        }
    }

    return [$array, $sortedCount];
}

출력 결과

1 2 3 4 5 6 
4

참고

책 프로그래밍 콘테스트 공략을 위한 알고리즘과 데이터 구조

나에게는 너무 어렵다···.

iOS 앱 알고리즘 도감

움직이는 이미지로 해설해 주기 때문에 알기 쉽다.