Machineboy空
Sorting(정렬) - bubble, selection, insertion, quick, merge, radix 본문
Computer/알고리즘
Sorting(정렬) - bubble, selection, insertion, quick, merge, radix
안녕도라 2023. 10. 14. 14:00정렬의 종류
버블 (bubble) | 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식 |
선택 (selection) | 대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식 |
삽입 (insertion) | 대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식 |
퀵 (quick) | pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식 |
병합 (merge) | 이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식 |
기수 (radix) | 데이터의 자릿수를 바탕으로 비교해 데이터를 정렬하는 방식 |
버블정렬(Bubble Sort)
- 두 인접한 데이터의 크기를 비교해 정렬하는 방법
- 시간복잡도는 n2^으로 다른 정렬 알고리즘보다 속도가 느리다.
- 시간복잡도 n2^ : n = 5 라면, 루프 한 번 도는데 n번, 그리고 루프 n번을 도니까 n제곱이 된다.
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]:
temp = A[j]
A[j] = A[j+1]
A[j+1] = temp
for i in range(N):
print(A[i])
선택정렬(Selection Sort)
- 최솟값 또는 최댓값을 찾고 남은 정렬 부분의 가장 앞에 있는 데이터와 swap하는 것이 핵심
- 남은 정렬부분(정렬해야하는 부분)에서 min, max를 찾아가며 swap해주는 방식
- 구현 방법이 복잡하고 시간 복잡도도 n2^로 효율적이지 않아서 많이 사용하지 않는다.
- 시간복잡도 n2^ :
- n = 5라면 처음에 n만큼 탐색 후 맨 앞 fix
- 그 다음 n-1, n-2... n-n : n만큼 반복
- 시간복잡도 n2^ :
삽입 정렬(Insertion Sort)
- 이미 정렬된 데이터의 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식
- 시간 복잡도 : n2^ 느린 편이지만 구현하기 쉽다
퀵 정렬(Quick Sort)
https://youtu.be/aXXWXz5rF64?si=nvD28Z0-D14HATpA
병합 정렬(Merge Sort)
기수 정렬(Radix Sort)
'Computer > 알고리즘' 카테고리의 다른 글
정수론 - 에라토스테네스의 체 / 오일러 피 / 유클리드 호제법 (0) | 2023.12.19 |
---|---|
백준 11004번: K번째 수 - 퀵 정렬 (Quick Sort) (0) | 2023.10.31 |
Query 질의란? (0) | 2023.10.12 |
알고리즘과 디버깅 (1) | 2023.10.11 |
시간복잡도(Time-Complexity), 빅오표기법(Big-O) (0) | 2023.10.11 |