[정렬]

파이썬 기본 라이브러리: sort(), sorted()

  머지소트 + 삽입정렬

 

1. 선택정렬 

 - 매번 가장 작은 것을 선택

 - O(n^2)

 

array = []

for i in range(len(array):
	min_idx = i
    for j in range(i+1, len(array)): #끝까지 반복
    	if array[min_idx] > array[j]:
        	min_idx = j
    array[i], array[min_idx] = array[min_idx], array[i]

 

2. 삽입정렬

 - 필요할 때만 위치를 바꿈

 - 두 번째부터 정렬시작 + 뒤->앞

   현재 원소보다 앞의 원소들은 오름차순으로 정렬된 상태

   현재 원소보다 작은 원소를 만나면 그 위치에서 멈춤

 - O(n^2) ~ O(n)

    현재 리스트가 거의 정렬된 상태라면 good(비교만 하고 넘어가면 되니까)

array = []

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

 

 

 

3. 퀵 소트

 - pivot을 설정. pivot 기준으로 크면 오른쪽, 작으면 왼쪽 리스트에 넣음. 리스트의 원소가 1개가 될때까지 과정 반복

 - pivot에 따라 성능차이. 

 - O(n^2) ~ O(nlogn)

   데이터가 무작위로 입력되는 경우에 good 

    cf) 삽입정렬과 반대

array = []

#recursion
def quick_sort(array):
	if len(array) <= 1:
    	return array
    
    pivot = array[0]
    search_arr = array[1:] #pivot제외 뒤
    
    left_arr = [x for x in search_array if x < pivot]
    right_arr = [x for x in search_array if x > pivot]
    
    return quick_sort(left_arr) + [pivot] + quicksort(right_arr)

 

 

4. 카운트 소트

 - 데이터의 크기가 제한된 정수형태(1,000,000) + 양수

 - O(n+k) 

    대신, 공간복잡도가 증가

 - 동일한 값을 가지는 중복 데이터가 많을수록 유리

 

array = []
sort_arr = [0]*(max(array)+1)

for e in array:
	sort_arr[e] += 1
    
for i in range(len(sort_arr)):
	for _ in range(sort_arr[i]):
    	print(i)
        
        
        
        
n = int(input())
sort_arr = [0 for _ in range(10001)]
largest = 0

for _ in range(n):
    tmp = int(input())
    sort_arr[tmp] += 1
    if tmp > largest:
        largest = tmp

for i in range(len(sort_arr[:largest+1])):
    if sort_arr[i] == 0:
        continue
    for _ in range(sort_arr[i]):
        print(i)