Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo
VisuAlgo is free of charge for Computer Science community on earth. If you like VisuAlgo, the only "payment" that we ask of you is for you to tell the existence of VisuAlgo to other Computer Science students/instructors that you know =) via Facebook/Twitte
visualgo.net
버블 정렬
- 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘
- 예
- 데이터가 네 개 일때
- (데이터 갯수에 따라 복잡도가 떨어지는 것은 아니므로, 네 개로 바로 로직을 이해해보자.)
- data_list = 1, 9, 3, 2
- 1차 로직 적용
- 1 와 9 비교, 자리바꿈없음 1, 9, 3, 2
- 9 와 3 비교, 자리바꿈 1, 3, 9, 2
- 9 와 2 비교, 자리바꿈 1, 3, 2, 9
- 2차 로직 적용
- 1 와 3 비교, 자리바꿈없음 1, 3, 2, 9
- 3 과 2 비교, 자리바꿈 1, 2, 3, 9
- 3 와 9 비교, 자리바꿈없음 1, 2, 3, 9
- 3차 로직 적용
- 1 과 2 비교, 자리바꿈없음 1, 2, 3, 9
- 2 과 3 비교, 자리바꿈없음 1, 2, 3, 9
- 3 과 9 비교, 자리바꿈없음 1, 2, 3, 9
- 데이터가 네 개 일때
def bubblesort(data):
for index in range(len(data) - 1):
swap = False
for index2 in range(len(data) - index - 1):
if data[index2] > data[index2 + 1]:
data[index2], data[index2 + 1] = data[index2 + 1], data[index2]
swap = True
if swap == False:
break
return data
- 알고리즘 분석
- 반복문이 두 개 O(n2)
- 최악의 경우, n∗(n−1)/2
- 완전 정렬이 되어 있는 상태라면 최선은 O(n)
- 반복문이 두 개 O(n2)
삽입 정렬
- 삽입 정렬은 두 번째 인덱스부터 시작
- 해당 인덱스(key 값) 앞에 있는 데이터(B)부터 비교해서 key 값이 더 작으면, B값을 뒤 인덱스로 복사
- 이를 key 값이 더 큰 데이터를 만날때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동
- 예
- 데이터가 네 개 일때 (데이터 갯수에 따라 복잡도가 떨어지는 것은 아니므로, 네 개로 바로 로직을 이해해보자.)
- 예: data_list = 9, 3, 2, 5
- 처음 한번 실행하면, key값은 9, 인덱스(0) - 1 은 0보다 작으므로 끝: 9, 3, 2, 5
- 두 번째 실행하면, key값은 3, 9보다 3이 작으므로 자리 바꾸고, 끝: 3, 9, 2, 5
- 세 번째 실행하면, key값은 2, 9보다 2가 작으므로 자리 바꾸고, 다시 3보다 2가 작으므로 끝: 2, 3, 9, 5
- 네 번째 실행하면, key값은 5, 9보다 5이 작으므로 자리 바꾸고, 3보다는 5가 크므로 끝: 2, 3, 5, 9
- 예: data_list = 9, 3, 2, 5
- 데이터가 네 개 일때 (데이터 갯수에 따라 복잡도가 떨어지는 것은 아니므로, 네 개로 바로 로직을 이해해보자.)
# 3. 알고리즘 구현
for stand in range(len(data_list)) 로 반복
key = data_liststand
for num in range(stand, 0, -1) 반복
#내부 반복문 안에서 data_liststand < data_listnum - 1 이면,
data_listnum - 1, data_listnum = data_listnum, data_listnum - 1
def insertion_sort(data):
for index in range(len(data) - 1):
for index2 in range(index + 1, 0, -1):
if data[index2] < data[index2 - 1]:
data[index2], data[index2 - 1] = data[index2 - 1], data[index2]
else:
break
return data
- 알고리즘 분석
- 반복문이 두 개 O(n2)
- 최악의 경우, n∗(n−1)/2
- 완전 정렬이 되어 있는 상태라면 최선은 O(n)
- 반복문이 두 개 O(n2)
선택 정렬
- 다음과 같은 순서를 반복하며 정렬하는 알고리즘
- 주어진 데이터 중, 최소값을 찾음
- 해당 최소값을 데이터 맨 앞에 위치한 값과 교체함
- 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함
- 예
def selection_sort(data):
for stand in range(len(data) - 1):
lowest = stand
for index in range(stand + 1, len(data)):
if data[lowest] > data[index]:
lowest = index
data[lowest], data[stand] = data[stand], data[lowest]
return data
'Engineering WIKI > Docs' 카테고리의 다른 글
Apache Tomcat(아파치 톰캣)_포트 변경하기 (0) | 2022.12.11 |
---|---|
Path Parameter 와 Query Parameter 구분 (0) | 2022.09.17 |
파이썬 최대공약수와 최소공배수 알고리즘 (0) | 2022.05.26 |
소수 (Prime Number) 판별 (0) | 2022.05.26 |
orphanRemoval 이란? (0) | 2022.04.02 |
Spring JPA CascadeType 종류 (0) | 2022.04.02 |
동시성 vs 병렬성 (헷갈리는 개념 뿌시기) (0) | 2022.02.28 |
API의 개념 뿌수기! (필수 API 개념 기술) (0) | 2021.01.17 |