삽입정렬 python insertionSort (배열, 링크드리스트로 구현)

삽입정렬

 

출처를 정확히 모르겠음..

 

삽입정렬은 인덱스를 하나씩 이동하며, 이미 정렬된 이전인덱스들과 비교하여 값을 교환하는 방식이다

 

그림에서 볼 수 있듯이 이미 정렬된 값들이 새로운 인덱스보다 큰 경우가 많으면 교환을 많이 해야 하지만!

운이 좋아서 새로운 인덱스의 값이 이미 정렬된 값들의 최댓값보다 크면 과정을 한번 건너뛸 수 있다!

 

그래서 시간복잡도를 보면 빅오는 O(n^2) 이지만 빅오메가는 Ω(n)인 복불복 정렬 알고리즘이다

 

 

배열로 삽입정렬 구현

def sortInsertionInArray(array):

    temp = None

    for i in range(len(array)):

        for j in range(i):

            if array[i-j] < array[i-j-1]:
                temp = array[i-j]
                array[i-j] = array[i-j-1]
                array[i-j-1] = temp

            else:
                break

    return

 

시간복잡도를 획기적으로 줄여주는 else: break 가 삽입정렬의 핵심이다

까먹고 안써도 잘 돌아가지만, 그러면 버블정렬보다도 심각한 최악의 알고리즘이 되버림

 

 

 

링크드리스트로 삽입정렬 구현

 

↓이전글의 링크드리스트가 반드시 필요하다

2022.11.25 - [자료구조] - python 알고리즘용 LinkedList

 

 

def sortInsertion(self):

    if self.head is None:
        return None
    elif self.head.next is None:
        return None

    idx = self.head
    curr = None
    tempValue = None

    while idx is not None:

        curr = idx

        while curr.prev is not None:

            if curr.data < curr.prev.data:
                tempValue = curr.data
                curr.data = curr.prev.data
                curr.prev.data = tempValue

            else:
                break

            curr = curr.prev

        idx = idx.next

    return

 

여기에는 노드를 이동하며 전부 값을 교환시켜주었지만,

링크드리스트로 구현을 할 때는 값을 교환하는 과정을 줄일 수도 있다.

 

값을 교환하며 이동하는게 아니라 선택정렬 처럼 들어갈 위치만 알아내고 두 노드끼리 바꿔치기만 해도 됨!

(그럼 약간 변형된 선택정렬이 아닌가? 싶네)

배열처럼 인덱스 기준의 접근이 아니기 때문에 가능한 방법이다.

약간의 효율성이 증가할 듯 하다.

 

하지만 n^2 앞에서 무슨 의미가 있으리.. 그냥 두기로 했다.

 

나중에 심심하면 시도해 보는걸로