Index:

1) Insertion sort
2) Quick Sort
3) Merge Sort
4) Heap Sort
5) Radix Sort

---

Sorting:

• 정렬되지 않은 Data를 비교할때는 Θ(n) 비교연산을 수행한다.

• 정렬되어 있는 Data를 비교할때는 Θ(lg(n)) 비교연산을 수행한다.

---

1. Insertion Sort:

출처링크

def insertSort(arr):
    for i in range(1,len(arr)):
        j = i-1
        while(j>=0 and arr[i]<arr[j]):
            j-=1
        
        arr.insert((j+1),arr[i])
        del arr[i+1]
    
    return arr


def main():
    arr = [2,1,5,4,3,8,10]
    arr = insertSort(arr)
    print(arr)

if __name__ == "__main__":
    main()

---

2. Quick sort

• 퀵정렬은 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.

• 분할 정복알고리즘의 하나로, 평균적으로 lg(n)의 시간복잡도로 수행한다.

분할정복이란?

큰 문제를 작은 문제로 분리하고 각각을 해결한다음, 결과를 모아서 원래의 문제를 해결하는 전략

쪼개지고 피벗잡고 왼쪽 오른쪽 recursive -> 쪼개지고 피벗잡고 왼쪽 오른쪽 recursive 반복하다가 쪼개졌는데 한칸이면 종료한다.

def partition(arr,start,end):
    pivot = arr[start]
    left = start+1
    right = end
    while True:
        while left <= end and arr[left] < pivot:
            if left == end:
                break
            left += 1
        
        while right >= 0 and arr[right] > pivot:
            if right == 0:
                break
            right -= 1

        if left >= right:
            break
        else:
            arr[left], arr[right] = arr[right] , arr[left]

    arr[start],arr[right] = arr[right] , arr[start]
    return right

def quickSort(arr,start,end):
    if start < end:
        pivot = partition(arr,start,end)
        quickSort(arr,start,pivot-1)
        quickSort(arr,pivot+1,end)
    
    return arr

a = list(map(int,input().split()))
print(quickSort(a,0,len(a)-1))
        

output:

[20, 74, 35, 84, 20, 50, 83, 15]
[15, 20, 20, 35, 50, 74, 83, 84]

---

3. MergeSort:

참고링크

def merge(left,right):
    result = []
    while (len(left) > 0 or len(right)> 0) :
        if  (len(left) > 0 and len(right) > 0) :
            if  left[0] <= right[0]:
                result.append(left[0])
                left = left[1:]
            else :
                result.append(right[0])
                right = right[1:]
        elif len(left) > 0 :
            result.append(left[0])
            left = left[1:]
        elif len(right) > 0 :
            result.append(right[0])
            right = right[1:] 

    return result

def merge_sort(list):
    if  len(list) <= 1:
        return list
    
    mid = len(list) // 2
    leftList = list[:mid]
    rightList = list[mid:]
    leftList = merge_sort(leftList)
    rightList = merge_sort(rightList)
    return merge(leftList,rightList)




list = [5,3,2,1,6,9,8,7]
list = merge_sort(list)
print(list)

output:

[1, 2, 3, 5, 6, 7, 8, 9]

---

4. HeapSort

---

참고: