정렬

정렬 알고리즘

• 정렬 : 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 의미한다.

선택 정렬

• 무작위 데이터 중 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 과정 * 반복
• 시간복잡도 : O(N²)
• 데이터가 10,000개 이상일 경우 속도 느리기 때문에 기본 정렬 라이브러리 쓰는 것이 나음 - sorted(array)
  

def selection_sort(array):
    for i in range(len(array)):
        for j in range(i+1, len(array)):
            if array[j] < array[i]:
                array[i], array[j] = array[j], array[i]
    print(array)

삽입 정렬

• 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤, 그 위치에 삽입됨
• 거의 정렬되어 있는 상태에서 매우 빠르게 동작한다.
  

def insertion_sort(array):
    for i in range(1, len(array)):
        for k in range(i, 0, -1):
            if array[k] < array[k-1]:
                array[k], array[k-1] = array[k-1], array[k]
            else:
                break
    print(array)

퀵 정렬

• 퀵 정렬 : 기준(Pivot)을 설정한 다음 가장 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작함(재귀함수 사용)
• 시간복잡도 : O(NlogN) ~ O(N²)
• 데이터가 무작위로 입력되는 경우 빠르게 동작하지만, 이미 데이터가 정렬되어 있는 경우에는 느리게 동작한다.

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) # 오른쪽 부분
    return array

계수 정렬

• 계수 정렬 : 데이터의 크기 범위가 제한 되어 정수 형태로 표현할 수 있을 때, 인덱스에 해당하는 숫자의 개수를 세는 것이다.
• 시간복잡도 : O(N+k)
  

def count_sort(array):
    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=' ')
    print()

파이썬의 정렬 라이브러리

• sorted(array)
• array.sort()
• key를 이용한 정렬

    def setting(data):
        return data[1]
	array2 = [('바나나', 2), ('사과', 5), ('당근', 3)]
    result = sorted(array2, key=setting)
    print(result)

정렬 문제를 푸는 방법 세 가지

1. 정렬 라이브러리 사용 : 단순 라이브러리 사용법 숙지
2. 정렬 알고리즘 원리 물어보는 문제 : 선택 정렬, 삽입 정렬, 퀵 정렬
3. 더 빠른 정렬 필요할 때 : 계수 정렬 이용하기