[Algorithm] 선택정렬, 삽입정렬, 계수정렬

1. 선택정렬

""" 
1. 특징
- average,worst,best : 모두 O(N^2)로 동일

2. 시간 복잡도 : O(N^2)
N + (N-1) + (N-2) + ... + 1 
(N^2+N-2)/2 => O(N^2)

"""
array = [7,4,6,2,1,9,0]

for i in range(len(array)):
    min_index = i #가장 작은 원소의 인덱스
    for j in range(i+1, len(array)):
        print(j, end=' ')
        if array[min_index] > array[j]:
            min_index = j
    print()
    array[i], array[min_index] = array[min_index], array[i] #swap
    

print(array)

 

 

 

2. 삽입정렬

"""
1. 특징
선택정렬보다 효율적임.
현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작.

2. 시간복잡도
- worst : O(N^2)
- average : O(N^2)
- best : O(N)

"""
array = [7,4,6,2,1,9,3] 

for i in range(1, len(array)):
    for j in range(i, 0, -1):
        print(j, end=' ')
        if array[j] < array[j-1]:
            array[j], array[j-1] = array[j-1], array[j]
        else:
            break
    print()
print(array)

 

3. 계수정렬

"""
1. 특징
공간 복잡도는 높지만, 특정 조건 만족시 빠르게 동작
데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을때만 사용 가능
최악의 경우에도 O(N+K)를 보장

2. 시간복잡도 * 공간복잡도도 O(N+K)
- worst : O(N+K)
- average : O(N+K)
- best : O(N+K)

* 최악인 경우 : 데이터가 0, 999999 단 2개일 때
* 효과적인 경우 : 동일한 값을 가지는 데이터가 여러 개 등장할 때

"""
# 가정 : 모든 원소의 값이 0보다 크거나 같다고 가정
array = [7,4,6,2,1,9,3,2] 
# 모든 범위를 포함하는 리스트 선언(0으로 초기화)
count = [0]*(max(array)+1)

for i in array:
    count[i] += 1
for i in range(len(count)):
    for j in range(count[i]):
        print(i, end=' ')

 

 

참고 - https://www.youtube.com/watch?v=KGyK-pNvWos&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=4