[ 이코테 강의 ] 정렬 알고리즘

정렬 알고리즘

• 정렬(sorting) : 데이터를 특정 기준에 따라 순서대로 나열하는 것

선택 정렬

• 처리되지 않은 데이터 중 가장 작은 데이터를 선택해 맨 앞의 데이터와 바꾸는 것을 반복
• 처리되지 않은 데이터 중 가장 작은 0 을 선택해 가장 앞의 5와 바꾸고.. 이를 반복
• 탐색 범위는 한번 확인할 때마다 줄어들게됨. 매번 선형탐색을 하는것과 같음 => 이중탐색을 활용할 수 있다

선택 정렬의 시간 복잡도

• 선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다
• N + (N-1) + (N-2)+ ... + 2
• 빅오 표기법으로는O(N^2)

삽입 정렬

• 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입
• 선택 정렬에 비해 구현하기는 힘들지만 효율적이다.

삽입 정렬 소스코드

for i in ragne(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

두번째 데이터부터 마지막 데이터까지 확인하면서 왼쪽에 있는 데이터와 위치를 바꿔줌.

삽입 정렬의 시간 복잡도

• 삽입 정렬의 시간 복잡도는 O(N^2) 이며, 선택 정렬과 마찬가지로 반복문이 두 번 중첩되어 사용됩니다.
• 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작합니다.
  • 최선의 경우 O(N)의 시간 복잡도

퀵 정렬

• 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꿈
• 일반적인 상황에서 가장 많이 사용
• 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘
• 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정

1. 왼쪽에서부터 첫 피벗값보다 큰 값을 고르고, 오른쪽에서는 피벗보다 낮은 값을 골라준다, 그리고 그 값들을 바꿔줌
2. 이렇게 계속 위치를 바꿔준다.
3. 오른쪽에서부터 데이터와 왼쪽으로부터의 데이터가 엇갈리는 상황이 오면 작은 데이터와 피벗 값을 바꿔준다.
4. 이 값을 중심으로 왼쪽은 피벗값보다 작은 데이터, 오른쪽으로는 피벗값보다 큰 데이터,
   • 이 상황을 파티션 / 분할 이라고 한다
5. 그 후 왼쫏과 오른쪽에서 다시 퀵정렬을 수행해주면서 동작한다
6. 정렬 완료

퀵 정렬이 빠른 이유

• 이상적인 경우 분할이 절반씩 일어난다면 전체 연산 횟수로 O(NlogN)을 기대할 수 있다.

퀵 정렬의 시간 복잡도

• 퀵 정렬은 평균 O(NlogN)의 시간 복잡도를 가짐
• 최악의 경우 O(N^2)

소스코드

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 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)
print(array)

소스코드(파이썬의 장점을 살린 방식)

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)

print(quick_sort(array))

계수 정렬

• 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작한다
• 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능하다
• 데이터의 개수가 N, 데이터(야웃) 중 최댓값이 K일 때 최악의 경우에도 수행 시간 O(N+K)를 보장한다.

1. 모든 범위를 담을 수 있는 리스트를 생성한다
2. 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킨다.
3. 결과적으로 리스트의 첫번째 데이터부터 하나씩 그 값만큼 반복해서 인덱스를 출력한다.

공간복잡도가 높지만 빠르게 동작한다

소스코드

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=" ")

계수 정렬의 복잡도 분석

• 시간복잡도와 공간복잡도는 둘아 O(N+K)
• 계수 정렬은 때에 따라서 심각한 비효율성을 초래할 수 있다
  • 만약 데이터가 0과 999999로 단 2개만 존재할 때
• 계수 정렬은 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적으로 사용할 수 있다
  • 성적의 경우 100 점을 맞은 학생이 여러 명일 수 있기 때문에 계수 정렬이 효과적

정렬 알고리즘 비교하기

정렬 알고리즘	평균 시간 복잡도	공간 복잡도	특징
선택 정렬	O(N^2)	O(N)	아이디어가 매우 간단
삽입 정렬	O(N^2)	O(N)	데이터가 거의 정렬되어 있을 때는 가장 빠르다
퀵 정렬	O(NlogN)	O(N)	대부분의 경우에 가장 적합하며, 충분히 빠르다
계수 정렬	O(N+K)	O(N+K)	데이터의 크기가 한정되어 있는 경우에만 사용이 가능하지만 매우 빠르게 동작한다.

🙇‍♀️
(이코테 2021 강의 몰아보기)4. 정렬 알고리즘