[파이썬] python sorting (bubble, selection, insertion, shell, qucik sort)

Sorting은 요소들을 일정한 기준을 가지고 순서를 만들어 배치를 하는 과정을 이야기 합니다.

 

예를 들면, 단어 목록을 알파벳순으로 또는 길이별로 정렬할 수 있습니다. 도시 목록은 인구, 지역 또는 우편 번호별로 정렬할 수 있습니다.

 

sorting과 관련된 많은 알고리즘들이 존재하는데, sorting을 하는 것은 computer science 에서 중요한 연구 영역임을 방증하기도 하죠.

 

많은 수의 항목을 정렬하기 위해서는 상당한 양의 컴퓨팅 리소스가 필요하게 되는데, 검색과 마찬가지로 정렬 알고리즘의 효율성은 처리하려는 항목의 수와 밀접한 관계를 가지고, 데이터의 양에 따라 어떠한 sorting 알고리즘을 적용하냐에 따라 효율성이 달라지기도 합니다.

The Bubble Sort

 

bubble sort는 바로 옆의 숫자와 비교를 통해 두개의 숫자를 비교해 큰값을 뒤로 밀어내면서 오름차순으로 정렬을 하는 방식입니다.

def bubbleSort(alist):
    for passnum in range(len(alist)-1,0,-1):
        for i in range(passnum):
            if alist[i]>alist[i+1]:
                temp = alist[i]
                alist[i] = alist[i+1]
                alist[i+1] = temp

alist = [54,26,93,17,77,31,44,55,20]
bubbleSort(alist)
print(alist)

일일히 데이터의 수를 비교해줘야하기 때문에 효율이 좋지 않은 알고리즘입니다.

bubble sorting 동작 animation

 

The Selection Sort

def selectionSort(alist):
   for fillslot in range(len(alist)-1,0,-1):
       positionOfMax=0
       for location in range(1,fillslot+1):
           if alist[location]>alist[positionOfMax]:
               positionOfMax = location

       temp = alist[fillslot]
       alist[fillslot] = alist[positionOfMax]
       alist[positionOfMax] = temp

alist = [54,26,93,17,77,31,44,55,20]
selectionSort(alist)
print(alist)

selection sorting은 가장 큰숫자나 작은 숫자를 먼저 선택하여 한곳으로 정렬을 하여 sorting을 하는 방식입니다.

 

The Insertion Sort

def insertionSort(alist):
   for index in range(1,len(alist)):

     currentvalue = alist[index]
     position = index

     while position>0 and alist[position-1]>currentvalue:
         alist[position]=alist[position-1]
         position = position-1

     alist[position]=currentvalue

alist = [54,26,93,17,77,31,44,55,20]
insertionSort(alist)
print(alist)

insert sort는 기준값을 앞의 값들과 하나씩 비교를 통해서 값이 작거나 큰 사이값이 되는 경우 해당 자리로 이동을 하면서 sorting을 하는 방식입니다.

예를들어 위 리스트 중 6번째 숫자인 31을 정렬을 할때,

93과 31을 비교하여 93보다 31일이 작기 때문에 왼쪽으로 이동

77과 31을 비교하여 77보다 31일이 작기 때문에 왼쪽으로 이동

54과 31을 비교하여 54보다 31일이 작기 때문에 왼쪽으로 이동

26과 31을 비교했을때 26보다 31일이 크기 때문에 해당 자리에 insert 하는 방식입니다.

The Shell Sort

shell sort는 sub list를 만든 후 sub list를 먼저 정렬하고, main list에 다시 조합한 후 다시 sub list를 정렬을 반복하는 형식의 sorting 방법입니다.

sublist1은 54, 17, 44

sublist2은 26, 77, 55

sublist3은 93,31,20

으로 각각 세개의 숫자를 뽑아낸 후 정렬을 해줍니다.

정렬을 한뒤 해당 자리의 숫자를 다시 조합하여 main list를 다시 만들어 주게 됩니다.

다시 조합된 리스트는 완전히 정렬된것은 아니지만 일부분 정렬이 된것을 볼 수 있습니다.

 

셀정렬은 어느정도 정렬된 배열에서는 더욱 빠르게 정렬이 가능하다는 사실에 착안한 방법으로 부분 리스트가 어느정도 정렬이 된 상태에서 정렬을 하기 때문에 삽입 정렬이 훨씬 빠르게 수행되는 장점이 있습니다.

 

The Merge Sort

merge sort는 우선 숫자들을 쪼개주게 됩니다.

각각의 쪼개진 sublist들을 두개로 그룹을 만들어 비교를 해준 뒤 단계별로 정렬을 해줍니다.

 

