이것이 코딩테스트다 챕터 6 정렬

정렬이란?

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

'알고리즘의 효율성'을 쉽게 이해할 수 있어 알고리즘의 초반 단계에서 공부함.

선택 정렬

가장 작은 데이터를 맨 앞의 데이터와 바꾸고, 다음으로 작은 데이터를 선택해 두 번째 데이터와 바꾸는 과정을 반복

선택 정렬 과정

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] // 두 개의 순서를 바꿈

print(array)
//선택정렬의 코드

선택 정렬은 N-1번 만큼 가장 작은 수를 찾기 위해 비교 연산을 진행하기 때문에,

N+(N-1)+(N-2)+...+2 ~= N(N+1)/2 정도의 시간 복잡도를 가지고 있다고 할 수 있고,

이를 가장 큰 차수만 차용하여 O(N^2)형태로 표현할 수 있다.

 

삽입 정렬

데이터를 하나씩 확인하며 각 데이터를 적절한 위치에 삽입하는 방식

데이터가 적절한 위치에 들어가기 전에 그 앞까지는 데이터가 정렬되어있다고 가정함.

따라서 '데이터가 거의 정렬되어 있을 때' 가장 효율적임.

삽입 정렬의 과정

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

for i in range(1, len(array)):
	for j in range(i,0,-1):
    	if array[j] < array[j-1]:
        	array[j],array[j-1] = array[j-1], array[j]
        else:
        	break
 print(array)
 
 //삽입 정렬의 코드

삽입 정렬도 앞선 선택 정렬과 같이 반복문을 두개 연달아 사용했기 때문에

시간 복잡도는 O(N^2)형태라고 볼 수 있다.

퀵 정렬

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다.

'피벗'이라는 기준을 설정해 보통 정렬을 진행하는데, 가장 대표적인 '호어 분할' 방식에서는

리스트의 첫 번째 데이터를 피벗으로 설정해 정렬을 진행한다.

퀵 소트의 진행 과정

앞에서부터 피벗보다 큰 데이터와 작은 데이터의 위치를 변경하며 정렬을 진행한다.

만약 두 데이터의 위치가 서로 엇갈리면(큰 데이터가 뒤쪽, 작은 데이터가 앞쪽)

작은 데이터와 피벗의 위치를 변경하여 분할을 수행한다.

만약 분할된 리스트의 길이가 1인 경우에는 해당 리스트에 대해서 정렬을 중지한다.

피벗의 위치가 변경되면 이후 분할된 리스트에 대해 동일한 작업을 반복하여 정렬을 진행한다.

//가장 대표적으로 사용되는 직관적인 퀵 정렬 소스코드
def quick_sort(li, start, end):
    if start >= end:
        return
    pivot = start
    left = start + 1
    right = end
    while left <= right:
        while left <= end and li[left] <= li[pivot]:
            left += 1
        while right > start and li[right] >= li[pivot]:
            right -= 1
        if left > right:
            li[right], li[pivot] = li[pivot], li[right]
        else:
            li[left], li[right] = li[right], li[left]
    quick_sort(li, start, right - 1)
    quick_sort(li, right + 1, end)

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


quick_sort(array, 0, len(array) - 1)
print(array)

퀵 정렬은 N개의 데이터를 절반씩 나눈다고 도식화 시

O(Nlog(N))의 시간 복잡도를 지닌다.

계수 정렬

가장 큰 데이터와 가장 작은 데이터의 범위가 담기도록 리스트를 생성하고

데이터의 갯수만큼 해당 인덱스에 1을 더해 개수를 저장하고 이후 개수가 저장된 리스트의 앞에서부터 개수만큼 출력

따라서

"데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때"만 사용 가능하다.

array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
count = [0] * (max(li) + 1)
for i in range(len(array)):
	count[array[i]] += 1
for i in range(len(count)):
    for j in range(count[i]):
    	print(i, end = ' ')
//계수 정렬 소스코드