정렬

개념

데이터를 특정한 기준에 따라서 순서대로 나열하는 것

+) 뒤집는 연산은 O(N)

1. 선택정렬
   • 매번 가장 작은 수를 선택해서 정렬하는 알고리즘 - O($N^2)$

   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]
   
   print(array)
   

2. 삽입정렬
   • 처리되지 않은 데이터를 하나씩 적절한 위치에 삽입 - $O(N^2)$ but 거의 정렬되있다면 최선 O(N)

   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): # 인덱스 i부터 1까지 감소하며 반복하는 문법
           if array[j] < array[j - 1]: # 한 칸씩 왼쪽으로 이동
               array[j], array[j - 1] = array[j - 1], array[j]
           else: # 자기보다 작은 데이터를 만나면 그자리에서 멈춤
               break
   print(array)
   

3. 퀵 정렬
   • 기준 데이터를 설정 후, 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법 - $O(NlogN)$

   array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
   
   def quick_sort(array, start, end):
       if start >= end: # 원소가 1개인 경우 종료
           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)
   
   # 단축 퀵정렬
   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))
   

4. 계수 정렬
   • 특정 조건에서만 매우 빠르게 동작 (동일한 값을 가진 데이터가 여러개일 때)
   • 데이터의 크기 범위가 제한되어 정수 형태로 표현할때 사용 가능
   • 데이터 개수 N, 최대값 K ⇒ $O(N+K)$

   array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
   # 모든 범위를 포함하는 리스트 선언(모든 값은 0 초기화)
   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=' ')
   

+) 파이썬 기본 정렬 라이브러리 $O(NlogN)$

위에서 아래로

• 사이트/난이도: 동빈북/1
• 코드

n = int(input())
nums = []
for _ in range(n):
    nums.append(int(input()))
nums.sort(reverse=True)
for num in nums:
    print(num, end=' ')

• 느낀점 : 파이썬 기본 정렬 라이브러리 사용 문제

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

• 사이트/난이도: 동빈북/1
• 코드

n = int(input())
arr = []
for _ in range(n):
    name, grade = input().split()
    arr.append((name, int(grade)))

arr.sort(key=lambda x: x[1])
for name, grade in arr:
    print(name, end=' ')

• 느낀점 : 파이썬 기본 정렬 라이브러리에 key=lambda 사용하기

두 배열의 원소 교체

• 사이트/난이도: 동빈북/1
• 코드

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]:
        break
    a[i], b[i] = b[i], a[i]

print(sum(a))

• 느낀점 : A에서 가장 작은원소와 B의 가장 큰원소를 교체하기

시간 복잡도 정리

제한시간 1초 기준

1. N의 범위가 500 ⇒ $O(N^3)$
2. N의 범위가 2000 ⇒ $O(N^2)$
3. N의 범위가 100000 (십만) ⇒ $O(NlogN)$
4. N의 범위가 10000000 (천만) ⇒ $O(N)$

대략 10억이 넘어가면 C언어 기준 1초 이상 소모

천만을 기준으로 생각하기