Data Analysis/파이썬

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

파이어울프 2022. 5. 24. 20:14

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)

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

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]