Algorithm - Sorting Algorithm, 반복문과 재귀 함수

Algorithm

어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법

 

Sorting Algorithm

Sorting Algorithm	공간 복잡도	시간 복잡도			Stable
	최악	최선	평균	최악
Bubble Sort	O(1)	O(n)	O(n^2)	O(n^2)	O
Selection Sort	O(1)	O(n^2)	O(n^2)	O(n^2)	X
Insert Sort	O(1)	O(n)	O(n^2)	O(n^2)	O
Merge Sort	O(n)	O(nlogn)	O(nlogn)	O(nlogn)	O
Quick Sort	O(1)	O(nlogn)	O(nlogn)	O(n^2)	X
Heap Sort	O(1)	O(n)	O(nlogn)	O(nlogn)	X

 

Bubble Sort와 Selection Sort

• Bubble Sort와 Selection Sort 둘 다 최악의 시간 복잡도는 O(n^2)을 가지지만, 버블 정렬은 처음부터 정렬된 배열이 들어오게 되면 1회전만 진행하기 때문에 O(n)의 시간 복잡도를 가질 수 있음
• 하지만, Selection Sort는 정렬을 위한 비교 횟수는 동일하게 많지만, 실제로 교환을 행하는 횟수는 적기 때문에 조금 더 빠르다는 장점을 가지고 있음
• Bubble Sort는 인접한 요소끼리 서로의 값을 비교하기 때문에 중복된 값의 순서가 변하지 않는 Stable 한 알고리즘이고, Selection Sort는 모든 요소를 탐색한 후에 마지막 최솟값과 변경시키기 때문에 Unstable 한 알고리즘

 

Merge Sort와 Quick Sort

• Merge Sort는 분할 후 병합 시점에서 정렬을 실행하는 과정이고, Quick Sort는 Pivot을 기준으로 분할하는 시점에서 정렬을 진행하는 과정
• Merge Sort는 Stable정렬에 속하고, Quick Sort는 Unstable 정렬에 속함

 

 

Factorial

반복문

def factorial(num):
    result = 1
    for i in range(1, num + 1):
        result *= i
    return result

재귀

def factorial(num):
    if num == 1:
        return 1
    return num * factorial(num - 1)

라이브러리

from math import factorial
print(factorial(5))

 

반복문과 재귀 함수

• 반복문
  
  • 명령을 반복적으로 실행시키는 것으로 설정한 조건에 도달할 때까지 반복 실행
  • 제어 조건이 참일 경우 무한 반복이 발생
  • 재귀 함수보다 속도가 빠른 편
  • 코드의 길이가 길어지고 변수가 늘어나서 가독성이 좋지 않음
• 재귀 함수
  • 함수 자체를 계속해서 호출하는 것으로 재귀를 호출하지 않고 함수를 return 시킬 때까지 반복 실행
  • 조건에 수렴하지 않을 경우 무한 재귀가 발생해 스텍 메모리를 초과하는 Stack Overflow가 발생함
  • 반복문에 비해 속도가 느린 편
  • 코드의 길이와 변수가 적다는 장점으로 가독성이 높음
  • Stack Overflow를 방지하기 위해 꼬리 재귀를 사용하기도 함(단, 컴파일러가 최적화를 지원해야 가능)

Stack Overflow
Stack영역의 메모리가 지정된 범위를 벗어날 때 발생
함수를 호출하면 함수의 지역변수, 리턴 값, 주소 값 등이 스택에 저장이 되는데,
재귀 함수를 통해 반복적으로 함수를 호출하게 되면, Stack메모리를 초과하는 현상을 Stack Overflow라고 함

꼬리 재귀(Tail Call Recursion)
꼬리 재귀는 함수 호출을 위한 파라미터의 연산이 일어나는 장소의 차이를 가짐
즉, Return문에 연산이 존재하는지의 차이점

# 일반 재귀
def factorial(num):
    if num == 1:
        return 1
    return num * factorial(num - 1)
    
# 꼬리 재귀
def factorial(num, ans):
    if num == 1
        return ans
    return factorial(num - 1, ans * num)​

꼬리 재귀는 연산이 return문 이전에 발생해 다음 함수 호출 시에 결과만을 전달한다.
이 과정에서 컴파일러가 꼬리 재귀를 최적화하는 과정에서 반복문으로 변경하게 되면서 기존 재귀의 메모리와 성능에 대한 문제를 감소시킬 수 있음 

 

피보나치 수열

반복문

def fibo(num):
    a, b = 1, 1
    if num == 1 or num == 2:
        return 1
    for i in range(1, num):
        a, b = b, a + b
    return a

재귀

def fibo(num):
    if num == 1 or num == 2:
        return 1
    return fibo(num - 1) + fibo(num - 2)

DP

def fibo(num):
    dp = []
	for i in range(num):
    	if i < 2:
        	dp.append(1)
    	else:
        	dp.append(dp[i-2] + dp[i-1])
	return dp

 

---

References

• Wikipedia - 정렬 알고리즘

정렬 알고리즘 - 위키백과, 우리 모두의 백과사전