[Python] ECC 2주차 정리 - 정렬

#  1. 버블 정렬

• 두 인접한 데이터의 크기를 비교해 정렬하는 방법
• O(n^2)의 시간 복잡도로 다른 정렬 알고리즘보다 느린 편이다. 

https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

N = int(input())
A = [0]*N
for i in range(N):
    A[i] = int(input())

for i in range(N-1):
    for j in range(N-1-i):
        if A[j] > A[j+1]:
            A[j], A[j+1] = A[j+1], A[j]

for i in range(N):
    print(A[i])

• 해당 코드는 오른쪽부터 큰 수를 정렬하게 된다.
• python에 내장된 O(nlogn)의 sort() 알고리즘이 있긴 하다.

 

https://www.acmicpc.net/problem/1377

1377번: 버블 소트

import sys
input = sys.stdin.readline

N = int(input())
A=[] # 데이터 리스트, 클래스를 데이터로 담는다.

for i in range(N):
    A.append((int(input()), i)) # 데이터, index 저장

Max = 0
sorted_A = sorted(A)

for i in range(N):
    if Max < sorted_A[i][1]-i: # 정렬 전 index - 정렬 후 index 계산 후 최댓값 저장
        Max = sorted_A[i][1] - i 

print(Max+1) # swap이 일어나지 않는 반복문이 한 번 더 실행되므로 최댓값 + 1

• 버블 정렬의 swap이 한 번도 일어나지 않은 루프가 언제인지 알아내는 문제
• 즉, 안쪽 for문에서 swap이 일어나지 않은 거은 이미 모든 데이터가 정렬됐다는 것을 의미한다. 이때 바로 종료하면 시간복잡도가 줄어든다.
• 시간 초과로 인해 안쪽 for문이 몇 번 수행됐는지 다른 방식으로 구한다. 즉 데이터의 정렬 전과 후의 index를 비교하여 왼쪽으로 가장 많이 이동한 값을 찾으면 된다.

---

# 2. 선택 정렬

• 대상 데이터에서 최대/최소 데이터를 찾아가며 선택하는 방법. 선택된 데이터는 남은 정렬 부분의 가장 앞에 있는 데이터와 swap한다.
• 구현 방법이 복잡하고 시간 복잡도가 O(n^2)으로 많이 사용하지 않는다.

https://www.acmicpc.net/problem/1427

1427번: 소트인사이드

import sys
input = sys.stdin.readline

A = list(input()) # 입력받은 수를 각 자릿수별로 나누기 위해 list로 변환

for i in range(len(A)):
    Max = i
    for j in range(i+1, len(A)):
        if A[j] > A[Max]: # 내림차순이므로 최댓값 찾기
            Max = j
        if A[i] < A[Max]:
            A[i], A[Max] = A[Max], A[i]

for i in range(len(A)):
    print(A[i], end='')

 

---

# 3. 삽입 정렬

• 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식
• 시간복잡도는 O(n^2)으로 느리지만 구현이 쉽다.
• 적절한 삽입 위치를 탐색하는 부분에서 이진 탐색 등과 같은 알고리즘을 사용하여 시간 복잡도를 줄인다.

https://www.acmicpc.net/problem/11399

11399번: ATM

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split())) # 자릿수별로 구분해 저장한 리스트
S = [0]*N # A 합 배열, 각 사람이 인출을 완료하는 데 필요한 시간 저장

for i in range(1, N): # 삽입 정렬
    insert_point = i
    insert_value = A[i]
    for j in range(i-1, -1, -1):
        if A[j]<A[i]: # 현재 범위에서 삽입 위치 찾기
            insert_point = j+1 
            break
        if j==0:
            insert_point=0
    
    for j in range(i, insert_point, -1): # 삽입을 위해 삽입 위치에서 i까지 한 칸씩 뒤로 밀기
        A[j] = A[j-1]
    A[insert_point] = insert_value

S[0] = A[0]

for i in range(1, N): # 합 배열 만들기
    S[i] = S[i-1]+A[i]

sum = 0

for i in range(0, N): # 합 배열 총합 구하기
    sum += S[i]

print(sum)

• ATM에서 모든 사람이 가장 빠른 시간에 인출하는 방법은 그리디 알고리즘으로 해결할 수 있다.
• 여기서 그리디 방식은 인출시간이 가장 적은 사람이 먼저 오도록, 즉 오름차순으로 정렬하는 것이다.
• 정렬 후 합 배열을 구한 후 전부 더해 시간을 구할 수 있다.

