정렬

정렬

데이터를 특정한 기준에 따라서 순서대로 나열하는 알고리즘
이코테에서는 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬 이렇게 4가지의 정렬 알고리즘을 다루고 있다. 사실 처음에는 파이썬 sort() 함수를 쓰면 끝 아닌가? 라는 생각을 했었는데, 백준에서 정렬 알고리즘 문제에서 계속 막히는 부분이 생겨서 학교 알고리즘 수업에서 배운 몇 가지 정렬 알고리즘들의 아이디어는 가져가는 것이 좋겠다는 생각이 들었다.

기본적인 알고리즘으로는 버블 정렬, 선택 정렬, 삽입 정렬이 있고,
효율적인 알고리즘으로는 퀵 정렬, 합병 정렬, 계수 정렬, 쉘 정렬, 힙 정렬 등이 있다.

버블 정렬

이웃하는 숫자를 비교하여 작은 수를 앞쪽으로 이동시키는 과정을 반복한다.
기본적인 코드는 다음과 같다.

def Bubble_Sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-1-i):
            if arr[j] > arr[j + 1]: 
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

가장 기본적이면서 비효율적인 정렬 알고리즘으로, 아주 정직하게 for문을 두 번 돌리기 때문에, 시간복잡도는 O(n^2)이다.

선택 정렬

1. 배열 전체에서 최솟값을 선택
2. 0번째 원소와 자리를 바꾸고, 0번째 원소는 제외
3. 나머지 원소에서 최솟값을 선택
4. 배열의 1번 원소와 자리를 바꾸고, 1번째 원소는 제외

다음의 과정을 반복하여 마지막에 2개의 원소 중에 최솟값을 선택하여 자리를 바꾼다.

기본적인 코드는 다음과 같다.

def Selection_Sort(arr):
    n = len(arr)
    for i in range(n-1):
        min = i
        for j in range(i+1,n):
            if arr[j] < arr[min]:
                min = j
        arr[i], arr[min] = arr[min], arr[i]

버블 정렬과 마찬가지로 이중 for문을 돌리기 때문에, 시간복잡도는 O(n^2)이다.

삽입 정렬

1. 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누고,
2. 정렬되지 않은 부분의 가장 왼쪽 원소를 정렬된 부분의 적절한 위치에 삽입

이 과정을 반복한다.

기본적인 코드는 다음과 같다.

def Insertion_Sort(arr):
    n = len(arr)
    for i in range(1,n):
        for j in range(i,0,-1):
            if arr[j] > arr[j-1]:
                arr[j], arr[j-1] = arr[j-1], arr[j]
            else:
                break

1번째 원소 : 0번째 원소와 비교하여 자리를 바꾼다.
n번째 원소 : (n-1)번째 원소 ~ 0번째 원소까지 비교(중간에 n번째 원소가 더 크면 멈춤)

퀵 정렬

가장 많이 사용되는 정렬 알고리즘
피봇을 설정하고 그 피봇을 기준으로 작은 값과 큰 값을 나누어 리스트에 담은 뒤, 그 리스트에 대해서 다시 그 과정을 재귀적으로 반복하는 정렬 알고리즘이다.

기본적인 코드는 다음과 같다.

def Quick_Sort(arr):
    n = len(arr)
    if n <= 1:
        return arr  # 리스트의 길이가 1 이하면 바로 리턴

    pivot = arr[0]  # 피봇을 리스트의 첫 번째 요소로 선택
    left = []  # 피봇보다 작은 값을 담을 리스트
    right = []  # 피봇보다 큰 값을 담을 리스트

    for i in range(1,n):
        if arr[i] < pivot:
            left.append(arr[i])  # 피봇보다 작으면 left에 추가
        else:
            right.append(arr[i])  # 피봇보다 크거나 같으면 right에 추가

    # 왼쪽 부분, 오른쪽 부분을 다시 퀵 정렬하고 병합
    return Quick_Sort(left) + [pivot] + Quick_Sort(right)

합병 정렬

분할 정복 알고리의 하나로, 배열을 원소가 하나 밖에 남지 않을 때까지 쪼갠 뒤에, 다시 재배열하여 합병해나가는 정렬 알고리즘이다.

퀵 정렬과 함께 정렬 라이브러리의 근간이 되는 알고리즘이다. 퀵 정렬과 비교할 만큼 빠른 알고리즘이기도 하다.

기본적인 코드는 다음과 같다.

def Merge_Sort(arr):
    n = len(arr)
    if n < 2:
        return arr

    mid = n // 2
    low_arr = Merge_Sort(arr[:mid])
    high_arr = Merge_Sort(arr[mid:])

    merged_arr = []
    l = 0 
    h = 0
    while l < len(low_arr) and h < len(high_arr):
        if low_arr[l] < high_arr[h]:
            merged_arr.append(low_arr[l])
            l += 1
        else:
            merged_arr.append(high_arr[h])
            h += 1
    merged_arr += low_arr[l:] + high_arr[h:]
    return merged_arr

계수 정렬

특정한 조건이 부합할 때만 사용할 수 있지만, 매우 빠른 알고리즘이다. 비교 기반의 정렬 알고리즘이 아니라, 리스트의 인덱스를 이용하는 방식이기 때문이다.
하지만 상황에 따라 공간 복잡도 측면에서 심각한 비효율성을 초래할 수 있기 때문에 조심해야한다.

기본적인 코드는 다음과 같다.

def Radix_Sort(arr):
    n = len(arr)
    count = [0] * (max(arr)+1)
    for i in range(n):
        count[arr[i]] += 1
    for i in range(n):
        for j in range(count[i]):
            print(i, end=' ')

계수 정렬의 시간복잡도는 데이터의 개수와 데이터 중 최대값의 영향을 받는다.
데이터의 개수를 N, 데이터의 최댓값을 K라고 하면, 시간 복잡도는 O(N+K)이다. 데이터의 개수만큼 +1 해줘야하고, 데이터의 최댓값만큼 반복하여 출력하기 때문이다.