[알고리즘 기초] 삽입 정렬 Insertion Sorting

삽입 정렬 알고리즘은 한 번에 하나의 항목을 추가하여 최종으로 정렬된 배열을 구축하는 간단한 정렬 알고리즘입니다. 이는 입력 리스트를 반복하면서 각 요소를 이미 정렬된 리스트 부분 내에 올바른 위치에 "삽입"하여 작동합니다.

삽입 정렬 알고리즘의 단계별 설명은 다음과 같습니다:

1. 리스트의 첫 번째 요소부터 시작하며, 이를 정렬된 부분으로 간주합니다.
2. 다음 요소를 가져와서 정렬된 부분 내에 올바른 위치에 삽입합니다.
3. 리스트의 모든 요소에 대해 이 과정을 반복합니다.

이제 Python으로 삽입 정렬 알고리즘을 구현해 보겠습니다:

def insertion_sort(arr):
    # 1부터 len(arr)까지 반복
    for i in range(1, len(arr)):
        key = arr[i]  # 비교할 현재 요소 (arr[0]은 이미 정렬된 것으로 간주)

        # key보다 큰 arr[0..i-1]의 요소를 현재 위치보다 한 칸 오른쪽으로 이동
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1

        # 현재 요소를 올바른 위치에 삽입
        arr[j + 1] = key

# 사용 예시:
unsorted_list = [64, 34, 25, 12, 22, 11, 90]
insertion_sort(unsorted_list)
print("정렬된 배열:", unsorted_list)

이 Python 구현에서 insertion_sort()는 리스트 arr을 입력으로 받아서 해당 리스트를 장소에서 정렬합니다. 알고리즘은 리스트를 반복하면서 두 번째 요소(인덱스 1)부터 시작하며, 첫 번째 요소는 이미 정렬된 것으로 간주합니다. 각 요소마다 정렬된 부분 리스트 내의 요소와 비교하여 올바른 위치로 이동시킵니다.

제공된 리스트 [64, 34, 25, 12, 22, 11, 90]을 사용한 예시에서:

1. 처음에 첫 번째 요소인 64가 정렬된 것으로 간주됩니다.
2. 두 번째 요소 34는 64와 비교되고 더 작으므로 왼쪽으로 이동합니다: [34, 64, 25, 12, 22, 11, 90].
3. 세 번째 요소 25는 64와 34와 비교되며 올바른 위치를 찾을 때까지 왼쪽으로 이동합니다: [25, 34, 64, 12, 22, 11, 90].
4. 이러한 과정을 나머지 요소에 대해서도 반복하여 전체 리스트가 정렬됩니다: [11, 12, 22, 25, 34, 64, 90].

알고리즘이 진행됨에 따라 리스트의 왼쪽 부분은 점점 더 정렬되고, 오른쪽 부분은 정렬되지 않은 부분을 나타냅니다. 최종적으로 전체 리스트가 오름차순으로 정렬됩니다.

아래는 삽입 정렬 알고리즘을 활용한 내림차순/오름차순 정렬 클래스입니다:

class SortNumbers:

    def __init__(self, nums, asc=True):
        self.numbers = nums
        self.isAsc = asc

    def isAscending(self, flag):
        self.isAsc = flag

    def setSort(self):

        for i in range(1, len(self.numbers)):

            key = self.numbers[i]

            j = i - 1

            if self.isAsc:
                while j >= 0 and key < self.numbers[j]:
                    self.numbers[j+1] = self.numbers[j]
                    j -= 1
            else:
                while j >= 0 and key > self.numbers[j]:
                    self.numbers[j+1] = self.numbers[j]
                    j -= 1

            self.numbers[j + 1] = key

    def getSortedNumbers(self):
        return self.numbers

    def getMinNumber(self):
        if self.isAsc:
            minNum = self.numbers[0]
            return minNum
        else:
            minNum = self.numbers[-1]
            return minNum

    def getMaxNumber(self):
        if self.isAsc:
            maxNum = self.numbers[-1]
            return maxNum
        else:
            maxNum = self.numbers[0]
            return maxNum