[이것이 코딩테스트다] 정렬-개념

어느덧 벌써 챕터9 정렬까지 오게 되었습니다. 

얼른 개념을 마무리하고 코딩테스트를 위해 

실전 문제들을 풀어봐야하는데...

부지런히 달려보겠습니다!!

---

1. 선택 정렬

선택 정렬 : 항상 가장 작은 것을 선택하는 알고리즘

 

알고리즘 동작 방법

1. 가장 작은 원소를 찾아 리스트의 첫번째 원소와 변경

2. 이미 정렬된 원소를 제외한 리스트에서  가장 작은 원소를 선택해 리스트의 두번째 원소와 변경

3. 이러한 과정을 반복 수행

구현 코드

array = [5,1,3,7,2,9]

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)

[1, 2, 3, 5, 7, 9]

 

 

시간복잡도

구현 방식에따라 오차가 있을 수 있지만 최악의 경우 연산 횟수는, N + (N-1) + (N-2) + ··· + 2 이다. 이는 N × (N + 1) / 2로 표현할 수 있고 이를 빅오 표기법으로 표기하면 O(N²)됩니다.

이는 매우 비효율적인 알고리즘이다. 하지만 코딩테스트에서 특정 리스트에서 가장 작은 데이터를 찾는 일이 잦으므로 소스코드에 익숙해지는 것이 좋습니다.

 

2. 삽입 정렬

삽입 정렬 : 원소를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하는 알고리즘

 

 

알고리즘 동작 방법

두번째 원소부터 시작하여 정렬된 원소들과 비교하여 자신이 들어갈 위치를 찾아서 들어감

 

 

 

구현 코드

array = [5,3,8,1,2,7]

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)

[1, 2, 3, 5, 7, 8]

 

시간복잡도

삽입 정렬의 시간 복잡도는 O(N²)이다. 그러나 현재 리스트 내 원소가 거의 정렬되어있는 상태라면 매우 빠르게 동작하여 최선의 경우 O(N)의 시간 복잡도를 가진다. 이미 정렬되어 있는 경우 퀵알고리즘보다 빠르다는 것을 반드시 기억해야한다.

 

3. 퀵 정렬

퀵 정렬 : 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 서로 바꾸며 정렬해가는 알고리즘

 

알고리즘 동작 방법

1. 리스트의 첫 번째 원소를 피벗으로 정한다.

2. left는 왼쪽에서부터 시작하여 피벗보다 큰 데이터를 찾는다. 

3. right는 오른쪽부터 시작하여 피벗보다 작은 데이터를 찾는다.

4. 만약 left와 right가 교차한다면 right와 피벗을 바꾼다.

    그렇지 않다면, left와 right를 바꾼다.

5. 피벗을 기준으로 왼쪽, 오른쪽 리스트에 대하여 각각 정렬이 완료 될때까지 이를 재귀적으로 반복한다. 

구현코드

퀵정렬은 총 두가지 방법으로 구현이 가능한다. 하나는 전통적인 구현방법이고 두번째는 파이써닉한 구현방법이다. 물론 파이써닉한 구현방법으로 구현시 비교 연산 횟수가 늘어나지만 더 직관적이기 때문에 파이써닉한 구현방법을 기억하길 추천합니다.

 

1. 전통적인 구현 방법

# 전통적인 규현 방법 
array = [5,3,8,4,9,1,6,2,7]

def quick_sort(array, start,end):
    if start >= end:
        return
    
    pivot=start
    left=start+1
    right=end
    while left<=right:
        # 피벗보다 큰 데이터를 찾을때까지 반복
        while left<=end and array[left]<=array[pivot]:
            left+=1
        # 피벗보다 작은 데이터를 찾을때까지 반복
        while right> start and array[right]>array[pivot]:
            right-=1

        if left > right: # 엇갈렸다면 작은 데이터와 피벗을 교체
            array[right], array[pivot] = array[pivot], array[right]
        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)

 

2. 파이써닉한 구현 방법

# 파이써닉한 퀵정렬
array = [5,3,8,4,9,1,6,2,7]

def quick_sort(array):
    # 리스트가 하나 이하의 원소만을 담고 있다면 종료
    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)

 

시간복잡도

퀵 정렬의 시간 복잡도는 O(N㏒N)이다. 이는 O(N²)인 선택정렬, 삽입 정렬과 비교하면 매우 빠르다는 것을 볼 수 있습니다. 그러나 이미 정렬된 데이터의 경우 매우 느리게 동작한다는 것을 꼭 기억해야합니다!! 퀵정렬의 시간복잡도를 수식적으로 증명 하기 보다는 직관적으로 이해해는 것이 좋습니다. 

피벗은 해당 리스트의 중간값으로 반드시 리시트를 반으로 분할한다고 가정할 때 이를 표현하면 위의 그림과 같을 것입니다. 위 그림을 보면 퀵정렬의 시간복잡도는 O(N㏒N)임을 쉽게 알 수 있습니다!

 

 

4. 계수 정렬

계수 정렬 : 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘

                    -> 데이터의 크기 범위가 제한되어 정수형태로 표현할 수 있을 때만 사용!(데이터의 차이가 1,000,000을 넘지 않            을 때 효과적)

 

 

 

알고리즘 동작 방법

1. 원소를 모두 표현할 수 있는 리스트를 만든 후 0으로 초기화한다.

2. 원소를 모두 확인하며 해당 원소와 대응하는 리스트의 인덱스 값을 1씩 증가한다.

3. 최솟값부터 해당하는 숫자만큼 출력한다.

 

 

구현코드

# 계수 정렬
array = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]
# 모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
count = [0] * (max(array)+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=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스를 출력

0 0 1 1 2 2 3 4 5 5 6 7 8 9 9

 

시간 복잡도

계수 정렬의 시간복잡도는 O(N + K)이다. 데이터 개수가 N이라 할 때, 모든 데이터를 확인하여 인덱스를 증가시켜줘야하고, 데이터 중 최댓값이 K라 할 때, 출력할 때 K까지 반복해야하기 때문입니다.

그러나 계수 정렬은 시간 복잡도 보다 공간 복잡도가 더욱 중요합니다. K까지 모두 표현할 수 있는 리스트를 만들어야하기 때문에 수가 너무 커지게 되면 메모리 소비량이 너무 크기 때문입니다. 

---

정렬 파트의 양이 많기 때문에 해당 표스트에서는 개념만 설명하도록 하고

문제는 다른 포스트에 이어서 풀어보도록 하겠습니다!

 

 

 

 

 

사진출처

선택정렬 - https://m.blog.naver.com/jsky10503/221249976761

삽입정렬 - https://t1.daumcdn.net/cfile/tistory/2569FD3854508BE811

퀵정렬 - https://t1.daumcdn.net/cfile/tistory/271D2B3354545F7A13 

퀵정렬 증명 - https://gmlwjd9405.github.io/images/algorithm-quick-sort/sort-time-complexity-etc1.png