[알고리즘] 정렬 알고리즘

👨🏼‍🏫 이준희 강사님 fastcampus(알고리즘 이론)

목록의 요소를 특정 순서대로 넣는 알고리즘, 대개 숫자식 순서와 사전식 순서로 정렬

정렬의 시간 복잡도

출처 : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

1. 버블 정렬

가장 느린 알고리즘

### 수도코드(sudo)
Bubblesort(A)
	for i from 1 to A.length
		for j from 0 to A.length -1 
			if A[j] > A[j+1]
				swap a[j] with a[j+1]

def bubblesort(A):
    for i in range(1,len(A)):
        for j in range(0, len(A)-1):
            if A[j] > A[j+1]:
                A[j], A[j+1] = A[j+1], A[j]

bubblesort([2,3,5,1])

2. 병합 정렬

• ‘존 폰 노이만(John von Neumann)’이라는 사람이 제안한 방법 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다.
• 분할 정복(divide and conquer) 방법 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. 분할 정복 방법은 대개 순환 호출을 이용하여 구현한다.
  • 과정 설명
    • 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
    • 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
    • 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.
• 합병 정렬(merge sort) 알고리즘의 구체적인 개념 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.
• 합병 정렬은 다음의 단계들로 이루어진다. 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다. 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다. 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.
• 합병 정렬의 과정 추가적인 리스트가 필요하다. 각 부분 배열을 정렬할 때도 합병 정렬을 순환적으로 호출하여 적용한다. 합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(merge)하는 단계이다.

출처 : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

3. 퀵 정렬

• 오름차순을 기준으로 정렬한다.

출처 : https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

# 퀵 정렬 수도코드
Quicksort(A, lo, hi)
    if lo < hi then

        pivot := partition(A, lo, hi)

        Quicksort(A, lo, pivot -1)

        Quicksort(A, pivot +1 ,hi)
        
#  퀵 정렬 로무토 파티션 함수 수도코드
partition(A, lo, hi)
    pivot := A[hi]
    i := lo
    for j := lo to hi do

        if A[j] < pivot then

            swap A[i] with A[j]
            i := i + 1

    swap A[i] with A[hi]
    return i

def quicksort(A, lo, hi):
    def partition(lo, hi):
        pivot = A[hi]
        left = lo
        for right in range(lo,hi):
            if A[right] < pivot:
                A[left], A[right] = A[right], A[left]
                left += 1
        A[left], A[hi] = A[hi], A[left]
        return left
    
    if lo < hi:
        pivot = partition(lo, hi)
        quicksort(A, lo, pivot -1)
        quicksort(A, pivot+1, hi)