---

# 4. 퀵 정렬

• 기준 값(pivot)을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류한다.
• 평균 시간 복잡도는 O(nlogn)이며 최악의 경우 O(n^2)이 된다.
• pivot을 중심으로 데이터를 2개의 집합으로 계속 나누면서 정렬한다. pivot보다 작은 왼쪽 정렬, pivot보다 큰 오른쪽 정렬 등으로 집합을 나눈다.
• 시간 복잡도가 준수한 편으로 가끔 사용되며, 재귀 함수의 형태로 구현할 수 있다.

https://www.acmicpc.net/problem/11004

11004번: K번째 수

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
A = list(map(int, input().split()))

def quickSort(S, E, K): # 시작, 종료, K
    global A
    if S < E:
        pivot = partitions(S, E)
        if pivot == K: # K번째 수가 pivot이면 더 구할 필요 X
            return
        elif K<pivot: # K가 pivot보다 작으면 왼쪽 그룹만 정렬
            quickSort(S, pivot-1, K)
        else:
            quickSort(pivot+1, E, K)

def partitions(S, E): # pivot 구하기.
    global A

    if S+1 == E:
        if A[S]>A[E]:
            A[S], A[E] = A[E], A[S]
        return E
    
    M = (S+E) // 2 # 중앙 값
    A[S], A[M] = A[M], A[S] # 중앙 값을 시작 위치와 swap
    pivot = A[S] # pivot을 시작 위치 값 A[S] 로 저장
    i = S+1
    j = E
    while i<=j:
        while pivot<A[j] and j >0:
            j = j-1 # pivot보다 작은 수가 나올 때까지 j 감소
            while pivot >A[i] and i <len(A)-1:
                i = i+1 # pivot보다 큰 수가 나올 때까지 i 증가
            if i<=j:
                A[i], A[j] = A[j], A[i] # i와 j 데이터 swap
                i=i+1 
                j=j-1 
    # i==j 피벗의 값을 약쪽으로 분리한 가운데에 오도록 설정하기
    A[S] = A[j]
    A[j] = pivot
    return j # 경계 index 리턴

quickSort(0, N-1, K-1)
print(A[K-1])

• 시간 초과 나온다...하지만 퀵 정렬 연습을 위해 작성함,
• 배열의 중간 위치를 pivot으로 설정했다. 그 후 이동을 편하게 하기 위해 pivot을 맨 앞과 swap. 
• i는 pivot을 제외한 배열의 맨 왼쪽, j는 배열의 맨 오른쪽. j가 pivot보다 크면 j--, i가 pivot보다 작으면서 i보다 j가 크면 i++연산을 반복한다.
• i와 j가 만난 위치와 pivot을 swap하면 pivot을 기준으로 두 배열이 나눠지게 된다!

---

# 5.  병합 정렬

• 분할-정복 방식을 사용하여 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘이다.
• 시간 복잡도는 O(nlogn)이며, 코딩 테스트에서 자주 등장한다.
• 두 그룹을 병합하는 방식은 투 포인터를 이용하여 추가 배열에 저장한다.

https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

import sys
input = sys.stdin.readline
print = sys.stdout.write

def merge_sort(s, e): # 병합 정렬 수행, 시작점 s, 동료점 e
    if e - s < 1: return
    m = int(s+(e-s)/2)
    merge_sort(s, m) # 재귀함수
    merge_sort(m+1, e)
    for i in range(s, e+1):
        tmp[i] = A[i]

    K=s 
    index1 = s # 앞쪽 그룹 시작점
    index2 = m+1 # 뒤쪽 그룹 시작점
    while index1 <=m and index2 <= e: # 두 그룹을 병합하는 로직
        if tmp[index1] > tmp[index2]: # 양쪽 그룹의 index가 가리키는 값을 비교 후 더 작은 수를 리스트에 저장
            A[K] = tmp[index2]
            K += 1
            index2 += 1
        else:
            A[K] = tmp[index1]
            K += 1
            index1 += 1
    while index1 <= m: # 한쪽 그룹이 모두 선택된 후 남아 있는 값 정리
        A[K] = tmp[index1]
        K += 1
        index1 += 1
    while index2 <= e:
        A[K] = tmp[index2]
        K += 1
        index2 += 1

N= int(input())
A = [0]*int(N+1) # 정렬할 리스트
tmp = [0]*int(N+1) # 정렬할 때 사용하는 임시 리스트

