정렬

정의 및 장단점

정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열 하는 것을 말한다. 정렬 알고리즘은 이진 탐색의 전처리 과정이기도 하니 제대로 알고 있어야 한다. 정렬 알고리즘은 굉장히 다양한데 대표적인 몇가지만 설명하겠다.

여러정렬은 각각의 장단점이 존재한다. 각 상황에 맞는 정렬을 선택하여야한다.

일반적으로 라이브러리에서 제공하는 정렬은 퀵소트 또는 변형된 퀵소트이다. 평균 nlogn에서 n^2의 시간복잡도를 가진다.

기수정렬: O(N) 또는 O(N+K) N은 개수, K는 숫자범위크기 (ex. 0~99면 100)

계수정렬: O(N) 또는 O(N+K) N은 개수, K는 최대자리수

 

---

선택 정렬(selection)

 

 

선택정렬은 앞에서부터 차례대로 정렬하는 방법입니다. 먼저 주어진 리스트 중에 최소값을 찾고 그 값을 맨 앞에 위치한 값과 교체하는 방식으로 진행하는 정렬방법입니다. 코드가 직관적이기에 구현도 비교적 간단합니다. n개 원소에 대해 n개의 메모리를 사용하기에 데이터를 하나씩 정밀 비교가 가능하며 정렬을 위한 비교 횟수는 많으나 교환 횟수는 상당히 적다는 것이 장점인 정렬 방식입니다. 따라서 교환이 많이 이루어져야하는 자료 상태에서 가장 효율적으로 적용될 수 있는 정렬 방식입니다. 선택 정렬이 가장 적합한 자료 상태는 역순 정렬입니다. 즉, 내림차순으로 정렬되어 있는 자료를 오름차순으로 재정렬할 때 최적의 효율을 보여줍니다. 반대로 이미 정렬된 상태에서 소수의 자료가 추가됨으로 재정렬하게 되는 때에는 최악의 처리 속도를 보여준다는 단점도 있습니다.

 

선택 정렬 구현방법

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)

 

---

삽입 정렬(insertion)

 

버블정렬이 조금 비효율적인 면이 있기에 비교횟수를 효율적으로 줄이기 위해서 고안된 방법이 삽입정렬입니다. 삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 정렬 방법입니다. 버블정렬은 비교대상의 메모리 값이 정렬되어 있음에도 불구하고 비교연산을 하는 부분이 있는데 삽입정렬은 기본적으로 버블정렬의 비교횟수를 줄이고 크기가 적은 데이터 집합을 정렬하는 루팅을 작성할 시 버블정렬보다 탁월한 성능 효율을 보여줍니다. 정렬된 값은 한번도 교환이 일어나지 않고 N-1의 비교만 일어납니다.

 

 

삽입 정렬 구현방법

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)

 

연속적인 분할에 의한 정렬방식입니다. 처음 하나의 축(Pivot)을 먼저 정하여 이 축의 값보다 작은 값은 왼쪽에 큰 값은 오른쪽으로 위치시킨뒤 왼쪽과 오른쪽의 수 들은 다시 각각의 축으로 나누어져 축값이 1이 될 때까지 정렬합니다. 가장 많이 사용되는 정렬법이나 안정성이 떨어진다는 단점이 있습니다. 

 

 

퀵 정렬 구현방법

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)

 

 

파이썬이점을 살린 퀵정렬

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

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

---

계수 정렬(counting)

 

 

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

숫자의 범위가 작을 때 효율적이다.

예를 들어 숫자범위가 0-99이라면 100크기의 리스트를 만들고 0으로 초기화한다.

그후 피정렬리스트를 순차하면서 해당 리스크위치의 값를 올린다(counting). (N)

그리고 100크기의 리스트를 순차하면서 그 크기(count) 만큼 반복하여 자신의 인덱스를 다시 새로운 리스트에 저장한다.(K)

 

※ 계수 정렬의 시간 복잡도

