Sorting

'''
## 정렬 알고리즘
데이터를 특정한 기준에  따라 순서대로 나열하는 것
일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용됨
'''

'''
1. 선택정렬(selection sort)
- 매번 현재범위에서 가장 작은 데이터를 골라서 앞으로 갖고옴
O(n^2)
'''
import random
import copy
array = [random.randint(0,10) for _ in range(10)]
print(array)

array_n = copy.deepcopy(array)
for i in range(len(array_n)):
    min_idx = i
    for j in range(i,len(array_n)):
        if array_n[min_idx] >= array_n[j]:
            min_idx = j
    array_n[min_idx], array_n[i] = array_n[i], array_n[min_idx] # swap 함수 !
print("selection sort:", array_n)

'''
2. 삽입정렬(insertion sort)
처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입
선택정렬에 비해서 더 빠름, 구현이 좀 더 어려움
2번째 위치의 데이터가 왼쪽보다 더 작다면 왼쪽, 더 크면 머무름 (두 경우만 존재)
O(n^2) - 선택정렬과 마찬가지로 반복문이 2번 중첩됨
이미 정렬되어있을 땐, O(N)의 시간 
'''

array_n = copy.deepcopy(array)
for i in range(1,len(array_n)):
    for j in range(i,0,-1): # i(j의 첫번째 값)부터 시작하며 계속 바꿈
        # print("i:{} j:{} ".format(i,j))
        if array_n[j] < array_n[j-1]:
            array_n[j], array_n[j-1] = array_n[j-1], array_n[j]
        else:
            break
print("Insertion sort:", array_n)

'''
3. 퀵정렬
일반적으로 데이터의 특성 관련없이 사용할 수 있는 정렬 알고리즘(가장 잘 쓰여짐)
작동방법
1. 기준 데이터(pivot) 고름
2. 작은 수들 | pivot | 큰 수들
'''
array_n = copy.deepcopy(array)
def quick_sort(array):
    if len(array) <= 1:
        return array

    pivot = array[0]
    tail = array[1:]

    left = [x for x in tail if x <= pivot]
    right =[x for x in tail if x > pivot]

    return quick_sort(left) + [pivot] + quick_sort(right)

print("quick sort:", quick_sort(array_n))

'''
4. 계수 정렬 (Counting Sort)
- 데이터의 크기 범위가 제한되어 있고, 데이터가 정수 형태로 표현되었을 때
데이터의 개수가 N, 양수 중 최대값이 k일 때 최악의 경우 수행시간 O(N+K) 보장
'''
array_n = copy.deepcopy(array)
max = max(array_n)

new_list = [0] * (max+1)
print("Counting Sort:",end=" ") 
for i in array_n:
    new_list[i] += 1  
for i,j in enumerate(new_list): 
    for _ in range(j):
        print(i,end=" ")