예들들어 54-26 은 26-54로 정렬을 하고, 93-17은 17-93으로 정렬을 해줍니다.

26-54 / 17-93 에서 26과 17을 비교하고, 54와 93을 비교한 뒤 정렬을 해주게 됩니다.

정렬결과는 17-26-54-93이 되게 됩니다.

단계별로 하나씩 비교를 해주게 되는데, log(n)으로 분리가 되고, 다시 합쳐질때는 log(n) 이 되고 각각의 비교를 위해서는 n번의 비교 연산이 발생하게 됩니다.

 

그래서 merge sort는 O(nlogn)이 되게 됩니다.

def mergeSort(alist):
    print("Splitting ",alist)
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i=0
        j=0
        k=0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] <= righthalf[j]:
                alist[k]=lefthalf[i]
                i=i+1
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1

        while i < len(lefthalf):
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j < len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1
    print("Merging ",alist)

alist = [54,26,93,17,77,31,44,55,20]
mergeSort(alist)
print(alist)

위 코드를 실행하면 아래와 같은 결과를 얻을 수 있습니다.

Splitting  [54, 26, 93, 17, 77, 31, 44, 55, 20]
Splitting  [54, 26, 93, 17]
Splitting  [54, 26]
Splitting  [54]
Merging  [54]
Splitting  [26]
Merging  [26]
Merging  [26, 54]
Splitting  [93, 17]
Splitting  [93]
Merging  [93]
Splitting  [17]
Merging  [17]
Merging  [17, 93]
Merging  [17, 26, 54, 93]
Splitting  [77, 31, 44, 55, 20]
Splitting  [77, 31]
Splitting  [77]
Merging  [77]
Splitting  [31]
Merging  [31]
Merging  [31, 77]
Splitting  [44, 55, 20]
Splitting  [44]
Merging  [44]
Splitting  [55, 20]
Splitting  [55]
Merging  [55]
Splitting  [20]
Merging  [20]
Merging  [20, 55]
Merging  [20, 44, 55]
Merging  [20, 31, 44, 55, 77]
Merging  [17, 20, 26, 31, 44, 54, 55, 77, 93]
[17, 20, 26, 31, 44, 54, 55, 77, 93]

The Quick Sort

 

quick sort는 매 그룹마다 pivot을 선정(random 또는 특정기준) 하여 비교를 통해 sorting을 하는 방식입니다.

 

이 방식도 운이 좋은 경우에는 O(nlogn) 연산이 가능해집니다.

 

그러나 pivot을 잘못 고르는 경우에, 예를들어 정렬이 되어 있는데 왼쪽부터 pivot을 뽑게 되면 매번 연산을 해주게 되게 됩니다.

 

이런 경우에 운이 나쁘면 worst case로 O(n^2)가 될 수도 있습니다.

 

이런 경우를 최소화 하기 위해서 'median of 3을 사용하여, [54,26,93,44,21,40,55....] 가 있는 경우 왼쪽의 세게 [54,26,93] 을 뽑은 후 이 중에 중간값인 54를 pivot으로 골라주는 방식입니다. 

 

뽑는 숫자는 3개나 5개.. 등 원하는 만큼 설정을 해주면 됩니다. 이렇게 숫자를 추출하면 극단적인 상황을 피할 수 있게 됩니다.

레프트 마크와 라이트 마크를 설정한 후 한칸씩 내려오면서 비교를 해줍니다.

 

레프트 마크를 하나씩 이동하면서, 가장 왼쪽의 값과 비교를 하게 됩니다.

 

위의 예시를 보면 첫번째 레프트마크는 26으로 지정을 하고,

26과 가장왼쪽의 숫자 54와 비교했을때 26이 더 작기 때문에 레프트 마크를 한칸 이동해줍니다.

 

다음 레프트 마크는 93이 되고, 93가 54를 비교했을때 93이 더 크기 때문에 레프트 마크는 정지를 합니다.

 

이후 라이트 마크 '20'을 지정을 하고, '20'과 54를 비교를 해줍니다.

 

20이 54보다 작은 경우이기 때문에 이 때는 20과 93을 변경해주고 20을 다시 레프트 마크로 지정해줍니다.

 

이 과정을 계속 반복하면서 정렬을 해주는 방식입니다.

quick 는 경우에 따라서 운이 나쁘면 O(n^2)가 될 수 있지만, 이런 경우는 드물게 나타나게 됩니다.

 

sorting 알고리즘 중에서는 quick sorting의 퍼포먼스가 가장 좋다고 하는 것이 일반적입니다.