Insert & Shell Sort

1. Insert Sort

Insert Sort알고리즘은 주어진 배열을 정렬하는 알고리즘 중 하나입니다.

 

해당 알고리즘은 정렬된 Array를 구축하고,

 

새로운 원소를 정렬된 Array에 Insert하는 알고리즘이어서 Insert 정렬이라고 불립니다.

 

알고리즘은

1. N번째 원소를 뽑는다(0~N-1번째 원소까지는 정렬이 되어있는 상태)

2. N번째 원소를 0~N-1 사이에 정렬된 위치로 이동시킨다.

3. N+1의 원소에서 1~2번 반복

빨간색 화살표는 N번째 원소(Insert할 원소)

이렇게 마지막 원소까지 이동하면 정렬이 완료되게 됩니다.

 

이 알고리즘은

모든 원소를 한번씩 선택(n) 하여 선택된 원소를 정렬된 원소들과 비교(n-1)를 진행하기 때문에

1+2+3+....n-1 = n(n-1)/2 = O(n2)의 시간복잡도를 갖습니다.

 

이때 n-1번을 모두 비교하는게 아니기 때문에, O(n)~O(n2)사이의 성능을 보입니다.

import random
#Generate ordered List
Data = [i for i in range(10)]
#Shuffle ordered list
random.shuffle(Data)


def insert_sort(DT_list):
    for i in range(len(DT_list)):
        #Random List에서 index 0부터 순서대로 Element를 선택합니다.
        #이번에 선택된 Index는 i라고 하겠습니다.
        temp = DT_list[i]        
        j = i
        #i-1번째 Index까지 이미 정렬이 되어있기 때문에, 0~i Index사이에서
        #i번째 Element가 이동할 위치를 찾아서 값을 넣어줍니다.
        while (DT_list[j-1]>temp and j>0):
            #i번째 Element가 이동 하기 위해서 나머지 Element을 한칸씩 밀어줍니다.
            DT_list[j] = DT_list[j-1]
            j = j-1
        #i번째 Element의 위치를 찾아서 값을 정렬시킵니다.
        DT_list[j] = temp                    
    return DT_list
                
insert_sort(Data)
=>[0,1,2,3,4,5,6,7,8,9]

 

2. Shell Sort

위에서 Insert Sort를 살펴봤습니다.

 

하지만 Insert Sort의 경우 원소의 이동에 따른 기존 정렬된 원소들의 이동이 많이 발생합니다.

(=Insert 할 원소의 이동하는 거리가 짧음)

 

Shell Sort는 이러한 단점을 보완하기 위해서 고안된 정렬 알고리즘으로, 기존 배열을 분할하여 Insert Sort를 진행한다고 할 수 있습니다.

 

아래 예제를 보겠습니다.

처음에 배열의 길이에 절반 만큼 떨어진 원소들과 Insert Sort를 진행합니다.

이때 배열의 길이가 n이라고 하면, 원소들 간의 거리는 n/2, Insert Sort시행 횟수는 n/2번이 됩니다.

 

그러면 이제 배열 길이의 절반의 절반만큼 떨어진 원소들간의 Insert Sort를 진행하면

(이때 원소들 간의 거리는 n/4, Insert Sort시행 횟수는 n/4번 입니다)

이렇게 알고리즘을 반복하면, 최종적으로 전체 배열에 Insert Sort를 실시하게 됩니다.

 

그렇다면 그냥 Insert Sort를 하면되지 뭐하러 복잡하게 여러번 나눠서 하느냐?

 

Insert Sort에서 설명했지만 Insert Sort는 기존 배열의 상태에따라 시간복잡도가 O(n)~O(n2)까지 차이가 납니다.

 

이때 기존의 배열이 정렬되어 있을수록 O(n2)보다 O(n)쪽의 시간복잡도를 갖게됩니다.

 

따라서 크게크게 Insert Sort를 진행해서 어느정도 정렬된 배열을 만들고

 

이를 통해서 마지막 Insert Sort의 알고리즘 성능을 높히는, 개선된 Insert Sort 알고리즘이라고 할수있습니다.

 

하지만 미리 정렬하는 과정이 추가되면서 시간복잡도는 O(nlogn) ~ O(n2)의 시간복잡도를 보여줍니다.

 

최소 시간복잡도는 나빠졌지만, 최악의 성능을 보일 경우를 최소화한다고 할 수 있습니다.

 

파이썬으로 구현된 알고리즘입니다.

import random
#Generate ordered List
Data = [i for i in range(10)]
#Shuffle ordered list
random.shuffle(Data)

def shell_sort(DT_list):
    Max = len(DT_list)    
    while Max > 0:        
        for i in range(Max):
            #위에 쓴 Insert Sort 알고리즘과 동일합니다!            
            #첫번째 Cycle에서는 Max = len(DT_list)이기 때문에 아무런일도 일어나지 않습니다.
            for j in range(int(len(DT_list)/Max)):                                                
                #대신 Insert Sort를 List에 통째로 적용하는 것이 아니라
            	#특정 거리만큼 벌어진 Element들만 모아서 진행합니다.
            	#이때 Element사이의 거리는 Max -> Max/2 -> Max/4..순으로 진행하였습니다.
                temp = DT_list[i+j*Max]
                k = j
                while DT_list[i+(k-1)*Max]>temp and k>0:
                    DT_list[i+k*Max] = DT_list[i+(k-1)*Max]
                    k = k-1
                DT_list[i+(k)*Max] = temp                        
        Max = int(round(Max/2,0))
    return DT_list
    

shell_sort(Data)
=>[0,1,2,3,4,5,6,7,8,9]