정렬

정렬(Sorting) 이란?

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

오름차순, 내림차순 정렬 등 기준을 정해서 정렬한다.

정렬은 이진 탐색의 전처리 과정이기도 하다.

 

Python Swap

array[0], array[1] = array[1], array[0]

 

선택정렬

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

def select_sort(arr):
    array = arr
    for i in range(len(array)):
        min_idx = i
        for j in range(i+1,len(array)):
            if array[min_idx] > array[j]:
                min_idx=j
        array[i],array[min_idx]=array[min_idx],array[i]
    return array

시간 복잡도

N-1번 만큼 가장 작은 수를 찾아 맨 앞으로 보내야 한다.

매번 가장 작은 수를 찾기 위한 연산도 필요하다.

즉 연산의 수는 N+(N-1)+(N-2)+....+2 = (N^2+N)/2 

O(N^2)이 된다. 데이터의 개수가 100배 늘어나면 수행시간은 10000배 늘어나는 셈이다.

 

삽입 정렬

데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하는 정렬.

필요할 때만 위치를 바꾸므로 데이터가 거의 정렬 되어 있을 때 효율적인 알고리즘이다.

def insert_sort(arr):
    array = arr
    for i in range(1,len(array)):
        for j in range(i,0,-1):# i부터 1까지 감소하며 반복하는 문법.
            if array[j]<array[j-1]: #한칸씩 왼쪽으로 이동
                array[j],array[j-1] = array[j-1],array[j] #swap
            else:
                break
    return array

시간 복잡도

O(N^2) 선택정렬과 마찬가지로 2중 for문을 사용하였기 때문이다. 최선의 경우에는 O(N)의 시간 복잡도를 가진다.

 

퀵 정렬

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

pivot을 사용한다. pivot이란 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 기준.

퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 것인지 미리 명시해야 한다.

호어 분할 방식에서는 리스트의 첫 번째 데이터를 피벗으로 정한다.

 

def quick_sort(arr, start,end):
    array = arr
    if start >= end:
        return
    pivot = start
    left = start+1
    right = end
    while left<=right:
        #pivot 보다 큰 데이터를 찾을 때 까지 반복
        while left <= end and array[left]<=array[pivot]:
            left+=1
        #pivot 보다 작은 데이터를 찾을 때 까지 반복
        while right > start and array[right]>= array[pivot]:
            right-=1
        #엇갈렸다면 작은 right -= 1 데이터와 pivot을 교체
        if left>right:
            array[right],array[pivot] = array[pivot],array[right]
        #엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
        else:
            array[right], array[left] = array[left],array[right]
    #분할 이후 왼쪽과 오른 쪽 각 부분에서 각각 정렬 수행
    quick_sort(arr, start,right-1)
    quick_sort(arr, right+1, end)

#python의 장점을 살린 quick sort
def quick_sort2(arr):
    if len(arr)<=1:
        return arr
    pivot = arr[0]
    tail = arr[1:]

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

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

 

시간복잡도

퀵정렬의 평균 시간 복잡도는 O(nlogn)이다. 앞서 다루었던 두 정렬 알고리즘에 비해 매우 빠르다.

퀵 정렬에서의 최선의 경우는 pivot값의 위치가 변경되어 분할이 일어날 때마다 정확히 왼쪽 리스트와 오른쪽 리스트를 절반씩 분할 한다면 데이터가 N개일때 높이는 약 log N이며 분할이 이루어지는 횟수가 기하급수적으로 감소하게 된다.

평균적으로는 O(nlogn)이지만 최악의 경우 O(N^2)가 될 수도 있다.

이미 데이터가 정렬된 경우 매우 느리게 동작한다. 무작위로 입력 받을시에는 빠르게 동작하지만.

 

계수정렬

특정한 조건이 부합할 때만 사용할 수 있다. 조건이 맞으면 매우 빠른 알고리즘.

모든 데이터가 양의 정수인 상황을 가정하면 데이터가 N개 데이터중 최댓값이 K일 때,

계수 정렬은 최악의 경우에도 수행시간 O(N+K)를 보장한다.

계수 정렬은 빠를뿐만 아니라 단순하다 다만 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용가능

리스트를 두개 두고 값들을 들고 있는 리스트 하나와 값들의 개수를 세는 리스트로 나누어 사용한다.

def count_sort(arr):
    count = [0]*(max(arr)+1)

    for i in range(len(arr)):
        count[arr[i]]+=1
    array= list()
    for i in range(len(count)):
        for j in range(count[i]):
            array.append(i)
    return array

 

시간복잡도

모든 데이터가 양의 정수인 상황에서는 데이터의 개수를 N, 데이터 중 최대값의 크기가 K라 할때 시간복잡도는 O(N+K).

데이터를 하나씩 확인하면서 리스트에서 적절한 인덱스의 값을 1씩 증가시킬 뿐 아니라 리스트의 각 인덱스에 해당하는 값들을 확인할 때 데이터중 최댓값의 크기만큼 반복을 수행해야 하기 때문.

공간복잡도

때에 따라 심각한 비효율성을 초래할 수도 있다. 0과 999999 두개의 데이터가 존재할 때 두개의 데이터를 정렬하기 위해

크기가 100만개인 리스트를 만들어서 사용해야 할 수 도 있기 때문.

 

Python 정렬 라이브러리