[PART2]CH.06_정렬

1. 기준에 따라 데이터를 정렬

 정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는것을 말한다. 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색이 가능해진다. 즉 정렬 알고리즘은 이진 탐색의 전처리 과정이다.

 

- 선택정렬

 선택정렬은 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 정렬. 즉, 매번 '가장 작은 것을 선택' 한다.

#코드

arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
 
for i in range(len(arr)):
    min_idx = i # 가장 작은 원소의 인덱스
    for j in range(i+1,len(arr)):
        if arr[min_idx] > arr[j]:
            min_idx = j
    arr[i], arr[min_idx] = arr[min_idx], arr[i] #swap
 
print(arr)

시간복잡도 : O(n^2)

 

- 삽입정렬

 '데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입한다.' 

삽입 정렬은 선택 정렬에 비해  실행 시간 측면에서 더 효율적인 알고리즘이다. 특히 삽입 정렬은 필요할 때만 위치를 바꾸므로 '데이터가 거의 정렬 되어 있을 때' 훨씬 효율적이다. 

 

#코드

 
arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
 
for i in range(1, len(arr)):    
    for j in range(i, 0, -1):
        if arr[j] < arr[j-1]:
            arr[j], arr[j-1] = arr[j-1], arr[j]
print(arr)
 
 

시간복잡도 : O(n^2) -- 단 최선인 경우 : O(n)

 

- 퀵 정렬

 퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다. 퀵 정렬에서는 피벗(pivot)이 사용된다. 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준'을 바로 피벗이라고 표현한다. 퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 것인지 미리 명시해야 한다. 대표적인 방식인 '호어 분할' 방식을 기준으로 살펴보자.

#코드1

 
def quick_sort(arr, start, end):
    if start >= end:  # 원소가 1개인 경우 종료
        return
    pivot = start 
    left  = start + 1
    right = end
 
    while left <= right:
        # 피벗보다 큰 데이터를 찾을 때까지 반복
        # 1, 9 - 5 7
        # 2,
        while left <= end and arr[left] <= arr[pivot]:
            left += 1
        # 9, 1 - 8, 7
        # 8
        # 피벗보다 작은 데이터를 찾을 때까지 반복
        while right > start and arr[right] >= arr[pivot]:
            right -= 1
        
        if left > right: # 엇갈렸다면 작은 데이터와 피벗을 교체한다.
            arr[right], arr[pivot] = arr[pivot], arr[right]
        else: # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체한다.
            arr[left], arr[right] = arr[right], arr[left]
        
        # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
        quick_sort(arr, start, right-1)
        quick_sort(arr, right+1, end)
 
 
if __name__ == "__main__":
    arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
    quick_sort(arr, 0, len(arr)-1)
    print(arr)

#코드2

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
 
    pivot = arr[0]
    tail  = arr[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)
 
if __name__ == "__main__":
    arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
    print(quick_sort(arr))
    

시간복잡도 : O(nlogn), 최악 : O(n^2)

 

- 계수 정렬

 계수 정렬은 알고리즘은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다. 모든 데이터가 양의 정수인 상황을 가정해보자. 데이터의 개수가 N, 데이터 중 최댓값이 K일 때, 계수 정렬은 최악의 경우에도 수행 시간 O(N+K)를 보장한다. 다만, 계수 정렬은 '데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때'만 사용할 수 있다. 예를들어 데이터의 값이 무한한 범위를 가질 수 있는 실수형 데이터가 주어지는 경우 계수 정렬은 사용하기가 어렵다. 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘기지 않을 때 효과적으로 사용할 수 있다.

계수 정렬은 일반적으로 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다는 특징이 있다.

 

#코드

if __name__ == "__main__":
    
    arr = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
 
    # 모든 범위를 포함하는 리스트 선언 (모든 값은 0으로 초기화)
    count = [0]*(max(arr)+1)
 
    for i in range(len(arr)):
        count[arr[i]] += 1 # 각 데이터에 해당하는 인덱스의 값 증가.
 
    for i in range(len(count)):
        for j in  range(count[i]):
            print(i, end=' ')

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

 

 

실전문제

 

• 위에서 아래로

#코드

import sys
 
def quick_sort(data):
 
    if len(data) <= 1:
        return data
    pivot = data[0]
    tail  = data[1:]
 
    left_side  = [x for x in tail if pivot >= x]
    right_side = [x for x in tail if pivot < x]
 
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)
 
if __name__ == "__main__":
    input = sys.stdin.readline
    n = int(input())
    arr = list()
    for _ in range(n):
        arr.append(int(input())) 
    print(quick_sort(arr))

 

실전문제

 

• 성적이 낮은 순서로 학생 출력하기

#코드

import sys
 
if __name__ == "__main__":
    input = sys.stdin.readline
    n = int(input())
    arr = list()
    for _ in range(n):
        input_data = input().split()
        arr.append((input_data[0], int(input_data[1])))
 
    arr = sorted(arr, key=lambda student:student[1])
 
    for stu in arr:
        print(stu[0], end=' ') 

실전문제

 

• 두 배열의 원소 교체

#코드

import sys
 
if __name__ == "__main__":
    input = sys.stdin.readline
    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):
        a[i], b[i] = b[i], a[i]
    
    sum = 0
    for i in a:
        sum += i
    print(sum)