[Python] 정렬 알고리즘

[참조]: https://medium.com/@fiv3star/%EC%A0%95%EB%A0%AC%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-sorting-algorithm-%EC%A0%95%EB%A6%AC-8ca307269dc7

(1) Bubble Sort

설명: 배열안에 연속된 두개의 인자 값을 비교해서 바꿔나가면서 리스트를 정렬

- 시간 복잡도: O(N^2)

- 공간 복잡도: O(N)

def bubbleSort(alist):
  for loop_count in range(len(alist)-1, 0, -1):
    for idx in range(loop_count):
      if alist[idx] > alist[idx+1]:
        tmp = alist[idx]
        alist[idx] = alist[idx+1]
        alist[idx+1] = tmp
  return alist

(2) Selection Sort

설명: 리스트안을 전체를 순회하면서 최소값과 offset위치에있는 인자와 서로 자리 바꿈을 하면서 정렬

- 시간 복잡도: O(N^2)

- 공간 복잡도: O(N)

def selectionSort(alist):
    for offset in range(0,len(alist)-1):
        offset_minValue = offset
        for num in range(offset+1, len(alist)):
            if alist[num] < alist[offset_minValue]:
                offset_minValue = num
        tmp = alist[offset_minValue]
        alist[offset_minValue] = alist[offset]
        alist[offset] = tmp

    return alist

(3) Insertion Sort

설명: 삽입정렬은 이미 정렬이 되어있다면 O(n)의 시간 복잡도를 가짐. 최악의 경우엔 선택정렬과 같은 시간 복잡도를 가짐.

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 #이 부분 잘못쓰신거 같다 (수정함)
    return alist

잘 이해가 안되서 간단한 배열로 변화를 살펴보면...

test = [3,2,1] #일때

index 가 1일때 [즉 [3,2]부분만 정렬 과정]

currentvalue 2

position 1 ==> [3,3]

(while문 종료)

position 0 ==> [2,3]

index가 2일때 [즉 [2,3,1] 정렬 과정]

currentvalue 1

position 2 ==> [2,3,3]

position 1 ==> [2,2,3]

(while문 종료)

position 0 ==> [1,2,3]

(4) Merge Sort

가장 많이 쓰이는 정렬 알고리즘 중 하나 시간복잡도는 O(nlogn).

def mergeSort(alist):
    if len(alist) <= 1:
        return alist

    mid = len(alist) // 2

    leftlist = alist[:mid]
    rightlist = alist[mid:]

    L = mergeSort(leftlist)
    R = mergeSort(rightlist)

    i = j = 0
    result = []

    while i < len(L) and j < len(R):
        if L[i] < R[j]:
            result.append(L[i])
            i+=1
        else:
            result.append(R[j])
            j+=1

    result += L[i:]
    result += R[j:]
    return result

(5) Quick Sort

일반적으로는 O(nlogn)복잡도를 가지지만, 최악의 경우에는 O(n^2) 복잡도를 가짐.

def quicksort(x):
    if len(x) <= 1:
        return x

pivot = x[len(x)//2]
less = []
more = []

for a in x:
    if a < pivot:
        less.append(a)
    elif a > pivot:
        more.append(a)
    else:
        equal = [a]

return quicksort(less) + equal + quicksort(more)

(6) Tim Sort

설명: Merge Sort의 변형이다. Quick Sort가 대부분 사람들이 가장빠른 정렬 알고리즘으로 알고있다고 하는데(저도 그렇고), 사실 그렇지 않다고 한다. 그렇지 않을 경우가 바로 "대부분의 인자들이 정렬이 되어있을 때" 다. 소스코드는 다음과 같다: (세개의 알고리즘: binary_search, insertion_sort, merge함수를 사용해서 만들어짐)

[출저]: https://gist.github.com/nandajavarma/a3a6b62f34e74ec4c31674934327bbd3

def binary_search(the_array, item, start, end):

    if start == end:

        if the_array[start] > item:

            return start

        else:

            return start + 1

    if start > end:

        return start

    mid = (start + end)/ 2

    if the_array[mid] < item:

        return binary_search(the_array, item, mid + 1, end)

    elif the_array[mid] > item:

        return binary_search(the_array, item, start, mid - 1)

    else:

        return mid

def insertion_sort(the_array):

    l = len(the_array)

    for index in range(1, l):

        value = the_array[index]

        pos = binary_search(the_array, value, 0, index - 1)

        the_array = the_array[:pos] + [value] + the_array[pos:index] + the_array[index+1:]

    return the_array

def merge(left, right):

    """Takes two sorted lists and returns a single sorted list by comparing the

    elements one at a time.

    [1, 2, 3, 4, 5, 6]

    """

    if not left:

        return right

    if not right:

        return left

    if left[0] < right[0]:

        return [left[0]] + merge(left[1:], right)

    return [right[0]] + merge(left, right[1:])

def timsort(the_array):

    runs, sorted_runs = [], []

    l = len(the_array)

    new_run = [the_array[0]]

    for i in range(1, l):

        if i == l-1:

            new_run.append(the_array[i])

            runs.append(new_run)

            break

        if the_array[i] < the_array[i-1]:

            if not new_run:

                runs.append([the_array[i-1]])

                new_run.append(the_array[i])

            else:

                runs.append(new_run)

                new_run = []

        else:

            new_run.append(the_array[i])

    for each in runs:

        sorted_runs.append(insertion_sort(each))

    sorted_array = []

    for run in sorted_runs:

        sorted_array = merge(sorted_array, run)

    print sorted_array