Yu's Algolithm Note

버블(Bubble)

옆에 있는 값과 비교하여 더 작은 값을 반복적으로 앞으로 보내는 알고리즘

(앞에서 부터 큰 값을 뒤로 보내는 것과 같음)

구현이 가장 쉽지만 가장 비효율적인 알고리즘 : 매번 스왑을 해야하기 때문

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

코드

# 스왑 메소드
def swap(a, b):
    temp = a
    a = b
    b = temp
    return (a, b)
# 정렬할 리스트 입력
list = list(map(int, input("버블 정렬할 숫자를 띄어쓰기로 구분하여 입력 : ").split(' ')))
n = len(list)
# 버블 정렬
for i in range(0, n):
    for j in range(1, n-i):
        if list[j-1] > list[j]:
            list[j - 1], list[j] = swap(list[j-1], list[j])
# 정렬된 리스트 출력
for i in list:
    print(i, end=' ')

선택 (Selection)

가장 작은 것을 선택해서 제일 앞으로 보내는 알고리즘

가장 윈시적이고 기초적인 방법이며 비효율적임

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

코드

# 스왑 메소드
def swap(a, b):
    temp = a
    a = b
    b = temp
    return (a, b)
# 정렬할 리스트 입력
list = list(map(int, input("선택 정렬할 숫자를 띄어쓰기로 구분하여 입력 : ").split(' ')))
n = len(list)
# 선택 정렬
index = 0
for i in range(0, n):
    min = 9999
    for j in range(i, n):
        if min > list[j]:
            min = list[j]
            index = j
    list[i], list[index] = swap(list[i], list[index])
# 정렬된 리스트 출력
for i in list:
    print(i, end=' ')

삽입 (Insert)

각 숫자를 적절한 위치에 삽입하는 알고리즘

(뒤로 가면서 앞의 숫자 크기를 보고 그 사이에 적절히 삽입)

선택, 버블 정렬에 비해 필요한 경우에만 위치를 바꿔 좀 더 효율적임

미리 어느정도 정렬이 되어 있다면 아주 빠르게 끝낼 수 있음

시간 복잡도 : O(N^2) (최악의 경우)

코드

# 스왑 메소드
def swap(a, b):
    temp = a
    a = b
    b = temp
    return (a, b)
# 정렬할 리스트 입력
list = list(map(int, input("삽입 정렬할 숫자를 띄어쓰기로 구분하여 입력 : ").split(' ')))
n = len(list)
# 삽입 정렬
    # while 문
for i in range(1, n):
    key = list[i] # key : 정렬할 원소
    j = i - 1
    while j >= 0 and list[j] > key:
        list[j+1] = list[j]
        j = j - 1
    list[j+1] = key
    # for 문
'''for i in range(0, n-1):
    #for j in range(0, i+1):
    #    print(list[j], end=' ')
    for j in range(0, i+1):
        if list[i-j] > list[i-j + 1]:
            list[i-j], list[i-j + 1] = swap(list[i-j], list[i-j + 1])
    #print("")'''
# 정렬된 리스트 출력
for i in list:
    print(i, end=' ')

퀵 (Quick)

대표적인 '분할 정복' 알고리즘(Divide and conquer algorithm)으로, 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나누는 것을 반복 하는 알고리즘.

[방법]

기준 값인 피벗(Pivot)이 필요 (보통 첫 번째 원소를 피벗으로 사용함)

기준 값보다 큰 값을 배열의 왼쪽부터, 작은 값을 오른쪽부터 찾음.

작은 값의 인덱스가 큰 값의 인덱스보다 크면, 작은 값과 큰 값을 교환.

작은 값의 인덱스가 큰 값의 인덱스보다 작으면, 피벗 값과 작은 값을 교환.

위 과정을 기준 값의 좌우측에 반복

시간 복잡도:

O(N * logN) (평균)

O(N^2) (최악)

-> 피벗값에 따라 최악의 경우가 생길 수 있음 [ex) 이미 정렬된 배열]

코드

# 스왑 메소드
def swap(a, b):
    temp = a
    a = b
    b = temp
    return (a, b)
# 재귀를 이용하여 퀵 정렬 수행
def quickSort(start, end):
    if start>=end:  # 원소가 1개인 경우 그대로 둠
        return
    pivot = start   # 피벗은 첫번째 원소
    i = start + 1
    j = end
    while i <= j:   # 엇갈릴 때까지 반복
        while(i <= end and list[i] <= list[pivot]):     #끝에 도달하거나 피벗보다 큰 값을 찾을 때까지 반복
            i = i + 1
        while(j > start and list[j] >= list[pivot]):    #피벗에 도달하거나 피벗보다 작은 값을 찾을 때까지 반복
            j = j - 1
        if(i > j):  # 엇갈린 상태(작은 값의 인덱스가 큰 값의 인덱스보다 작으면, 피벗 값과 작은 값을 교환)
            list[pivot], list[j] = swap(list[pivot], list[j])
        else:       # 엇갈리지 않은 상태 (작은 값의 인덱스가 큰 값의 인덱스보다 크면, 작은 값과 큰 값을 교환)
            list[i], list[j] = swap(list[i], list[j])
    quickSort(start, j - 1); # 피벗보다 작은 값들에 대해서도 새로운 피벗을 설정하여 퀵정렬 실행
    quickSort(j + 1, end);     # 피벗보다 큰 값들에 대해서도 새로운 피벗을 설정하여 퀵정렬 실행
# 정렬할 리스트 입력
list = list(map(int, input("퀵 정렬할 숫자를 띄어쓰기로 구분하여 입력 : ").split(' ')))
n = len(list)
# 퀵 정렬
quickSort(0, n-1)
# 정렬된 리스트 출력
for i in list:
    print(i, end=' ')

병합 (Merge)

퀵 정렬과 같은 분할 정복 알고리즘을 사용하는 정렬 알고리즘. 일단 반으로 나누고 나중에 정렬하는 방식

퀵 정렬과 다르게 피벗 값에 상관없이 정확히 반을 나누어 정렬하므로 최악의 경우에도 O(N * logN)의 시간 복잡도를 보장.

[방법]

다 쪼개진 원소들을 합치면서 정렬을 수행

합쳐진 배열은 정렬이 됨

최종적으로 합쳐지면 정렬이된 전체 배열을 얻음

시간 복잡도 : O(N * logN)

코드

# 스왑 메소드
def swap(a, b):
    temp = a
    a = b
    b = temp
    return (a, b)
# 재귀를 이용하여 퀵 정렬 수행
def mergeSort(start, end):
    if end == start:
        return start
    else:
        half = (end - start) // 2
        l = mergeSort(start, half)
        r = mergeSort(half+1, end)
    
        

# 정렬할 리스트 입력
list = list(map(int, input("병합 정렬할 숫자를 띄어쓰기로 구분하여 입력 : ").split(' ')))
n = len(list)
# 병합 정렬
print()
mergeSort(list)
# 정렬된 리스트 출력
for i in list:
    print(i, end=' ')

힙 (Heap)

힙 : 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조

셸

삽입정렬을 보완한 알고리즘

정렬 (Sort)

버블(Bubble)

선택 (Selection)

삽입 (Insert)

퀵 (Quick)

[방법]

병합 (Merge)

[방법]

힙 (Heap)

셸