Python - Sorting

Sorting

Sorting Algorithm	Best	Avg	Worst
Bubble Sort	\(O(n)\)	\(O(n^2)\)	\(O(n^2)\)
Quick Sort	\(O(n\log{n})\)	\(O(n\log{n})\)	\(O(n^2)\)
Merge Sort	\(O(n\log{n})\)	\(O(n\log{n})\)	\(O(n\log{n})\)
Heapsort	\(O(n\log{n})\)	\(O(n\log{n})\)	\(O(n\log{n})\)
Insertion Sort	\(O(n)\)	\(O(n^2)\)	\(O(n^2)\)
Selection Sort	\(O(n^2)\)	\(O(n^2)\)	\(O(n^2)\)

Bubble Sort

"""
1. adjacent elements 끼리 비교한다. 
2. 어떻게 sorted가 되었는지 판단하는가(종료조건)
    2-1. 첫 pass를 통과하면 마지막 원소는 무조건 가장 큰 원소가 됨
    2-2. 따라서 pass 할 때마다 뒤에서부터 정렬이 되는 알고리즘
    2-3. 그렇기 때문에, pass 후에 range는 뒤에서부터 1씩 줄어들게 하면 된다. (이게 포인트 ✔)
    2-4. 따라서 이중 반복문 수행후에는 종료가 된다. (원소 2개씩 비교하기 때문에)
    2-5. 안쪽 반복문은 index 1부터 시작해서 range end 지점이 1씩 줄어야 한다.
    2-6. 비교할 index를 프린트 해보면 이렇게 나와야 한다.
    (0, 1) (1, 2) (2, 3) (3, 4)
    (0, 1) (1, 2) (2, 3) 
    (0, 1) (1, 2) 
    (0, 1)
==========
index 설정 실패
이유: i,j 두개를 동시에 해야된다고 생각했다.
하나만 해야되는 이유: 어차피 adjacent이기 때문에 하나를 기준으로 +1 해주면 되기 때문이다.
=========
사실 i의 용도는 j를 구하기 위해 필요했던 것 이다.
j를 -1 해주는 이유는 adjacent이기 때문에 j, j+1에서 인덱스가 넘어가 버리기 때문이다.
i는 위해서 얘기한 맨 마지막 원소들을 하나씩 줄이기 위해 사용
==========
arr로 넘어가기 전에 올바른 index 위치를 교환하는지 확인해 볼 것.
"""
myList = list(map(int, input().split()))
# print(myList)
for i in range(len(myList)):
    for j in range(len(myList)-i-1):
        print((j, j+1))
        if myList[j] > myList[j+1]: # need swap since the former is larger.
            myList[j], myList[j+1] = myList[j+1], myList[j]
print(myList)

Quick Sort

• Divide and Conquer

"""
기준점(pivot)을 정한다.
---------------------------------------------------------------
기준점 정하는 기준
- Always pick first element as pivot.  
- Always pick last element as pivot (implemented below)  
- Pick a random element as pivot.  
- Pick median as pivot.  
아마 random이 제일 좋지 않을까?
---------------------------------------------------------------
기준점 보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로
재귀함수를 사용(iterative 방법은?)
종료조건: list의 길이가 2보다 작을 경우
=======================================================
random element 를 pivot으로 해서 구현할 경우
index error 발생
random 으로 구현할 경우 첫번째나 마지막 원소와 pivot 원소를 교환한 후 똑같이 진행
=======================================================

list를 사용해서 재귀호출을 하는 형태의 구현은 메모리 사용 측면에서 비효율적임
큰 사이즈의 입력이 들어왔을 경우 단점이 크게 부각됨
따라서 in-place 정렬이 선호되는 이유이다.
https://www.daleseo.com/sort-quick/

----------- list quick sort --------------
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    lesser_arr, equal_arr, greater_arr = [], [], []
    for num in arr:
        if num < pivot:
            lesser_arr.append(num)
        elif num > pivot:
            greater_arr.append(num)
        else:
            equal_arr.append(num)
    return quick_sort(lesser_arr) + equal_arr + quick_sort(greater_arr)
===================================
optimized quick sort in-place implementation
https://www.geeksforgeeks.org/quick-sort/
=============================
Python QuickSort 최적화에 따른 속도
https://choiseokwon.tistory.com/233
"""
# This Function handles sorting part of quick sort
# start and end points to first and last element of
# an array respectively
import sys
sys.setrecursionlimit(2000)
def partition(start, end, array):
    
    # Initializing pivot's index to start
    pivot_idx = start
      
    # This loop runs till start pointer crosses 
    # end pointer, and when it does we swap the
    # pivot with element on end pointer
    while start < end:          
        # Increment the start pointer till it finds an 
        # element greater than  pivot 
        while start < len(array) and array[start] <= array[pivot_idx]:
            start += 1
        # Decrement the end pointer till it finds an 
        # element less than pivot
        while array[end] > array[pivot_idx]:
            end -= 1

        # If start and end have not crossed each other, 
        # swap the numbers on start and end
        if start < end:
            array[start], array[end] = array[end], array[start]
      
    # Swap pivot element with element on end pointer.
    # This puts pivot on its correct sorted place.
    # Returning end pointer to divide the array into 2
    array[end], array[pivot_idx] = array[pivot_idx], array[end]
    return end
