[코딩 + 알고리즘 완주반] 16일차. 정렬 알고리즘(버블 정렬, 선택 정렬, 삽입 정렬,공간복잡도)

# 정렬

어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것

 

# 버블 정렬

두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘

큰 숫자를 뒤로 보내기

 

def bubblesort(data):
    for index in range(len(data) - 1):
        swap = False
        for index2 in range(len(data) - index - 1): # 한번 실행할 때마다 뒤에 하나씩 정렬됨- index 뺀 횟수만큼 실행
            if data[index2] > data[index2 + 1]:
                data[index2], data[index2 + 1] = data[index2 + 1], data[index2]
                swap = True
        
        if swap == False: # swap 된게 없는 경우 이미 정렬된 데이터
            break
    return data

# 버블 정렬 시간복잡도

반복문이 2개 O(n^2)

완전 정렬이 되어있는 상태라면 O(n)

 

# 선택 정렬

주어진 데이터 중 최소값을 찾음

해당 최소값을 데이터 맨 앞에 위치한 값과 교체

맨 앞의 위치를 뺀 나머지 데이터를 반복

def selection_sort(data):
    for stand in range(len(data) - 1):
        lowest = stand
        for index in range(stand + 1, len(data)):
            if data[lowest] > data[index]:
                lowest = index
        data[lowest], data[stand] = data[stand], data[lowest]
    return data
       	

 

# 선택 정렬 시간복잡도

 반복문이 2개 O(n^2)

 

# 삽입 정렬

두번째 인덱스부터 시작

해당 인덱스(key) 바로 앞에 있는 데이터부터 비교해서 key값이 더 작으면, 비교한 데이터 값을 뒤 인덱스로 복사

key 값이 더 큰 데이터를 만날때까지 반복, 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동

그 앞은 이미 정렬되어 있으므로 실행하지 않아도 됨

 

def insertion_sort(data):
    for index in range(len(data) - 1):
        for index2 in range(index + 1, 0, -1):
            if data[index2] < data[index2 - 1]:
                data[index2], data[index2 - 1] = data[index2 - 1], data[index2]
            else:
                break
    return data

# 삽입정렬 시간복잡도

반복문이 두개 O(n^2)

완전 정렬이 되어 있는 상태라면 최선은 O(n)

 

# 공간 복잡도

얼마나 많은 저장 공간이 필요한지

 

시간과 공간은 반비례적 경향이 있음

대용량 시스템이 보편화되면서, 공간 복잡도보다는 시간 복잡도가 우선

 

총 필요 저장공간  = 고정공간 (코드 저장공간) + 가변 공간 ( 실행 중 동적으로 필요한 공간)

 

# 공간 복잡도 예제 - 팩토리얼 구하기

# 공간 복잡도 O(1) - n의 값에 상관없이 변수 n, fac, index 만 필요
def factorial(n):
    fac = 1
    for index in range(2, n + 1):
        fac = fac * index
    return fac
    
    
# 재귀함수 - n에 따라 변수 n이 n개 만들어짐 
# 공간 복잡도 O(n)
def factorial(n):
    if n > 1:
        return n * factorial(n - 1)
    else:
        return 1