for i in range(1, N+1):
    A[i] = int(input())

merge_sort(1, N)

for i in range(1,N+1):
    print(str(A[i])+'\n')

• 정렬할 그룹을 최소 길이로 나눈 후 나눈 그룹마다 병합 정렬을 수행한다.
• 정렬 용도로 선언한 tmp 배열에 병합 정렬 한다.

https://www.acmicpc.net/problem/1517

1517번: 버블 소트

import sys
input = sys.stdin.readline
result = 0

def merge_sort(s, e): # 병합 정렬 수행, 시작점 s, 동료점 e
    global result
    if e - s < 1: return
    m = int(s+(e-s)/2)
    merge_sort(s, m) # 재귀함수
    merge_sort(m+1, e)
    for i in range(s, e+1):
        tmp[i] = A[i]

    K=s 
    index1 = s # 앞쪽 그룹 시작점
    index2 = m+1 # 뒤쪽 그룹 시작점
    while index1 <=m and index2 <= e: # 두 그룹을 병합하는 로직
        if tmp[index1] > tmp[index2]: # 양쪽 그룹의 index가 가리키는 값을 비교 후 더 작은 수를 리스트에 저장
            A[K] = tmp[index2]
            result = result + index2 - K # 뒤쪽 데이터 값이 더 작다면 결괏값 업데이트
            K += 1
            index2 += 1
        else:
            A[K] = tmp[index1]
            K += 1
            index1 += 1
    while index1 <= m: # 한쪽 그룹이 모두 선택된 후 남아 있는 값 정리
        A[K] = tmp[index1]
        K += 1
        index1 += 1
    while index2 <= e:
        A[K] = tmp[index2]
        K += 1
        index2 += 1

N= int(input())
A = list(map(int, input().split()))
A.insert(0,0)
tmp = [0]*int(N+1)
merge_sort(1,N)
print(result)

• 버블 정렬이지만...N의 최대가 500,000이므로 O(nlogn)인 병합 정렬로 수행한다.
• 두 그룹을 병합하는 과정에서 swap이 포함되어 있다. 예를 들어, 뒤쪽 그룹의 index2와 앞쪽 그룹의 index1을 비교할 때 뒤쪽 그룹이 작다면 앞에 남아 있는 데이터 세트보다 앞으로 이동하므로 그만큼 swap이 일어난 것이다.
• 앞쪽 그룹이 작다면 swap은 없음. 즉 result + index2 - K로 뒤쪽 그룹을 먼저 오게 병합할 때 앞쪽에 남은 데이터만큼 result를 업데이트 하면 된다.

---

# 6. 기수 정렬

• 값을 비교하지 않고, 비교할 자릿수를 더한 다음 해당 자릿수만 비교하는 독특한 정렬이다.
• 10개의 큐를 이용하여 일의 자릿수부터 데이터를 저장한다. 
• 시간 복잡도가 가장 짧은 정렬이므로 데이터의 개수가 너무 많을 때 활용하면 좋다.

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

import sys
input = sys.stdin.readline
N = int(input())
count = [0]*10001 # 카운팅 정렬 리스트

for i in range(N):
    count[int(input())] += 1 # count 리스트에 현재 수에 해당하는 index의 값 1 증가

for i in range(10001):
    if count[i] != 0: # i가 기존 input에 있는 수
        for _ in range(count[i]): # 해당 index값만큼 index를 반복하여 출력
            print(i)

• 숫자 크기가 10,000보다 작으므로 10,001 크기의 count 리스트를 선언한다. 문제에서 입력하는 수를 리스트의 인덱스 값으로 판단하고 해당 인덱스 값을 1 증가한다.
• count 리스트를 탐색하며 0이 아닌 경우 해당 값이 있는 index값만큼 반복하여 출력한다.
• 공간 복잡도라는 특수한..보기 힘든 조건이지만 막상 구현은 쉽다!

 

---

# 회고

 

다양한 정렬 알고리즘에 대하여 알아봤다. 가장 잘 쓸 것 같은건 역시 병합 정렬..? 시간 복잡도가 O(nlogn)이니깐...

버블 정렬이지만 버블 정렬로 풀면 안되는 문제...문제를 믿을 수 없다.

 

python의 정렬 함수 sort()는 병합 정렬과 삽입 정렬 아이디어를 더한 하이브리드 정렬 방식이라고 한다.