[알고리즘] 정렬 + 문제풀이

버블정렬 O(N^2)

• loop를 돌며 인접한 데이터 간의 swap 연산 진행
• 특정 루프의 전체 영역에서 swap이 한 번도 진행되지 않으면 정렬이 완료된 것

n = int(input())

num = []

for i in range(n):
  a = int(input())
  num.append(a)

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

for i in num:
  print(i)

 

 

선택정렬 O(N^2)

• 남은 정렬 부분의 가장 작은(or 가장 큰) 데이터를 선택해 가장 앞에 있는 데이터와 바꿈

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

for i in range(len(arr)):
  min_index = i
  for j in range(i+1, len(arr)):
    if arr[min_index] > arr[j]:
      min_index = j
  arr[i], arr[min_index] = arr[min_index], arr[i]

print(arr)

#백준 1427번

import sys
input = sys.stdin.readline
print = sys.stdout.write
num = list(input().rstrip())

for i in range(len(num)):
  max_num = i
  for j in range(i+1,len(num)):
    if num[j] > num[max_num]:
      max_num = j

  if num[i] < num[max_num]:
    num[i], num[max_num] = num[max_num], num[i]

for i in range(len(num)):
  print(num[i])

 

삽입정렬

• 특정한 데이터를 적절한 위치에 삽입한다는 의미 (O(N^2))
• 삽입될 위치 앞의 데이터는 이미 정렬되어있다고 가정해서 살펴볼 필요 X
• 거의 정렬되어 있는 상태라면 퀵정렬보다 효율적
• 맨 앞은 이미 정렬되어있다고 생각해서 1번 index부터 정렬 시작

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-1],arr[j] = arr[j], arr[j-1]
    else:
      break

print(arr)

 

퀵정렬 (혼자 작성할 수 있을 때까지 반복 해보기)

• 피벗을 기준으로 큰 숫자와 작은 숫자를 교환하는 것(O(NlogN))

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

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[right], array[left] = array[left], array[right]

    quick_sort(array, start, right-1)
    quick_sort(array, right+1, end)

quick_sort(array, 0, len(array)-1)
print(array)

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(N+K))
• 모든 데이터가 정수 형태이고 가장 크고 작은 데이터의 차이가 너무 크지 않을 때 사용 가능

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

cnt = [0] * (max(array)+1)

for i in range(len(array)):
  cnt[array[i]] += 1

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

 

문제풀이 현황(기록용)

1	백준 2108번	실버3	△	20230202
2	백준 11651번	실버5	O	20230202