4. 정렬

https://zero0205.notion.site/4-85630a7e1bca49c2bd9d7b5a6a5b02e4

4. 정렬

기준에 따라 데이터를 정렬

• 정렬 : 데이터를 특정한 기준에 따라서 순서대로 나열하는 것
• 정렬을 해놓으면 이진 탐색(Binary Search)이 가능
• 내림차순은 오름차순해서 뒤집기만 하면 되는데, 리스트 뒤집기 연산은 O(N) 정도의 복잡도로 간단히 수행 가능

정렬 알고리즘의 종류

선택 정렬

• 데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸고...→반복
• 소스 코드결과✅ 파이썬의 스와프파이썬은 다음과 같이 간편하게 스와프 가능결과
• [5, 3]
• array = [3, 5] array[0], array[1] = array[1], array[0] print(array)
• : 특정한 리스트가 주어졌을 때 두 변수의 위치를 변경하는 작업
• [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
• 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! 특정한 리스트에서 가장 작은 데이터를 찾는 일이 코딩 테스트에서 잦으므로 선택 정렬 소스코드 형태에 익숙해질 필요가 있음

삽입 정렬

• 특정한 데이터를 적절한 위치에 ‘삽입’. 그 앞까지의 데이터는 이미 정렬되어 있다고 가정.
• 두 번째 데이터부터 시작. (∵ 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문)
• 정렬이 이루어진 원소는 항상 오름차순을 유지하고 있기 때문에 특정한 데이터가 삽입될 위치를 찾을 때(삽입될 위치를 찾기 위하여 왼쪽으로 한 칸씩 이동할 때), 삽입될 데이터보다 작은 데이터를 만나면 그 위치에서 멈추면 됨
• 선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하여 위치를 바꾸는데 삽입 정렬은 그렇지 않음
• 삽입 정렬은 필요할 때만 위치를 바꾸므로 ‘데이터가 거의 정렬되어 있을 때’ 훨씬 효율적
• 소스 코드결과✅ range의 세 번째 매개 변수
• range의 매개 변수는 3개(start, end, step)이다. 세 번째 매개 변수인 step에 -1이 들어가면 start 인덱스부터 시작해서 end + 1 인덱스까지 1씩 감소한다. 앞의 코드에서는 j 변수가 i부터 1까지 1씩 감소한다.
• [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
• 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)
• 삽입 정렬의 시간 복잡도
  • 2중 반복문 → O(N^2)
  • 실제로 수행 시간을 테스트해보면 선택 정렬과 흡사한 시간이 소요됨
  • 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작 ⇒ 최선의 경우 O(N)의 시간 복잡도를 가짐

퀵 정렬

• 정렬 알고리즘 중 가장 많이 사용됨
• 기준(피벗 pivot)을 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸고 리스트를 반으로 나눔. ⇒ 리스트의 크기가 0이나 1이 될 때까지 반복
  • 구체적인 과정
    1. 왼쪽에서부터 피벗보다 큰 데이터 찾기 + 오른쪽에서부터 피벗보다 작은 데이터 찾기
    2. 찾으면 둘이 바꿈 ⇒ 왼쪽에서 오는 것과 오른쪽에서 오는 것이 엇갈릴 때까지 반복
    3. 둘이 엇갈리면 피벗과 작은 데이터의 위치 바꿈
    4. 피벗을 기준으로 2개의 리스트로 나눠짐
    5. 나눠진 리스트에 대해 1~4의 과정 반복 (리스트의 데이터 개수가 1개가 될 때까지)
• 분할 정복(Divide and Conquer)
• 피벗을 설정하고 리스트를 분할하는 방식에 따라 여러 가지 방식으로 퀵 정렬을 구분
  • 호어 분할 : 리스트의 첫 번째 데이터를 피벗으로 한다.
• 소스 코드결과
• [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
• array = [7, 5, 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)
• 파이썬의 장점을 살린 소스 코드
  • 전통적인 퀵 분할 방식과는 조금 다름
  • 피벗과 데이터를 비교하는 비교 연산 횟수 ⬆️ ⇒ 시간 면에서 비효율적 but! 더 직관적이고 기억하기 쉬움

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

• 퀵 정렬의 시간 복잡도
  • 평균 : O(NlogN)
  • 최악 : O(N^2) ⇒ 이미 데이터가 정렬되어 있는 경우

병합 정렬

• 일반적으로 퀵 정렬보다는 느리지만 최악의 경우에도 시간 복잡도 O(NlogN)을 보장.

계수 정렬

• 특정 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘
• 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담음.
• 모든 데이터가 양의 정수라 가정할 때, 데이터의 개수가 N, 데이터 중 최댓값이 K라면 계수 정렬은 최악의 경우에도 **O(N+K)**의 시간 복잡도를 보장한다.
• 데이터 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용 가능 (데이터의 값이 무한한 범위를 가질 수 있는 실수형 데이터가 주어지는 경우 사용이 어려움)
• 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용 가능 WHY?? ⇒ 계수 정렬을 이용할 때는 모든 범위를 담을 수 있는 크기의 리스트(배열)을 선언해야하기 때문. ex) 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000이라면 총 1,000,001개의 데이터가 들어갈 수 있는 리스트 초기화 필요 (∵ 0 ~ 1,000,000까지는 총 1,000,001개의 수이므로)
• 계수 정렬은 직접 데이터의 값을 비교한 뒤에 위치를 변경하며 정렬하는 방식(비교 기반의 정렬 알고리즘)이 아님
• 원리
  • 리스트의 인덱스가 모든 범위를 포함할 수 있도록 리스트의 크기를 선언하고 리스트의 모든 데이터를 0으로 초기화
  • 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킴
  • 정렬 끝!
  ex)⇒ 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가 → 반복0 1 2 3 4 5 6 7 8 9

  2

  2

  2

  1

  1

  2

  1

  1

  1

  2

  출력 결과 : 0 0 1 1 2 2 3 4 5 5 6 7 8 9 9
