정렬

0.정렬

- 데이터를 특정한 기준에 따라서 순서대로 나열하는 것

- 삽입 정렬, 퀵 정렬, 계수 정렬

 

1. 선택 정렬

- 가장 작은 데이터를 선택해서 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 앞에서 두번째 데이터와 바꾸는 과정을 반복하는 정렬

- 최악의 경우 : 데이터가 내림차순으로 있는 경우

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

#선택 정렬
array = [7,5,9,0 ,3,1,6,2,4,8]

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

 

2. 삽입 정렬

- 특정한 데이터를 특정한 위치에 삽입하는 정렬. 이 때 그 앞까지의 데이터는 이미 정렬되어있다고 가정

- i번째 데이터의 위치를 찾기 위해. i-1번과 자기 자신을 비교 후, i-1번 데이터보다 작으면 왼쪽으로 탐색하며 본인의 자리를 찾고, i-1번 데이터보다 크면 그 자리에 그대로 있는다. 이 때 i는 1 (0이 첫번째 일때)번째 데이터부터 탐색한다.

- 최악의 경우: 데이터가 내림 차순으로 정렬되어있을 때

- 시간 복잡도: O(N^2) , 하지만 현재 데이터가 거의 정렬되어 있을수록 매우 빠르게 동작하며 최선의 경우 O(N)이 될 수 있다. 

#삽입 정렬
array = [7,5,9,0,3,1,2,4,8]

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

3. 퀵 정렬

- 정렬 알고리즘 중 가장 많이 사용되는 알고리즘(퀵, 병합)

- 기준 데이터(pivot)을 설정하고, 그보다 큰 데이터와 작은 데이터의 위치를 바꾼다.

ex) 호어 분할 : 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾아 두 위치를 바꿈. 단 왼쪽부터 찾는 값과 오른쪽부터 찾는 값의 위치가 엇갈린다면, "작은 데이터"와 pivot의 위치를 변경한다.

- 최악의 경우: 배열이 오름차순 혹은 내림차순 정렬되어있는 경우

- 시간 복잡도 : 최악의 경우 O(N^2), 최선의 경우(모든 원소가 동일) O(1), 평균 (NlogN) -- 데이터가 N개 일 때 평균 logN만큼의 그룹이 생성됨

array = [5,7,9,0,3,1,6,2,4,8]

def quick_sort(array, start, end):
	if start >= end: #원소가 1개인 경우 종료
    	return
    pivot = start
    left = start + 1
    right = end
    while left <= right:
    	#왼쪽에서부터 피벗보다 큰 데이터의 위치 찾기
        while left <= end and array[left] <= array[pivot]:
        	left += 1
        
        #오른쪽에서부터 피벗보다 작은 데이터의 위치 찾기
        while right >= start end array[right] >= array[pivot]:
        	right -= 1
        #왼쪽 데이터와 오른쪽 데이터의 위치가 바뀌었을 경우 피벗 교체
        if left > right:
        	array[pivot],array[right] = array[right], array[pivot]
         else:
         	array[left],array[right] = array[right], array[left]
    
    #리스트 분할 이후 왼쪽과 오른쪽에서 각각 정렬 수행
    quick_sort(array,start,right-1)
    quick_sort(array,right+1,end)
 
 quick_sort(array,0,len(array)-1)
 print(array)

 -- 파이썬에 최적화된 코드

array = [5,7,9,0,3,1,6,2,4,8]

def queick_sort(array):
	#리스트 원소가 1개면 종료
    if len(array) <= 1:
    	return array
    
    pivot = array[0]
    tail = array[1:] #피벗을 제외한 리스트
    
    left_side = [x for x in tail if x <= pivot] #피벗 기준 작은 값들로 배열 생성
    right_side = [x for x in tail if x > pivot] #피벗 기준 큰 값들로 배열 생성
    
    #왼쪽,오른쪽으로 분할한 부분에서 각각 정렬 수행 후, 전체 리스트 반환
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)
  
print(quick_sort(array))

 

4. 계수 정렬

- 특정 조건이 부합할 때만 사용가능 하지만 매우 빠른 정렬 방법

- 모든 데이터가 양의 정수이며, 크기가 제한되어 있을때 사용 가능 ( 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을때)

- 정렬 방법: 모든 범위의 데이터가 남길 수 있는 리스트를 선언 후, 데이터 값과 동일한 인덱스의 데이터를 1씩 증가시킴(counting). 결과적으로 각 데이터가 몇 번 등장했는지 기록되므로 해당 등장 횟수만큼 출력

- 시간 복잡도: 개수가 N, 최댓값이 k일 경우, 최악의 경우에도 O(N+K)

array = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]

#모든 범위를 포함하는 리스트 선언
count = [0] * (max(array) + 1)

#각 array에 데이터가 몇 개 저장되어 있는지 카운팅
for i in range(len(array)):
	count[array[i]] += 1

#출력
for i in range(len(count)):
	for j in range(count[i]);
    	ptint(i, end = ' ') #띄어쓰기를 구분으로 하며, 등장 횟수만큼 인덱스 출력

 

5. 정렬 라이브러리

- sorted() 함수/ 집합 자료형 혹은 딕셔너리 자료형을 입력받아서 정렬된 list를 출력 

- 시간복잡도 : 최악의 경우 O(NlogN)