# The main function that implements QuickSort 
def quick_sort(start, end, array):
      
    # if start and end is not overlapped, proceed.
    if (start < end):
        # p is partitioning index, array[p] 
        # is at right place
        p = partition(start, end, array)
          
        # Sort elements before partition 
        # and after partition
        quick_sort(start, p-1, array)
        quick_sort(p+1, end, array)


N = int(input())
array = [int(input()) for _ in range(N)]
# print(array)
# print(quick_sort(array))
quick_sort(0, len(array)-1, array)
# print(array)
for e in array:
    print(e)

Merge Sort

"""
slice notation
slice 시 배열의 복제가 일어나므로 메모리 사용 효율 나쁨
-------------------
1. 수도코드보고 구현
2. 실패시, 코드보고 코멘트 달고 작성해보기
3. 재귀로 구현 완성
4. iterative version 구현하기
"""
"""
MergeSort(arr[], l,  r)
If r > l
     1. Find the middle point to divide the array into two halves:  
             middle m = l+ (r-l)/2
     2. Call mergeSort for first half:   
             Call mergeSort(arr, l, m)
     3. Call mergeSort for second half:
             Call mergeSort(arr, m+1, r)
     4. Merge the two halves sorted in step 2 and 3:
             Call merge(arr, l, m, r)
# In-Place Merge Sort
<https://www.geeksforgeeks.org/in-place-merge-sort/>
# Iterative Merge Sort
<https://www.geeksforgeeks.org/iterative-merge-sort/>
"""


N = int(input())
array = [int(input()) for _ in range(N)]

# def mergeSort(arr):
#     if len(arr) < 2:
#         return arr

#     mid = len(arr) // 2
#     low_arr = mergeSort(arr[:mid])
#     high_arr = mergeSort(arr[mid:])
#     print(low_arr, high_arr, "######")

#     merged_arr = []
#     l = h = 0
#     while l < len(low_arr) and h < len(high_arr):
#         if low_arr[l] < high_arr[h]:
#             merged_arr.append(low_arr[l])
#             l += 1
#         else:
#             merged_arr.append(high_arr[h])
#             h += 1
    
#     merged_arr += low_arr[l:]
#     merged_arr += high_arr[h:]
#     print(merged_arr,' merged arr')
#     return merged_arr

def mergeSort(arr):
    if len(arr) > 1:
  
        # Finding the mid of the array
        mid = len(arr)//2
          
        # Dividing the array elements
        # into 2 halves
        L = arr[:mid]
        R = arr[mid:]
  
        # Sorting the first half
        mergeSort(L)
        # Sorting the second half
        mergeSort(R)
  
        # Copy data to temp arrays L[] and R[]
        i = j = k = 0
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1
  
        # Checking if any element was left
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1
        
        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

  
mergeSort(array)
print(array)


"""
In-place Merge Sort
-------------------
* l is for left index and r is right index of
the sub-array of arr to be sorted
"""
def merge(arr, start, mid, end):
    start2 = mid + 1
 
    # If the direct merge is already sorted
    if (arr[mid] <= arr[start2]):
        return
 
    # Two pointers to maintain start
    # of both arrays to merge
    while (start <= mid and start2 <= end):
 
        # If element 1 is in right place
        if (arr[start] <= arr[start2]):
            start += 1
        else:
            value = arr[start2]
            index = start2
 
            # Shift all the elements between element 1
            # element 2, right by 1.
            while (index != start):
                arr[index] = arr[index - 1]
                index -= 1
 
            arr[start] = value
 
            # Update all the pointers
            start += 1
            mid += 1
            start2 += 1
 
 
def mergeSort(arr, l, r):
    if (l < r):
 
        # Same as (l + r) / 2, but avoids overflow
        # for large l and r
        m = l + (r - l) // 2
 
        # Sort first and second halves
        mergeSort(arr, l, m)
        mergeSort(arr, m + 1, r)
 
        merge(arr, l, m, r)