• 초기 단계 : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2
• 소스 코드결과
• 0 0 1 1 2 2 3 4 5 5 6 7 8 9 9
• # 모든 원소의 값이 0보다 크거나 같다고 가정 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 = ' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력
• 계수 정렬의 시간 복잡도
  • 모든 데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터 중 최대값의 크기를 K라고 할 때, 계수 정렬의 시간 복잡도는 O(N+K) ⇒ 앞에서부터 데이터를 하나씩 확인하며 리스트에서 적절한 인덱스의 값을 1 증가 → N ⇒ 추후에 리스트의 각 인덱스의 값에 해당하는 값들을 확인 → K
  • 데이터의 범위만 한정되어 있다면 매우 빠른 정렬 가능
  • 현존하는 알고리즘 중 기수 정렬과 더불어 가장 빠름
• 계수 정렬의 공간 복잡도
  • 계수 정렬은 때에 따라서 심각하게 비효율적일 수 있음
  • ex) 데이터가 0, 999,999 단 2개만 존재. 그런데 계수 정렬은 이 경우에도 리스트의 크기가 100만개가 되도록 선언 필요 ⇒ 계수 정렬은 아무때나 사용하는 알고리즘은 아님.
  • 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합.
• 계수 정렬이 유리한 상황
  • 데이터의 크기 한정 + 데이터의 크기가 많이 중복되어 있음.

파이썬의 정렬 라이브러리

• 미리 만들어진 라이브러리를 사용하는 것이 더 효과적인 경우가 더 많음.
• 파이썬은 병합 + 삽입 정렬의 아이디어를 더한 하이브리드 방식의 정렬 알고리즘 사용
• 파이썬은 기본 정렬 라이브러리인 sorted() 함수를 제공.

  array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
  
  result = sorted(array)
  print(result)
  

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

• ⇒ sorted는 병합 정렬을 기반으로 만들어짐.
• 리스트 객체의 내장 함수인 sort()도 이용 가능.

  array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
  
  array.sort()
  print(array)
  

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

• 별도의 정렬된 리스트가 반환되지 않고 내부 원소가 바로 정렬됨.
• sorted()나 sort()를 이용할 때는 key 매개변수를 입력으로 받을 수 있음. key 값으로는 하나의 함수가 들어가야 하며 이는 정렬 기준이 됨.

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

  결과
  • lambda 이용?

  dict = {'바나나' : 2, '사과' : 5, '당근' : 3}
  
  array = sorted(dict.items(), key=lambda x : x[1])
  print(array)
  

  결과
