<div id="readability-page-1" class="page"><div><h2 id="선택-정렬selection-sort의-특징">선택 정렬(Selection Sort)의 특징</h2>
<ul>
<li>선택 정렬은 배열을 순회하면서 각 단계에서 배열의 나머지 부분 중에서 <strong>최소값을 찾아 최소값을 해당 단계의 시작점에 위치한 요소와 교환</strong>한다. 이 과정을 반복하여 정렬한다.</li>
<li><strong>제자리 정렬(In-place sorting):</strong> 선택 정렬은 추가적인 배열을 필요로 하지 않으며, 배열 내에서 요소들의 위치를 교환하여 정렬한다.</li>
<li><strong>불안정 정렬(Unstable sort):</strong> 선택 정렬은 동일한 값을 가진 요소의 상대적 순서가 정렬 과정에서 바뀔 수 있다. 동일한 원소가 초기 배열에서 가진 순서를 보존하지 않는다.<ul>
<li>예를 들어, <code>[4, 6, 3, 4, 2, 8]</code> 배열에 중복된 값이 있을 때, 정렬 과정에서 이 두 <code>4</code> 중 어느 하나가 다른 위치로 이동할 때, 그들 사이의 원래 순서가 바뀔 수 있다. 즉, 처음 배열에서 앞에 있던 <code>4</code>가 정렬 후에는 뒤에 있던 <code>4</code> 뒤로 이동할 수 있어, 두 <code>4</code>의 상대적인 순서가 뒤바뀌게된다.</li>
</ul></li>
</ul>
<blockquote>
<p><a href="https://www.toptal.com/developers/sorting-algorithms/selection-sort">selection-sort Animation 참고</a><br>
<a href="https://visualgo.net/en/sorting">sorting 참고</a></p>
</blockquote>
<p>예를 들어, 아래와 같은 배열이 있다.<br>
작은 수부터 큰 수로 나열한다고 했을 때,</p>
<p><strong>첫 번째 순회</strong></p>
<p>배열 전체 <code>[4, 6, 3, 2, 8]</code>에서 최소값 2를 찾아 첫번째 위치의 4와 교환한다.<br>
2와 첫 번째 위치의 4를 교환합니다.<br>
결과: <code>[2, 6, 3, 4, 8]</code></p>
<p><strong>두 번째 순회</strong></p>
<p>남은 배열 <code>[6, 3, 4, 8]</code>에서 최소값 3을 찾아 현재 순회의 시작 위치인 6을 교환한다.<br>
결과: <code>[2, 3, 6, 4, 8]</code></p>
<p><strong>세 번째 순회</strong></p>
<p>남은 배열 <code>[6, 4, 8]</code>에서 최소값 4를 찾아 현재 순회의 시작 위치인 6을 교환한다.<br>
4와 현재 순회의 시작 위치인 6을 교환합니다.<br>
결과: <code>[2, 3, 4, 6, 8]</code></p>
<p><strong>네 번째 순회</strong></p>
<p>남은 배열 <code>[6, 8]</code>에서 6이 이미 최소값이므로 교환 없이 유지한다.<br>
결과: <code>[2, 3, 4, 6, 8]</code></p>
<h2 id="big-o">Big-O</h2>
<ul>
<li>시간 복잡도: O(n²) (best case : O(n²) (이미 정렬이 되어 있는 경우))<ul>
<li>Best: O(n²)</li>
<li>Averrage:&nbsp;O(n²)</li>
<li>Worst:&nbsp;O(n²)</li>
</ul></li>
<li>공간 복잡도: O(1)</li>
</ul>
<h2 id="장점">장점</h2>
<ul>
<li><strong>제자리 정렬(In-place sorting)</strong>: 추가적인 메모리를 사용하지 않고, 주어진 공간만 이용해서 정렬한다.(공간 복잡도: O(1)) 메모리 공간을 절약할 수 있다.</li>
<li><strong>선택 정렬은 교환 횟수가 비교적 적어</strong>, 데이터 이동이 비용이 많이 드는 상황에서 유리할 수 있다.</li>
</ul>
<h2 id="단점">단점</h2>
<ul>
<li><strong>데이터 양이 많아질수록 성능이 좋지 않다.</strong> 대용량 데이터를 처리할 때는 부적합하다.</li>
<li><strong>불안정 정렬</strong>: 동일한 값을 가진 요소의 상대적 순서가 정렬 과정에서 바뀔 수 있다.</li>
<li><strong>최선, 평균, 최악의 경우 모두 O(n²) 시간 복잡도를 가진다.</strong></li>
</ul>
<h2 id="javascript-algorithm">Javascript Algorithm</h2>
<p>아래 소스는 선택 정렬을 알고리즘 구현한 소스이다.</p>
<pre><code>function selectionSort(arr) {
    for(let i = 0; i &lt; arr.length; i++) {
        let index = i;
        for(let j = i + 1; j &lt; arr.length; j++) {
            if(arr[j] &lt; arr[index]) {
                index = [j]
            }
        }
        let temp = arr[i];
        arr[i] = arr[index];
        arr[index] = temp;
    }
    return arr;
}

