알고리즘 - 정렬 알고리즘(sorting algorithm)

 

<정렬 알고리즘의 정의>

 

선택 정렬(Selection sorting)

처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 정렬법이다.

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

for i in range(len(array)): #i는 매번 앞쪽으로 보내는 맨 앞의 자리라고 생각하면 
    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)

 

 

삽입 정렬(Insertion sorting)

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다.

선택 정렬에 비해 구현 난이도가 높지만 일반적으로 더 효율적으로 동작한다.

 

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): #인덱스 i부터 1까지 1씩 감소하며 반복하는 문법
        if array[j] < array[j-1]:
            array[j],array[j-1] = array[j-1],array[j] #스왑
        else:
            break

print(array)

#왼쪽 값과 비교를 했을 때 자신이 더 작다면 그때 스왑을 해준다.

 

 

퀵 정렬(Quick sorting)

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

일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나이다.

병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘이다.

가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정한다.

 

퀵 정렬은 재귀적으로 수행이 되고 수행이 될 때마다 수행 범위가 점점 좁아지는 양상을 볼 수 있다.

 

<퀵 정렬이 빠른 이유: 직관적인 이해>

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

- 너비 X 높이 = N X logN = NlogN

- 퀵 정렬은 평균의 경우 O(NlogN)의 시간 복잡도를 가진다.

- 하지만 최악의 경우 O(N**)의 시간 복잡도를 가진다. 

🤷‍♀️ 첫 번째 원소를 피벗으로 삼을 때, 이미 정렬된 배열에 대해서 퀵 정렬을 수행할 때 최악의 경우이다.

 

<퀵 정렬 소스코드: 일반적인 방식 / 이상적인 경우 >

#퀵 정렬 소스코드: 일반적인 방식

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

# start = 0(index)

# end = len(array) -1 / index가 0부터 시작하기 때문 길이에선 -1을 해주어야 한다.

 

<퀵 정렬 소스코드: 파이썬의 장점을 살린 방식>

#퀵 정렬 소스코드: 파이썬의 장점을 살린 방

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

def quick_sort(array):
    #리스트가 하나 이하의 원소만을 담고 있다면 종료
    if len(array) <= 1:
        return array
    pivot = array[0] #피벗은 첫 번째 원소 index가 0에 해당하는 값이 기준점(피벗)이 된다.
    tail = array[1:] #피벗을 제외한 리스트

    left_side = [x for x in tail if x <= pivot] #1 분할된 왼쪽 부분 
    right_side = [x for x in tail if x > pivot] #2 분할된 오른쪽 부분

    #분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행하고, 전체 리스트 반환
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)#3

print(quick_sort(array))

#1 피벗을 제외한 리스트에 원소를 하나씩 확인하면서 피벗값보다 작은 경우에는 왼쪽 리스트에 담길 수 있도록 한다.

 

#2 피벗을 제외한 리스트에 원소를 하나씩 확인하면서 피벗값보다 큰 경우에는 오른쪽 리스트에 담길 수 있도록 한다.

 

#3 리턴값으로 왼쪽 리스트에 정렬한 값과 기준점이 된 pivot값 그리고 pivot값보다 큰 값들의 모임인 오른쪽 리스트를 돌려준다.

 

 

계수 정렬 (Counting sort)

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘이다.

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

데이터 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 수행 시간 O(N + K)를 보장한다. 

결과를 확인할 때는 리스트의 첫 번째 데이터부터 하나씩 그 값만큼 반복하여 인덱스를 출력한다.

공간 복잡도는 높지만 퀵정렬보다 빠르게 동작한다.

# 모든 원소의 값이 0보다 크거나 같다고 가정
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=' ') #띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

 

 

<정렬 알고리즘 비교하기>

 

 

<선택 정렬과 파이썬에서 제공하는 기본라이브러리(=정렬) 수행 시간 비교>