"""
Iterative Merge Sort
"""
def merge(left, right):
    if not len(left) or not len(right):
        return left or right
 
    result = []
    i, j = 0, 0
    while (len(result) < len(left) + len(right)):
        if left[i] < right[j]:
            result.append(left[i])
            i+= 1
        else:
            result.append(right[j])
            j+= 1
        if i == len(left) or j == len(right):
            result.extend(left[i:] or right[j:])
            break

    return result

def mergesort(list):
    if len(list) < 2:
        return list
 
    middle = int(len(list)/2)
    left = mergesort(list[:middle])
    right = mergesort(list[middle:])

    return merge(left, right)

Heap Sort

"""
1. 수도코드보고 구현
2. 실패시, 코드보고 코멘트 달고 작성해보기
3. 재귀로 구현 완성
4. iterative version 구현하기
----------------------------------------
https://www.geeksforgeeks.org/heap-sort/
----------------------------------------
__author__ = 'Minsuk Heo'
#=======================================================================
#  Title: Heapsort
#
#  Statement:
#  Given a disordered list of integers (or any other items),
#  rearrange the integers in natural order.
#
#  Sample Input: [8,5,3,1,9,6,0,7,4,2,5]
#  Sample Output: [0,1,2,3,4,5,5,6,7,8,9]
#
#  Time Complexity of Solution:
#  Best O(nlog(n)); Average O(nlog(n)); Worst O(nlog(n)).
#
#  Approach:
#  Heap sort happens in two phases. In the first phase, the array
#  is transformed into a heap. A heap is a binary tree where
#  1) each node is greater than each of its children
#  2) the tree is perfectly balanced
#  3) all leaves are in the leftmost position available.
#  In phase two the heap is continuously reduced to a sorted array:
#  1) while the heap is not empty
#  - remove the top of the head into an array
#  - fix the heap.
#  Heap sort was invented by John Williams not by B. R. Heap.
#
#  MoveDown:
#  The movedown method checks and verifies that the structure is a heap.
#
#  Technical Details:
#  A heap is based on an array just as a hashmap is based on an
#  array. For a heap, the children of an element n are at index
#  2n+1 for the left child and 2n+2 for the right child.
#
#  The movedown function checks that an element is greater than its
#  children. If not the values of element and child are swapped. The
#  function continues to check and swap until the element is at a
#  position where it is greater than its children.
#=======================================================================
# 마지막에 있는 노드부터 순회하면서 swap하면 되는데, 
# leaf 노드(자식노드가 없는)의 경우는 필요없기 때문에,
# p의 값을 아래와 같이 설정함으로써(이진트리의 특징을 활용)
# leaf 노드의 parent 노드 중에서 마지막 index부터 시작을 한다.
# p를 구했으니 이제 siftdown을 수행한다.
# ----------------------------------
# "siftdown"
# 1. 현재 노드의 child node 의 값이 현재 node의 값보다 크다면 SWAP
# 1-1. swap 후에 부모 노드였다가 자식노드로 바뀐 노드에 대해 자식노드를 다시 확인하는 것을 반복.
"""


def heapsort(a):

    
    def siftdown(a, i, size):
        l = 2*i + 1
        r = 2*i + 2
        largest = i
        if l <= size-1 and a[l] > a[i]:
            largest = l
        if r <= size-1 and a[r] > a[largest]: # 자식노드 2개중 큰 것을 largest 변수에 넣어야 하기 때문에, r에서는 largest와 r을 비교
            largest = r
        if largest != i: # largest가 i와 다르다면, 즉, largest가 변경되었다면, swap을 해주고 siftdown
            # SWAP
            a[i], a[largest] = a[largest], a[i]
            siftdown(a, largest, size)

    def heapify(a, size):
        
        p = (size//2)-1 
        while p>=0:
            siftdown(a, p, size)
            p -= 1

    size = len(a)
    heapify(a, size) # MAX HEAP
    end = size-1
    while(end > 0):
        # root와 end를 swap 해준 후
        # root를 siftdown 해주면 정렬이 된다.
        # (swap된 노드(root에서 swap했으므로 현재는 end노드)는 siftdown에서 배제된 상태로 siftdown 진행된다.)
        # (root는 heapify된 후 이므로 최고 혹은 최소이기 때문에)
        a[0], a[end] = a[end], a[0]
        siftdown(a, 0, end) # root node 부터 siftdown을 진행
        end -= 1

arr = [1,3,2,4,9,7]
heapsort(arr)
print(arr)