selectionSort([1, 5, 3, 2, 6]);</code></pre></div></div>

760kry.log

선택 정렬(Selection Sort)의 특징
선택 정렬은 배열을 순회하면서 각 단계에서 배열의 나머지 부분 중에서 최소값을 찾아 최소값을 해당 단계의 시작점에 위치한 요소와 교환한다. 이 과정을 반복하여 정렬한다.
제자리 정렬(In-place sorting): 선택 정렬은 추가적인 배열을 필요로 하지 않으며, 배열 내에서 요소들의 위치를 교환하여 정렬한다.
불안정 정렬(Unstable sort): 선택 정렬은 동일한 값을 가진 요소의 상대적 순서가 정렬 과정에서 바뀔 수 있다. 동일한 원소가 초기 배열에서 가진 순서를 보존하지 않는다.
예를 들어, [4, 6, 3, 4, 2, 8] 배열에 중복된 값이 있을 때, 정렬 과정에서 이 두 4 중 어느 하나가 다른 위치로 이동할 때, 그들 사이의 원래 순서가 바뀔 수 있다. 즉, 처음 배열에서 앞에 있던 4가 정렬 후에는 뒤에 있던 4 뒤로 이동할 수 있어, 두 4의 상대적인 순서가 뒤바뀌게된다.
selection-sort Animation 참고
sorting 참고
예를 들어, 아래와 같은 배열이 있다.
작은 수부터 큰 수로 나열한다고 했을 때,
첫 번째 순회
배열 전체 [4, 6, 3, 2, 8]에서 최소값 2를 찾아 첫번째 위치의 4와 교환한다.
2와 첫 번째 위치의 4를 교환합니다.
결과: [2, 6, 3, 4, 8]
두 번째 순회
남은 배열 [6, 3, 4, 8]에서 최소값 3을 찾아 현재 순회의 시작 위치인 6을 교환한다.
결과: [2, 3, 6, 4, 8]
세 번째 순회
남은 배열 [6, 4, 8]에서 최소값 4를 찾아 현재 순회의 시작 위치인 6을 교환한다.
4와 현재 순회의 시작 위치인 6을 교환합니다.
결과: [2, 3, 4, 6, 8]
네 번째 순회
남은 배열 [6, 8]에서 6이 이미 최소값이므로 교환 없이 유지한다.
결과: [2, 3, 4, 6, 8]
Big-O
시간 복잡도: O(n²) (best case : O(n²) (이미 정렬이 되어 있는 경우))
Best: O(n²)
Averrage: O(n²)
Worst: O(n²)
공간 복잡도: O(1)
장점
제자리 정렬(In-place sorting): 추가적인 메모리를 사용하지 않고, 주어진 공간만 이용해서 정렬한다.(공간 복잡도: O(1)) 메모리 공간을 절약할 수 있다.
선택 정렬은 교환 횟수가 비교적 적어, 데이터 이동이 비용이 많이 드는 상황에서 유리할 수 있다.
단점
데이터 양이 많아질수록 성능이 좋지 않다. 대용량 데이터를 처리할 때는 부적합하다.
불안정 정렬: 동일한 값을 가진 요소의 상대적 순서가 정렬 과정에서 바뀔 수 있다.
최선, 평균, 최악의 경우 모두 O(n²) 시간 복잡도를 가진다.
Javascript Algorithm
아래 소스는 선택 정렬을 알고리즘 구현한 소스이다.
function selectionSort(arr) {
    for(let i = 0; i < arr.length; i++) {
        let index = i;
        for(let j = i + 1; j < arr.length; j++) {
            if(arr[j] < arr[index]) {
                index = [j]
            }
        }
        let temp = arr[i];
        arr[i] = arr[index];
        arr[index] = temp;
    }
    return arr;
}
selectionSort([1, 5, 3, 2, 6]);

선택 정렬(Selection Sort)

댓글