for textmining

쉘정렬

|

이번 글에서는 쉘정렬(selection sort)에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김황남 교수님 강의와 위키피디아를 정리하였음을 먼저 밝힙니다. 예시 그림과 파이썬 코드는 이곳을 참고하였습니다. 그럼 시작하겠습니다.

concepts

쉘정렬은 정렬되지 않은 배열을 정렬하는 데 많은 계산량이 드는 삽입정렬을 개선한 기법입니다. 다음과 같은 배열을 정렬한다고 칩시다.

54, 26, 93, 17, 77, 31, 44, 55, 20

쉘정렬에서는 gap이라는 개념이 있습니다. 데이터를 띄엄띄엄 봐서 정렬한다는 개념인데요. 우선 위 숫자들을 아래와 같이 세 개 서브리스트로 나눕니다(gap=3).

이번엔 서브리스트별로 삽입정렬을 적용해 정렬한 뒤 세 서브리스트를 합칩니다. 다음과 같습니다.

마지막으로 위 리스트(17, 26, 20, 44, 55, 31, 54, 77, 93 )에 삽입정렬을 수행하면 쉘 정렬이 끝납니다. 쉘 정렬에서 gap은 정렬 대상 리스트의 절반으로 시작해 iteration이 돌 때마다 반씩 줄여가게 됩니다.

파이썬 코드

쉘정렬을 파이썬으로 구현한 코드는 다음과 같습니다.

def shellSort(alist):
    sublistcount = len(alist)//2
    while sublistcount > 0:

      for startposition in range(sublistcount):
        gapInsertionSort(alist,startposition,sublistcount)

      print("After increments of size",sublistcount,
                                   "The list is",alist)

      sublistcount = sublistcount // 2

def gapInsertionSort(alist,start,gap):
    for i in range(start+gap,len(alist),gap):

        currentvalue = alist[i]
        position = i

        while position>=gap and alist[position-gap]>currentvalue:
            alist[position]=alist[position-gap]
            position = position-gap

        alist[position]=currentvalue

Comments