정렬

Lee Sang Hyuk·2022년 1월 10일

Algorithm

목록 보기

4/6

정렬(Sorting)

데이터를 특정한 기준에 따라 순서대로 나열하는 것입니다. 알고리즘 중에서 가장 많이 사용하는 방법으로 눈 감고도 풀 수 있을 정도로 연습할 필요가 있습니다. 또한, '이진 탐색'에 대해서 배우려면 정렬 알고리즘 개념에 대해 필요하기 때문에 이 내용에 대해서 넘어가면 곤란합니다.

정렬 알고리즘은 다양하지만, 책에서는 '선택 정렬', '삽입 정렬', '퀵 정렬', '계수 정렬'에 대해서 언급했기에 이 개념을 우선적으로 작성합니다.

효율성

정렬 알고리즘은 '효율성' 부분에 대해서도 고려해야 할 필요가 있습니다. 효율성을 확인할 수 있는 방법은 작성한 코드에 대한 시간 복잡도)이며, 시간 복잡도를 표현하기 위해서 빅오 표기법( $O(N)$ )으로 간단히 표현할 수 있다. 다음 아래의 자료는 시간 복잡도에 따른 그래프입니다.

선택 정렬(Selection Sort)

(오름차순 기준) 여러 개의 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 두 번째 데이터와 바꾸는 과정을 반복하면 된다.

시간 복잡도 : Best, Worst case → $O(N^2)$

# Selection Sort

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]  # swap in pyhton

print(array)

sanghyuk-2i/Algorithm

파이썬에서의 스와프(Swap)

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

print(array)    # [2, 1]

삽입 정렬(Insertion Sort)

특정한 데이터를 적절한 위치에 '삽입'한다는 의미로 두 번째 데이터로부터 시작하여 데이터를 정렬합니다.

시간 복잡도 : Best, Worst case → $O(N)$ , $O(N^2)$

(여기서, Case를 판별하는 기준은 기존 데이터가 거의 정렬되어 있으면 Best, 아니면 Worst에 따라 갈라진다.)

# Insertion Sort

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):
        if(array[j] < array[j - 1]):
            array[j], array[j - 1] = array[j - 1], array[j]
        else:
            break

print(array)

sanghyuk-2i/Algorithm

퀵 정렬(Quick Sort)

정렬 알고리즘 중에서 '가장 많이 사용' + '빠른' 알고리즘에 속한다. 기준 데이터(수)를 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작합니다.

시간 복잡도 : Average, Worst case → $O(NlogN)$ , $O(N^2)$

# Quick Sort

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

def quick_sort(array, start, end):
    if(start >= end):
        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)

# Quick Sort 2

def quick_sort_two(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_two(left_side) + [pivot] + quick_sort_two(right_side)

print(quick_sort_two(array))

sanghyuk-2i/Algorithm

계수 정렬(Count Sort)

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘입니다. 여기서 말한 특정한 조건이라는 것은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있는 조건입니다. 예를 들어 데이터의 값이 무한한 범위를 가진 실수형 데이터로 이루어져 있으면 계수 정렬을 이용하기 힘듭니다. 보통 정수형 데이터 중에서 0 ~ 100 사이로 이루어져 있으며 데이터 값들의 차이가 너무 크지 않으면 효과적인 정렬 알고리즘입니다.

시간 복잡도 : $O(N + K)$

# Count Sort

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

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

sanghyuk-2i/Algorithm

파이썬 정렬 라이브러리

파이썬에서는 기본적으로 정렬 라이브러리에서 sorted() 함수를 제공합니다. 이 함수는 퀵 정렬의 동작 방식이 비슷한 병합 정렬을 기반으로 제작하였습니다. 여기서 병합 정렬의 특징은 일반적으로 퀵 정렬보다 느리지만 Worst Case에서는 시간 복잡도( $O(NlogN)$ )을 보장합니다.

시간 복잡도 : Worst case → $O(NlogN)$

# Python Sorting Library

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

result = sorted(array)
print(result)

array.sort()
print(array)

array_t = [('바나나', 2), ('사과', 5), ('당근', 3)]

def setting(data):
    return data[1]

result_two = sorted(array_t, key=setting)
print(result)

sanghyuk-2i/Algorithm

문제 및 풀이

문제 1. 위에서 아래로

n = int(input())

array = []
for i in range(n):
    array.append(int(input()))

array = sorted(array, reverse=True)

for i in array:
    print(i, end=' ')

const solution = (arr) => {
    arr.sort((a, b) => b - a);
    return arr;
}

let arr = [15, 27, 12];
console.log(solution(arr));

sanghyuk-2i/Algorithm

Algorithm/sort_6.js at main · sanghyuk-2i/Algorithm

문제 2. 성적이 낮은 순서로 학생 출력하기

n = int(input())

array = []
for i in range(n):
    check = input().split()
    array.append((check[0], int(check[1])))

array = sorted(array, key=lambda student: student[1])

for s in array:
    print(s[0], end=' ')

const solution = (arr) => {
    arr.sort((a, b) => a[1] - b[1]);
    return arr.map((a) => a[0]);
}

let arr = [['홍길동', 95], ['이순신', 77]];
console.log(solution(arr));

sanghyuk-2i/Algorithm

Algorithm/sort_7.js at main · sanghyuk-2i/Algorithm

문제 3. 두 배열의 원소 교체

n, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

a.sort()
b.sort(reverse=True)

for i in range(k):
    if(a[i] < b[i]):
        a[i], b[i] = b[i], a[i]
    else:
        break

print(sum(a))

const solution = (n, arr, arr2) => {
    arr.sort((a, b) => a - b);
    arr2.sort((a, b) => b - a);

    for (let i = 0; i < n; i++) {
        if (arr[i] < arr2[i]) {
            let check = arr[i];
            arr.splice(i, 1, arr2[i]);
            arr2.splice(i, 1, check);
        }
    }
    return arr.reduce((a, v) => a + v);
}

let arr = [1, 2, 5, 4, 3];
let arr2 = [5, 5, 6, 6, 5];
console.log(solution(3, arr, arr2));