모든 데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터 중 최댓값의 크기를 K라고 할 때, 계수 정렬의 시간 복잡도는 O(N + K)이다. 계수 정렬은 앞에서부터 데이터를 하나씩 확인하면서 리스트에서 적절한 인덱스의 값을 1씩 증가시킬 뿐만 아니라, 추후에 리스트의 각 인덱스에 해당하는 값들을 확인할 때 데이터 중 최댓값의 크기만큼 반복을 수행해야 하기 때문이다.

 

※ 계수 정렬의 공간 복잡도

계수 정렬은 데이터의 범위만 한정되어 있다면 항상 빠르게 동작하는 정렬 알고리즘이다.하지만 때에 따라서 심각한 비효율성을 초래할 수 있다. 예를 들어 데이터가 0과 999,999 단 2개만 존재한다고 가정하면 이럴 때에도 리스트의 크기가 100만이 되도록 선언해야 한다. 따라서 항상 사용할 수 있는 알고리즘은 아니며 동일한 값이 여러 번 등장할 때 적합하다. 계수 정렬의 공간 복잡도는 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=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

 

---

교환 정렬(bubble)

 

버블정렬은 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 끝부터 정렬하는 방식을 말합니다. 마찬가지로 코드가 간단하므로 구현이 간편합니다. 정렬을 하는 방식이 물속에서 물위로 올라오는 물방울 모양과 같다하여 버블정렬이라고 합니다. n개의 원소에 대하여 n개의 메모리를 사용합니다. 데이터를 하나씩 비교할 수 있어서 정밀하게 비교가 가능하나 비교횟수가 많아지므로 성능면에서는 좋은 방법이 아닙니다. 첫 번째 원소부터 마지막 원소까지 반복하여 한 단계가 끝나면 가장 큰 원소를 마지막 자리로 정렬하는 식으로 정렬이 됩니다. 

 

시간복잡도: 

 

교환 정렬 구현방법

def bubble_sort(arr):
    for i in range(len(arr)-1): # 반복 횟수
        for j in range(len(arr)-1): # 교환하는 원소 수
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

---

힙 정렬(heap)

 

힙 정렬은 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법입니다. 이진 완전 나무를 배열에다 접목시킨 절묘한 알고리즘입니다. 처음에는 나무 아래에서 위로 각 원소들을 최대값 힙 조건에 맞게 정리한 뒤, 나무 뿌리에 있는 자료를 차례차례 나무 뒤로 옮기면서 힙을 정렬된 배열로 바꿉니다. 뿌리에는 힙 나무 맨 뒤에 있던 원소가 왔다가, 다시 힙 조건에 맞는 위치로 내려갑니다. 시간복잡도가 O(nlogn)인 정렬 알고리즘 중에서는 부가적인 메모리가 전혀 필요없다는 게 큰 장점인 정렬 방식입니다.

 

 

 

힙 정렬 구현방법

# 힙 정렬
def heapify(unsorted, index, heap_size):
  largest = index
  left = 2 * index + 1
  right = 2 * index + 2
  
  if left < heap_size and unsorted[right] > unsorted[largest]:
    largest = left
    
  if right < heap_size and unsorted[right] > unsorted[largest]:
    largest = right
    
  if largest != index:
    unsorted[largest], unsorted[index] = unsorted[index], unsorted[largest]
    heapify(unsorted, largest, heap_size)

