이것이 코딩테스트다 - 11일차

주제

sort

정렬

무작위적인 데이터를 순차적으로 나열하는 것이다.

예시

오름차순 정렬

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

내림차순 정렬

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

퀵정렬

피벗을 사용하여 왼쪽과 오른쪽을 기준점으로 나누어 분할 정복을 하듯이 정렬하는 방식

• 분할 정복 (divide and conquer): 큰 단위를 작은 단위들로 나누어 큰 단위의 문제를 해결하는 방식

array = [5, 7, 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[left]
        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))

계수 정렬

중복된 데이터가 많고, 다량의 데이터일 경우 효율적

단점: [0, 9999] 두 개의 데이터가 있을 경우에도 10000까지의 배열을 잡아야한다.

배열의 크기 만큼 0으로 초기화를 시킨 뒤, 데이터위치에 카운팅을 한다.

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

파이썬 정렬라이브러리

1. sorted()
2. sort()

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

result = sorted(array)
result = array.sort()
print(result)

튜플 데이터 정렬

key값을 기준으로 정렬

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

def setting(data):
    return data[1]

result = sorted(array, key=setting)
print(result)