• [('바나나', 2), ('당근', 3), ('사과', 5)]
• [('바나나', 2), ('당근', 3), ('사과', 5)]
• ex) 리스트의 데이터가 튜플로 구성되어 있으며, 각 데이터의 두 번째 원소를 기준으로 설정하는 경우
• 정렬 라이브러리의 시간 복잡도
  • 최악의 경우에도 O(NlogN) 보장.
  • 정렬 라이브러리는 이미 잘 작성된 함수이므로 우리가 직접 퀵 정렬 구현할 때보다 효과적.

문제 유형

1. 정렬 라이브러리로 풀 수 있는 문제
   • 단순히 정렬 기법을 알고 있는지 물어보는 문제.
   • 기본 정렬 라이브러리의 사용 방법만 안다면 어렵지 않게 해결 가능
2. 정렬 알고리즘의 원리에 대해 물어보는 문제
   • 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알아야 해결 가능
3. 더 빠른 정렬이 필요한 문제
   • 퀵 정렬 기반의 정렬 기법으로는 해결 불가
   • 계수 정렬 등의 다른 정렬 알고리즘 사용 OR 문제에서 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 해결 가능

위에서 아래로

• 내가 작성한 코드

# n 입력
n = int(input())

arr = []

for i in range(n):
    arr.append(int(input()))

arr.sort(reverse=True)

for j in arr:
    print(j, end = ' ')

• 책의 해답

# N을 입력받기
n = int(input())

# N개의 정수를 입력받아 리스트에 저장
array = []
for i in range(n):
    array.append(int(input()))

array = sorted(array, reverse=True)

# 정렬이 수행된 결과를 출력
for i in array:
    print(i, end = ' ')

• 문제만 잘 읽으면 될 것 같다....내림차순으로 정렬하라는걸 안 보고 무작정 오름차순으로 정렬함. 눈을 똑바로 뜨자
• 내림차순은 sort(reverse=True) 또는 sorted(reverse=True)으로 가능
• sort vs sortedsort() sorted()

  리스트만을 위한 메서드	어떤 iterable 객체도 가능(ex> 딕셔너리)
  리스트를 정렬된 상태로 변경	정렬된 리스트를 반환. (딕셔너리가 들어와도 리스트 형태로 반환)
  기존 리스트를 변경하지는 X

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

• 내가 작성한 코드

n = int(input())

array = []

for i in range(n):
  name, score = input().split()
  score = int(score)
  array.append((name, score))

array.sort(key = lambda x : x[1])

for j in array:
  print(j[0], end = ' ')

• 책의 해답

# N을 입력받기
n = int(input())

# N명의 학생 정보를 입력받아 리스트에 저장
array = []
for i in range(n):
    input_data = input().split()
    # 이름은 문자열 그대로, 점수는 정수형으로 변환하여 저장
    array.append(input_data[0], int(input_data[1]))

# 키(key)를 이용하여, 점수를 기준으로 정렬
array = sorted(array, key=lambda student: student[1])

# 정렬이 수행된 결과를 출력
for student in array:
    print(student[0], end=' ')

두 배열의 원소 교체

• 내가 작성한 코드

# n, k 입력받기
n, k = map(int, input().split())

# 배열 A, B의 원소 입력받기
a = list(map(int, input().split()))
b = list(map(int, input().split()))

# a를 오름차순 정렬, b를 내림차순 정렬
a = sorted(a)
b = sorted(b, reverse=True)

for i in range(k):
    if a[i] < b[i]:
        a[i], b[i] = b[i], a[i]

print(sum(a))

• 책의 해답

n, k = map(int, input().split())    # N과 K를 입력받기
a = list(map(int, input().split())) # 배열 A의 모든 원소를 입력받기    
b = list(map(int, input().split())) # 배열 B의 모든 원소를 입력받기

a.sort()    # 배열 A는 오름차순 정렬 수행
b.sort(reverse=True)    # 배열 B는 내림차순 정렬 수행

# 첫 번째 인덱스부터 확인하며, 두 배열의 원소를 최대 K번 비교
for i in range(k):
    # A의 원소가 B의 원소보다 작은 경우
    if a[i] < b[i]:
        # 두 원소를 교체
        a[i], b[i] = b[i], a[i]
    else:   # A의 원소가 B의 원소보다 크거나 같을 때, 반복문을 멈춤
        break

print(sum(a))   # 배열 A의 모든 원소의 합을 출력

• for문 돌릴 때 A의 원소가 B의 원소보다 크거나 같으면 더이상 for문 안 돌려도 되는걸 생각 안 함! → 이런 점에 주의해서 불필요하게 코드가 돌아가지 않도록 하자!