정렬 | 삽입정렬 | 특이 case 에 적합한 정렬

1. 반복문을 사용한 삽입 정렬

 

• 이 코드는 반복문을 사용하여 배열 내의 각 요소를 적절한 위치로 이동시킵니다.
• 두 개의 반복문을 사용하며, 내부 반복문은 현재 요소를 그보다 앞에 위치한 요소들과 비교하여 적절한 위치로 이동시킵니다.

 

def insertion_sort(seq):
    n = len(seq)
    for i in range(1,n):
        for j in range(i,0,-1):
            if seq[j-1] > seq[j]:
                seq[j-1],seq[j] = seq[j] ,seq[j-1]

arr = [4,5,2,1,9,6,7,8,2,5]
insertion_sort(arr)
print(arr)

 

 

2. 재귀를 사용한 삽입 정렬 (두 개의 함수)

 

• 여기서는 insertion_sort와 selection이라는 두 개의 함수를 재귀적으로 사용하여 정렬을 수행합니다.
• insertion_sort 함수는 주어진 위치에서 시작하여 배열의 시작까지 각 요소를 비교하고 교환합니다.
• selection 함수는 배열을 순회하면서 각 요소를 적절한 위치에 삽입하기 위해 insertion_sort를 호출합니다.

 

arr =[6,5,4,3,2,1]
def insertion_sort(arr,count):
    if count == 0:
        return 
    if arr[count-1] > arr[count]:
        arr[count-1],arr[count] = arr[count],arr[count-1]
    return insertion_sort(arr,count-1)
    
def selection(arr,count=1):
    if count == len(arr):
        return 1
    insertion_sort(arr,count)
    return 1 + selection(arr,count+1)
selection(arr)
print(arr)

 

 

3. 재귀를 사용한 삽입 정렬 (하나의 함수로 구현 )

 

• 이 구현은 단 하나의 재귀 함수를 사용하여 삽입 정렬을 수행합니다.
• position은 현재 정렬할 요소의 위치를, ending_point는 비교를 시작할 위치를 나타냅니다.
• 함수는 자기 자신을 호출하면서 ending_point를 감소시켜 요소를 적절한 위치로 이동시킵니다.

 

 

def insertion_sort(arr,position=1,ending_point=1):
    if position == len(arr):
        return
        
    if ending_point ==0:
        return insertion_sort(arr,position + 1,position+1)
        
    if arr[ending_point-1] > arr[ending_point]:
        arr[ending_point-1],arr[ending_point] = arr[ending_point],arr[ending_point-1]
        
    return insertion_sort(arr,position,ending_point-1)


arr=[6,5,4,3,2,1]
insertion_sort(arr)
print(arr)

 

 

4. 시각화를 포함한 삽입 정렬

 

• 이 코드는 삽입 정렬의 각 단계를 시각화하여 사용자에게 보여주는 방식으로 구현되어 있습니다.
• 그래프를 통해 각 정렬 단계에서 배열의 상태를 시각적으로 나타내며, 최종적으로 이 이미지들을 GIF 파일로 저장하여 정렬 과정을 동적으로 표현합니다.

 

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

def insertion_sort(seq):
    images = []
    n = len(seq)
    for i in range(1, n):
        key = seq[i]
        j = i - 1
        while j >= 0 and key < seq[j]:
            seq[j + 1] = seq[j]
            j -= 1
        seq[j + 1] = key

        # 배열의 상태를 그래프로 그림
        fig, ax = plt.subplots(figsize=(10, 6))
        ax.bar(range(len(seq)), seq, color='white')  # 하얀색 막대
        ax.set_facecolor('black')  # 검정색 배경
        ax.set_title('Insertion Sort', color='white')  # 타이틀 색상 변경
        ax.set_xlabel('Index', color='white')  # x축 레이블 색상 변경
        ax.set_ylabel('Value', color='white')  # y축 레이블 색상 변경
        ax.tick_params(colors='white')  # 축 눈금 색상 변경
        plt.savefig(f'step{i}.png')
        plt.close()

        # 이미지를 저장
        images.append(imageio.imread(f'step{i}.png'))

    # GIF 생성
    imageio.mimsave('insertion_sort.gif', images, fps=67)

# 예시 배열
arr = np.random.randint(10000, size=200)
insertion_sort(arr)