def heap_sort(unsorted):
  n = len(unsorted)
  
  for i in range(n // 2 - 1, -1, -1):
    heapify(unsorted, i, n)
    
  for i in range(n - 1, 0, -1):
    unsorted[0], unsorted[i] = unsorted[i], unsorted[0]
    heapify(unsorted, 0, i)

  return unsorted

---

기수정렬(radix)

 

기수 정렬(Radix Sort)

기수 정렬은 낮은 자리수부터 비교하여 정렬해 가는 정렬 알고리즘이다.

원소들의 값이 음수가 아닌 정수이고 자릿수가 모두 같을 때(같게 만들어서) 사용 가능하다.

데이터의 비교를 통한 정렬이 아닌 분산 정렬을 이용한 정렬 방법이며 자릿수가 있는 데이터(정수, 문자열 등)에만 사용 가능합니다. 각 자리수를 기준으로 점차 정렬을 진행합니다.

 

시간복잡도: O(N)

 

※ 기수 정렬의 시간 복잡도

기수 정렬은 데이터의 개수가 N이고 데이터의 최대 자릿수를 K라고 했을 때 N * K번의 연산을 하게 되고 O(N)의 시간 복잡도를 갖는다. 보통 기수 정렬은 계수 정렬에 비해 동작이 느리지만 처리할 수 있는 정수의 크기는 더 크다. 또한 기수 정렬의 탐색 과정을 보면 알 수 있듯이 최악, 최선의 경우가 존재하지 않아 항상 빠르고 안정된 성능을 보여준다. 

 

※ 기수 정렬의 공간 복잡도

기수 정렬이 빠르고 안정된 수행 속도를 가지고 있기에 가장 좋은 정렬 알고리즘이라고 생각할 수 있지만 그렇지는 않다.

왜냐하면, 버킷이라는 작지 않은 용량의 추가적인 메모리 공간을 필요로 하기 때문이다

 

기수정렬 구현방법

from collections import deque

def radixSort():
    nums = list(map(int, input().split(' ')))
    buckets = [deque() for _ in range(10)]
    
    max_val = max(nums)
    queue = deque(nums)
    digit = 1 # 자릿수
    
    while (max_val >= digit): # 가장 큰 수의 자릿수일 때 까지만 실행
        while queue:
            num = queue.popleft()
            buckets[(num // digit) % 10].append(num) # 각 자리의 수(0~9)에 따라 버킷에 num을 넣는다.
        
        # 해당 자릿수에서 버킷에 다 넣었으면, 버킷에 담겨있는 순서대로 꺼내와 정렬한다.
        for bucket in buckets:
            while bucket:
                queue.append(bucket.popleft())
        print(digit,"의 자릿 수 정렬: ", list(queue))
        digit *= 10 # 자릿수 증가시키기
    
    print(list(queue))

 

---

합병 정렬(merge)

작은 단위로 잘게 쪼개어 작은 단위부터 정렬해서 정렬된 단위들을 계속 병합해가면서 정렬하는 방식입니다. 알고리즘 중에 가장 간단하고 쉽게 떠올릴 수 있는 방법이며 안정성이 있여 상당히 좋은 성능을 나타냅니다. 하나 큰 결점이 있다면 공간이 많이 필요하다는 점입니다. 정렬을 하기 위해서는 데이터 전체 크기만한 메모리가 더 필요합니다

 

시간복잡도: 

 

 

합병정렬 구현방법

def merge_sort(arr):
    #둘로 쪼개고 하나로 합쳐라
    def sort(low, high):
        if high - low < 2:
            return
        mid = (low + high) // 2
        sort(low, mid)
        sort(mid, high)
        merge(low, mid, high)

    def merge(low, mid, high):
        temp = []
        l, h = low, mid

        # low/high가 둘다 남아있을 때
        while l < mid and h < high:
            if arr[l] < arr[h]:
                temp.append(arr[l])
                l += 1
            else:
                temp.append(arr[h])
                h += 1
        # low 또는 high만 남아있을 때
        while l < mid:
            temp.append(arr[l])
            l += 1
        while h < high:
            temp.append(arr[h])
            h += 1

        for i in range(low, high):
            arr[i] = temp[i - low]

    return sort(0, len(arr))

---

정렬문제예시

다음 입력들을 정렬하시오.

# N 입력 받기
n = int(input())

# N개의 정수를 입력 받아 리스트에 저장
array = []
for i in range(n):
    array.append(int(input()))

# 파이썬 정렬 라이브러리를 이용하여 내림차순 정렬 수행
array = sorted(array, reverse=True)

# 정렬이 수행된 결과를 출력
for i in array:
    print(i, end=' ')

실제 코딩테스트에서는 라이브러리의 함수를 쓰면 된다. 하지만 그 함수의 사용법을 미리 알고 있어야 빠르고 효율적으로 사용할 수 있다.

 

 

아래는 sort함수의 사용법이다.

리스트.sort()로 사용한다.

숫자는 음수,0,양수 순으로 정렬을 해주고

문자는 대문자가 앞으로 소문자가 뒤로간다.

 

sorted()

sorted( <list> , key = <function> , reverse = <bool>)
# <list> 뿐 아니라, <Tuple>, <Dictionary>, <Str>에도 사용 가능하다.

• 원본 내용을 바꾸지 않고, 정렬한 값을 반환한다.
• List, tuple, Dictionary, str에 모두 사용 가능하다.
• key 를 통하여 정렬할 기준을 정할 수 있다.
• reverse 가 True이면 내림차순, False이면 오름차순으로 정렬된다.

 

arr = [10, 40, 20, 15]
arr = sorted(arr, reverse = True)
print(arr)

>>>> [40, 20, 15, 10]

---

sort()

<list>.sort(key = <function>, reverse = <bool>)

• 원본 자체를 수정한다.
• 반환값은 None
• Tuple , Dictionary, Str 에는 사용이 불가하다.

reverse 옵션을 이용하여 오름차순과 내림차순을 설정할 수 있다.

기본적으로 오름차순이며 reverse=True로 설정하면 내림차순이 된다.

arr = [10, 40, 20, 15]
arr = sorted(arr, reverse = True)
print(arr)

>>>> [40, 20, 15, 10]

 

 

key값을 사용하면 여러가지 기준으로 정렬을 실행할 수 있다.

 

2중 리스트에서 정렬하기

array = [[50, "apple"], [30, "banana"] , [400, "melon"]]

위와 같이 [Int, Str]형식의 요소를 가진 리스트가 존재할때

 

Int 를 기준으로 정렬하기

.sort() 함수 사용

array.sort(key = lambda x:x[0])
print(array)
>>>>> [[30, 'banana'], [50, 'apple'], [400, 'melon']]

sorted() 함수 사용

print(sorted(array, key = lambda x: x[0]))
>>>>> [[30, 'banana'], [50, 'apple'], [400, 'melon']]

 

 

Str을 기준으로 정렬하기

Sort() 함수 사용

array.sort(key = lambda x:x[1])
print(array)
>>>>>[[50, 'apple'], [30, 'banana'], [400, 'melon']]

sorted() 함수 사용

print(sorted(array, key = lambda x: x[1]))
>>>>>[[50, 'apple'], [30, 'banana'], [400, 'melon']]

 

 

 

#  key가 여러개 일때 (다중조건 정렬)

 

array = [("A", 18, 300000) , ("F", 24, 10000), ("T", 24, 200000),("Q",24,5000000), ("B", 70, 5000)]
# (<이름> , <나이> , <재산>) 이라고 하면

• 위의 리스트처럼 정렬해야 할때 고려해야 많은 경우가 있을때는 튜플형식으로 key = lambda x: (x[0] , x[2]) lambda식을 세워주면 된다.
• 그리고 내림차순으로 하고 싶다면 마이너스 부호를 붙여주면 된다. key= lambda x: (-x[0], x[2])

 

 

나이를 기준으로 오름차순 정렬하고 , 같은 나이라면 재산을 내림차순으로 정렬

array.sort(key = lambda (x: x[1], -x[2]))
print(array)

>>> [('A', 18, 300000), ('Q', 24, 5000000), ('T', 24, 200000), ('F', 24, 10000), ('B', 70, 5000)]

 

 

 

 

자료출처 및 참고: https://coding-factory.tistory.com/615