누구나 구현 할 수 있는 알고리즘 II

선택 정렬의 다양한 구현과 원리 이해

 

이전 게시글에서 선택 정렬이 무엇인지 잠시 소개했습니다. 이번 게시글에서는 선택정렬의 원리와 코드로 다양하게

표현 해보겠습니다.

 

 

 

1. 기본 선택 정렬

기본적인 선택 정렬은 두 개의 중첩 루프를 사용하여 구현됩니다. 바깥 루프는 정렬되지 않은 배열의 각 요소를 순회하고, 내부 루프는 현재 요소에서 배열의 끝까지 가장 작은 요소를 찾아 현재 요소와 교환합니다.

 

def selection_sort(arr):
    N = len(arr)
    for i in range(N-1):
        min_index = i
        for j in range(i+1, N):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]

 

 

 

2.재귀를 이용한 선택 정렬

선택 정렬을 재귀적으로 구현하는 방법은 알고리즘의 반복적인 특성을 함수 호출 스택을 사용해 처리합니다. 재귀 호출을 통해 배열의 각 위치에서 최소값을 찾고, 이를 배열의 앞쪽으로 이동시키는 과정을 반복합니다.

 

def search_min_index(index, value, arr):
    if value == len(arr):
        return index
    if arr[index] > arr[value]:
        index = value
    return search_min_index(index, value+1, arr)

def selection_sort(index, arr):
    if index == len(arr) - 1:
        return
    min_index = search_min_index(index, index+1, arr)
    arr[index], arr[min_index] = arr[min_index], arr[index]
    selection_sort(index+1, arr)

 

3. 깊은 재귀를 통한 선택 정렬

이 방식에서는 모든 비교와 교환 과정을 깊은 재귀 호출을 통해 수행합니다. 이는 코드의 복잡성은 증가하지만, 선택 정렬의 재귀적 특성을 극대화합니다.

def recursive_selection_sort(arr, current=0, compare=None, min_index=None):
    n = len(arr)
    if compare is None and min_index is None:
        compare = current + 1
        min_index = current
    if current == n:
        return arr
    if compare == n:
        arr[current], arr[min_index] = arr[min_index], arr[current]
        return recursive_selection_sort(arr, current + 1)
    if arr[compare] < arr[min_index]:
        min_index = compare
    return recursive_selection_sort(arr, current, compare + 1, min_index)

 

4.선택 정렬의 시각화

선택 정렬 과정을 시각화하는 것은 알고리즘의 작동 원리를 이해하는 데 매우 유용합니다. 아래의 구현에서는 각 단계에서 배열의 상태를 이미지로 저장하고 이를 GIF로 변환하여 시각적으로 표현합니다. 다음 코드를 직접 튜닝하여 실험해보시면 이해도 잘 되실 것이고 더 의미있는 학습 과정이 될 거 같습니다.

 

import numpy as np
import matplotlib.pyplot as plt
import imageio.v2 as imageio

def selection_sort(arr):
    images = []
    for i in range(len(arr)):
        min_idx = i
        for j in range(i+1, len(arr)):
            if arr[min_idx] > arr[j]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
        fig, ax = plt.subplots(figsize=(10, 6))
        ax.bar(range(len(arr)), arr, color='white')
        ax.set_facecolor('black')
        ax.set_title('Selection Sort Step {}'.format(i + 1), color='white')
        ax.set_xlabel('Index', color='white')
        ax.set_ylabel('Value', color='white')
        ax.tick_params(colors='white')
        plt.savefig(f'step{i}.png')
        plt.close()
        images.append(imageio.imread(f'step{i}.png'))
    imageio.mimsave('selection_sort.gif', images, fps=67)