알고리즘 다시 공부하기 3일차

정렬 알고리즘

→ 도출하는 결과는 같더라도 알고리즘에 따라 성능과 효율이 달라지기 때문에 작동원리와 장단점 파악 필요

→  알고리즘 문제 풀 때 + 코딩테스트 문제 풀 때 기본적으로 자주 사용하게 되는 요소가 아닌가 싶음

• 버블 정렬
• 삽입 정렬
• 병합 정렬
• 셸 정렬
• 선택 정렬

→ 평소에 안썼던 정렬들이 더 많은 거 같음.

⇒ 파이썬은 느리다는 단점이 있어서 퀵 정렬을 쓰는게 좋다고 배웠는데 내용들 보면서 봤을 땐 병합 정렬이 좋을 수도 있겠단 생각이 들었음(+ 연결리스트?)

*파이썬에서 변수 편하게 바꾸기

→ a, b = b, a (양쪽 값을 편하게 바꿀 수 있음, 평소에 temp 써서 임시로 담아두는거 안해둬도 됨!)

1. 버블 정렬

가장 간편하지만 속도가 가장 느린 알고리즘, 가장 큰 값을 반복적으로 옮겨서 정렬 해줌

최악의 경우 시간복잡도가 O(n^2)까지 올라갈 수 있으므로 최대한 작은 데이터셋에 사용

• 작동 원리 : 패스라는 과정을 반복함. 작은 값 부터 큰 값으로 정렬하려고 할 때 제일 큰 값을 리스트의 맨 오른쪽으로 보는내는 것을 통해서 리스트를 정렬하게 됨
• 정렬 할 때 서로 붙어 있는 이웃끼리 값을 비교 해서 더 크다면, 큰 값을 작은 값과 바꿔주고 오른쪽으로 한 칸 이동하게 됨.

list = [25, 22, 21, 24, 23, 27, 26]
lastEle = len(list)-1

for i in range(lastEle):
		if list[i] > list[i+1]:
				list[i], list[i+1] = list[i+1], list[i]

→ 패스라는 과정을 한번 하게 해주는 경우

def bubbleSort(list):
	lastEle = len(list)-1
	for i in range(lastEle, 0, -1):
		for j in range(i):
			if list[j] > list[j+1]
				list[j], list[j+1] = list[j+1], list[j]

→ 두 개의 루프를 통해서 가장 높은 값을 오른쪽으로 이동시키는 과정을 반복해줌

→ 루프 두개의 중첩으로 인해 최악의 경우 O(n^2)으로 시간복잡도가 나타날 수 있음

2. 삽입 정렬

자료 구조에서 데이터 포인트를 하나씩 빼내어 올바른 위치에 집어넣는 과정을 반복하는 것

→ 참고용 gif 인데, 흠… 역시 직접 짜봐야 제일 이해가 잘 되는 거 같다.

def insertionSort(list):
		for i in range(1, len(list)):
				j = i-1
				nextEle = list[i]
				while(list[j] > nextEle) and (j>=0):
						list[j+1] = list[j]
						j = j - 1
				list[j+1] = nextEle
		return list

25 26 22 24 27 23 21
[25, 26, 26, 24, 27, 23, 21]
[25, 25, 26, 24, 27, 23, 21]
[22, 25, 26, 26, 27, 23, 21]
[22, 25, 25, 26, 27, 23, 21]
[22, 24, 25, 26, 27, 27, 21]
[22, 24, 25, 26, 26, 27, 21]
[22, 24, 25, 25, 26, 27, 21]
[22, 24, 24, 25, 26, 27, 21]
[22, 23, 24, 25, 26, 27, 27]
[22, 23, 24, 25, 26, 26, 27]
[22, 23, 24, 25, 25, 26, 27]
[22, 23, 24, 24, 25, 26, 27]
[22, 23, 23, 24, 25, 26, 27]
[22, 22, 23, 24, 25, 26, 27]
[21, 22, 23, 24, 25, 26, 27]

→ 실행 되어지는 과정

⇒리스트 전체를 순회하면서 조건을 만족하면 다음 요소의 위치에 현재 요소를 삽입 해주고 자리를 뺏긴 다음 요소는 while문이 끝나기 전에 위치를 재조정 하여 주는 방식

이라고는 하는데 말이 참 어려운 거 같다. 결국에는 그냥 맨 처음 자리부터 뒤쪽으로 하나씩 비교를 하여주고 비교를 할 때는 첫자리부터 하나씩 비교를 하여주는식으로 해주면…? 만약에 역순으로 리스트 자리가 배치되어져 있는 경우에는 시간 복잡도가 O(n^2)으로 걸려서 데이터 셋이 크면 터지는 결말을 맞지 않을까 싶음.

*추가작성 예정