2023. 3. 28. 01:30ㆍ_Study/Algorithm
O(n2)의 시간 복잡도를 가지는 정렬 알고리즘
목차
1. 버블 정렬(Bubble sort)
2. 선택 정렬(Selection Sort)
3. 삽입 정렬(Insertion Sort)
4. 쉘 정렬 (Shell Sort)
정렬은 데이터를 정해진 기준에 따라 배치해 의미 있는 구조로 재설정하는 것을 말한다.
def bubbleSort(x):
length = len(x)-1
for i in range(length):
for j in range(length-i):
if x[j] > x[j+1]:
x[j], x[j+1] = x[j+1], x[j]
return x
1. 버블 정렬 (bubble sort)
- 간단하게 구현할 수 있다.
- 속도가 느리다.
- 이웃하는 두 거품을 크기순으로 swap 한다고 생각하면 된다. swap이 발생하지 않았다면 모두 정렬
- 거의 모든 상황에서 최악의 성능을 보여준다.
- 가장 손쉽게 구현하고 만들기가 쉽지만 알고리즘 적에서 대단히 비효율적이라 교육용으로 사용된다.
https://panthema.net/2013/sound-of-sorting/
The Sound of Sorting - "Audibilization" and Visualization of Sorting Algorithms - panthema.net
The Sound of Sorting - "Audibilization" and Visualization of Sorting Algorithms TalkBox macino: You could do gravity sorting. Piotr: MSD radix sort is wrong for some sizes with input n-2 equal.Binary insertion sort over-inserts the equal elements, making n
panthema.net
약간 정렬된 경우 오히려 성능이 빠르다.
1) Random 인 경우 2) 오름차순인경우
오름차순인경우 이미 정렬한 알고리즘을 확인한다고 계속 반복한다.
3) 내림차순인경우 4) 같은 값이 많은경우 (아......)
파생으로 칵테일 정렬(양방향 거품정렬)이 있다.
최악 시간복잡도 O(n2) 비교, O(n2) 교환 : 반대로 되어있는 경
최선 시간복잡도 O(n) 비교, O(1) 교환 : 이미 정렬된 경우
평균 시간복잡도 O(n2) 비교, O(n2) 교환
공간복잡도 : O(1) 보조
슈도코드
for i 0~N-1만큼 반복:
for j 0~ N-1-i만큼 반복:
현재 A리스트의 값보다 1칸 오른쪽 리스트의 값이 더 작으면 두 수를 바꾼다.
백준 2750번 수 정렬하기로 과정을 알아보자.
Tip : N의 최대 범위가 1000으로 매우 작기 때문에 버블 정렬 알고리즘을 이용해도 문제 해결 가능
빨간색 : swap 파란색: no swap 보라색 : 정렬데이터
1번째 루프
| 5 | 2 | 3 | 4 | 1 |
| 2 | 5 | 3 | 4 | 1 |
| 2 | 3 | 5 | 4 | 1 |
| 2 | 3 | 4 | 5 | 1 |
| 2 | 3 | 4 | 1 | 5 |
2번째 루프
| 2 | 3 | 4 | 1 | 5 |
| 2 | 3 | 4 | 1 | 5 |
| 2 | 3 | 1 | 4 | 5 |
3번째 루프
| 2 | 3 | 1 | 4 | 5 |
| 2 | 1 | 3 | 4 | 5 |
4번째 루프
| 1 | 2 | 3 | 4 | 5 |
디버깅 shift+F9
F8 한줄씩 실행
N = int(input())
lists = []
for i in range(N):
lists.append(int(input()))
def bubbleSort(lists):
for i in range(len(lists)):
for j in range(len(lists)-1-i):
if (lists[j]>lists[j+1]):
lists[j],lists[j+1] = lists[j+1],lists[j]
print(lists)
bubbleSort(lists)
백준 1377번 수 정렬하기로 과정을 알아보자.
http://acmicpc.net/problem/1377
위 코드를 확인하면 일종의 flag함수로 swap이 작동하면 change가 True로 변경된다.
즉 change가 false 일때, 정렬이 종료되었을 때를 cout(씨아웃) 으로 출력한다.
얼마만에 정렬이 종료될 수 있을까?
다만 이 문제는 N의 최대범위가 500000이기 때문에 bubbleSort를 사용하면 시간이 초과될 수 있다.
index를 고려하여 문제를 푸는 방법을 적용하면
방법이 가능한 이유는 결괏값을 분석하면 -인 경우는 뒤로 밀린 경우. +인 경우는 수가 작아 앞으로 정렬된 경우로 한 번 swap 일 때마다 앞으로 한 칸 가므로 1씩 늘어난다.
따라서 마지막 정렬까지 더하여 2+1 3인 경우로 생각한다.
import sys
def main():
input = sys.stdin.readline
N = int(input())
lists = []
lists3 = []
for i in range(N):
lists.append((int(input()),i))
max = 0
lists = sorted(lists)
# list의 변경을 확인
for i in range(N):
if max < lists[i][1] - i:
max = lists[i][1] - i
print(max+1)
main()
http://boj.kr/d4f7238075b147ce8023c98244fbb81c
공유 소스 보기
www.acmicpc.net
참고자료 : Do it! 코딩테스트 - 기초편