Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
Tags
- Python
- SQLSCOTT
- 파이썬데이터분석주피터노트북
- 파이썬알고리즘
- matplotlib
- python데이터분석
- python알고리즘
- 주피터노트북그래프
- 맷플롯립
- 주피터노트북판다스
- sql따라하기
- SQL수업
- 판다스그래프
- 데이터분석시각화
- 파이썬
- python수업
- 주피터노트북맷플롯립
- 파이썬데이터분석
- SQL
- sql연습
- 파이썬크롤링
- 파이썬시각화
- 주피터노트북
- 파이썬수업
- 수업기록
- 파이썬차트
- 판다스데이터분석
- 팀플기록
- 주피터노트북데이터분석
- sql연습하기
Archives
- Today
- Total
IT_developers
Python algorithm 개념 및 실습 - 정렬(1) 본문
알고리즘이란 ?
- 어떤 일을 하기 위한 명령의 집합
- 문제 해결 방법을 추상화하여 각 절차를 논리적으로 기술해 놓은 것
- 어떤 문제를 해결하기 위한 절차나 방법
알고리즘 복잡도
- Complexity
- 어떤 알고리즘이 문제를 풀기 위해 해야하는 계산이 얼마나 복잡한가?
- 알고리즘의 성능을 객관적으로 평가하는 기준
- 시간복잡도(time complexity) : 실행 횟수로 판단
- 공간복잡도(space complexity) : 기억공간과 파일 공간의 사용량
- 빅오 표기법 ( Big O Notation)
- 알고리즘이 얼마나 빠른지 표시하는 방법
- 입력 데이터 크기 증가할 때 알고리즘 연산 시간(횟수)의 증가 방식
- 연산의 횟수를 비교함
- O(n) : 계산 복잡도
- O : 빅 O
- n : 연산 횟수
- O(1) : 입력 크기 n과 계산 복잡도가 무관 할때 ex) n(n+1)/2
- O(logn) : 입력 크기 n의 로그 값에 비례하여 증가 ex) 이분탐색
- O(n) : 입력 크기 n에 비례하여 복잡도 증가 ex) 최댓값, 순차탐색
- O(nlogn) : 입력 크기 n과 로그 n 값의 곱에 비례하여 복잡도 증가 ex) 병합정렬, 퀵정렬
- O(n²) : 입력 크기 n의 제곱에 비례하여 복잡도 증가 ex) 선택정렬, 삽입정렬
- O(n₂) : 입력 크기가 n 일 때, 2의 n 제곱 값에 비례하여 복잡도 증가 ex)하노이의 탑
선택 정렬 : 주어진 리스트 안의 자료를 작은 수부터 큰 수 순서로 배열하는 정렬
- 알고리즘 복잡도 : O(n ²)
# 이중 for문 사용 - 특정 위치부터 자료 값 중 최솟값의 위치를 찾은 후
# 정렬을 원하는 자리와 교환
# 정렬할 때 대부분 이중 for문을 사용
# 오름차순
def selection_sort1(list1):
size = len(list1)
for i in range(0, size - 1): # 0,1,2,3 자리까지만 정렬
# 최솟값에 대한 변수
min_idx = i
for j in range(i + 1, size):
if list1[j] < list1[min_idx]:
min_idx = j
# for문 종료 후 최솟값의 위치를 확인
# 찾은 최솟값과 정렬 위치를 교환
list1[i], list1[min_idx] = list1[min_idx], list1[i]
# 내림차순
def selection_sort2(list1):
size = len(list1)
for i in range(0, size - 1):
max_idx = i
for j in range(i + 1, size):
if list1[j] > list1[max_idx]:
max_idx = j
list1[i], list1[max_idx] = list1[max_idx], list1[i]
if __name__ == "__main__":
list1 = [35, 9, 2, 85, 17]
print("오름차순")
selection_sort1(list1)
print("선택 정렬 : ", list1)
print("내림차순")
selection_sort2(list1)
print("선택 정렬 : ", list1)
삽입 정렬 : 제일 처음에 있는 요소를 기준으로 나머지 요소들과 비교하면 정렬
# result에 v가 들어가야 할 위치를 리턴하는 함수
def find_ins_idx(r, v):
# r은 이미 정렬된 리스트 상태
# r의 자료를 앞에서부터 확인
for i in range(0, len(r)):
# v가 어느 위치에 들어가는지 찾기
if v < r[i]:
return i
# 적절한 위치를 못 찾을 경우에는 v가 이미 정렬된 리스트보다
# 크다는 뜻이므로 맨 뒤에 삽입
return len(r)
def insertion_sort1(list1):
result = []
while list1:
value = list1.pop(0) # 하나의 값만 가지고 나옴.
ins_idx = find_ins_idx(result, value)
result.insert(ins_idx, value)
return result
if __name__ == "__main__":
list1 = [2, 4, 5, 1, 3]
print("삽입 정렬 : ", insertion_sort1(list1))
하나의 리스트에서 구현
# 오름차순 정렬
def insertion_sort1(list1):
# 현재 리스트 길이 구하기
size = len(list1)
# for 1 ~ n
for i in range(1, size):
# i번 위치에 있는 값을 key 변수에 저장
key = list1[i]
# j를 i바로 왼쪽 위치로 지정
j = i - 1
# 리스트의 j번 위치에 있는 값과 key를 비교해 key가 삽입될 위치 찾기
# while문
# j는 0 자리 앞으로는 갈 수 없음
while j >= 0 and list1[j] > key:
list1[j + 1] = list1[j]
j -= 1
# while문 종료 후 찾은 삽입 위치에 key 저장
list1[j + 1] = key
if __name__ == "__main__":
list1 = [2, 4, 5, 1, 3]
insertion_sort1(list1)
print("삽입 정렬 : ", list1)
'Python' 카테고리의 다른 글
Python algorithm 개념 및 실습 - 이진 탐색 (0) | 2022.09.19 |
---|---|
Python algorithm 개념 및 실습 - 정렬(2) (0) | 2022.09.18 |
Python algorithm 개념 및 실습 - 순차탐색 (0) | 2022.09.17 |
Python algorithm 개념 및 실습 - 피보나치, 하노이 탑 (0) | 2022.09.17 |
Python algorithm 개념 및 실습 - 최대공약수, 유클리드 (0) | 2022.09.17 |
Comments