[알고리즘] 3. 정렬

Index

1. 정렬

2. 버블 정렬

3. 삽입 정렬

4. 선택 정렬

5. 퀵 정렬

6. 병합 정렬

7. 계수 정렬

8. 추천 문제

9. 참고자료

---

1.  정렬

정렬(Sort)

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

 

2.  버블 정렬

버블 정렬(Bubble Sort)

 

def bubble_sort(arr: list):
    for i in range(len(arr)):
    	for j in range(len(arr)-1):
        	if (arr[j] > arr[j+1]:
            	arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

3.  삽입 정렬

삽입 정렬(Insertion Sort)

- 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입

- 선택 정렬에 비해 더 효율적, 데이터가 정렬되어 있는 상태라면 더 빠르게 동작O(N)

- O(N^2)

def insertion_sort(arr: list):
  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]
      else:
        break
  return arr

 

4.  선택 정렬

선택 정렬(Selection Sort)

- 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복

- O(N^2)

def selection_sort(arr: list):
  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]
  return arr

 

5. 퀵 정렬

퀵 정렬(Quick Sort)

- 기준 데이터(Pivot)을 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법

- O(NlogN)

- 최악의 경우 O(N^2)

 

(동작 과정)

1. pivot 설정 후 좌측 포인터와 우측 포인터를 각각 한칸씩 이동하면서 pivot보다 큰, 작은 데이터를 선택하여 서로 위치를 변경

2. 1번 과정을 반복, 좌측과 우측의 포인터가 엇갈리는 경우 pivot과 작은 데이터의 위치를 변경

 

def quick_sort(arr, start, end):
  if start >= end:
    return
  pivot = start
  left = start + 1
  right = end
  while (left <= right):
    while (left <= end and arr[left] <= arr[pivot])
      left += 1
    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)
  
  return arr

(python 방식 구현)

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)

 

6.  병합 정렬

 

7.  계수 정렬

계수 정렬

- 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘

- 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능

- 최악의 경우 O(N+K): N은 데이터의 개수, K는 양수 데이터 중 최댓값이 K

- 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적으로 사용

 

count = [0] *(max(arr) + 1)

for i in range(len(arr)):
  count[arr[i]] += 1

 

8.  추천 문제

정렬

- 수 정렬하기(https://www.acmicpc.net/problem/2750)

- 대표값2(https://www.acmicpc.net/problem/2587)

- 수 정렬하기3(https://www.acmicpc.net/problem/10989)

- 좌표 정렬하기 2(https://www.acmicpc.net/problem/11651)

- K번째수(https://school.programmers.co.kr/learn/courses/30/lessons/42748)

- 가장 큰 수(https://school.programmers.co.kr/learn/courses/30/lessons/42746)

- H-Index(https://school.programmers.co.kr/learn/courses/30/lessons/42747)

 

---

참고 자료

[Video: 동빈나의 이코테 2021(정렬)] https://www.youtube.com/watch?v=KGyK-pNvWos&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=4