Algorithm/Sort
-
[알고리즘/Algorithm] 파이썬으로 퀵 정렬(Quick Sort) 알아보기Algorithm/Sort 2021. 7. 13. 22:49
Quick Sort (퀵 정렬) 기준점 (pivot)을 정해서, 기준점보다 작은 데이터는 왼쪽, 기준점보다 큰 데이터는 오른쪽으로 모으는 함수를 작성 각 왼쪽, 오른쪽 데이터를 재귀 함수를 활용해서 다시 동일 함수를 호출하여 위 작업을 반복 함수는 왼쪽, 오른쪽 데이터를 리턴 퀵 정렬 흐름 퀵 정렬은 위 그림과 같이 기준점(pivot)을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 정렬하고, 또 나뉘어진 값에서 왼쪽과 오른쪽으로 정렬하며 정렬될 때까지 반복하며 정렬하는 알고리즘이다. 파이썬으로 구현한 퀵 정렬 def quick_sort(data): if len(data) item] right = [item for item in data[1:] if pivot
-
[알고리즘/Algorithm] 파이썬으로 병합/합병 정렬(Merge Sort) 알아보기Algorithm/Sort 2021. 7. 13. 22:27
Merge Sort (병합 정렬) 리스트를 절반으로 잘라 비슷한 크기의 리스트 2개로 나눈다. 각 부분 리스트를 재귀적으로 병합 정렬을 이용해 정렬한다. 두 부분 리스트를 다시 하나의 정렬되 리스트로 병합한다. 병합 정렬 흐름 그림 병합 정렬은 그림과 같이 리스트를 분할(split)한 후에 병합(merge)를 반복하며 정렬한다. 파이썬으로 구현한 병합 정렬 def merge_sort(data): return split(data) def split(data): if len(data) left_point and len(right) > right_point: if left[left_point] > right[right_point]: merged.append(right[right_point]) right_poi..
-
[알고리즘/Algorithm] 파이썬으로 선택 정렬(Selection Sort) 알아보기Algorithm/Sort 2021. 7. 6. 21:41
Selection Sort (선택 정렬) 다음과 같은 순서를 반복하며 정렬하는 알고리즘 주어진 데이터 중, 최소값을 찾는다. 해당 최소값을 데이터 맨 앞에 위치한 값과 교체한다. 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복한다. 선택 정렬 흐름 그림과 같이 한 루프마다 제일 작은 값을 찾아 왼쪽부터 차례차례 스왑하며 정렬해준다. 개인적으로 기본 정렬 3개(버블 정렬, 선택 정렬, 삽입 정렬)중 제일 직관적인 정렬 알고리즘이라고 생각이 들었다. 선택 정렬을 파이썬으로 구현하며 아래와 같이 구현할 수 있다. def selection_sort(target): # 10개의 데이터가 있는 리스트는 최대 9번의 정렬이면 정렬됨 # 따라서 i는 range는 len - 1 for i in range(len..
-
[알고리즘/Algorithm] 파이썬으로 삽입 정렬(Insertion Sort) 알아보기Algorithm/Sort 2021. 7. 5. 23:21
Insertion Sort (삽입 정렬) : 다음과 같은 순서를 반복하며 정렬하는 알고리즘 삽입 정렬은 두 번째 인덱스부터 시작 해당 인덱스 앞에 있는 데이터(B)부터 비교해서 Key 값이 더 작으면, B값을 뒤 인덱스로 복사 이를 Key 값이 더 큰 데이터를 만날때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 Key 값을 이동 삽입 정렬 흐름 삽입 정렬은 그림과 같이 해당 인덱스의 요소에서 그 앞의 요소와 비교를 해서 앞의 요소가 크다면 서로 스왑을 해서 위치를 바꿔준다. 스왑을 한 번 해줬다고 바로 해당 인덱스의 다음 요소부터 또 비교를 시작하는 것이 아니라, 그림에서 4 ~ 6번과 같이 스왑된 요소가 자기 자리를 찾을 때까지 최대 0번째 인덱스까지 비교해서 자기 자리를 찾아간다. 위 그림에서..
-
[알고리즘/Algorithm] 파이썬으로 버블 정렬(Bubble Sort) 알아보기Algorithm/Sort 2021. 7. 1. 22:37
Bubble Sort (버블 정렬) : 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘 버블 정렬 흐름 버블 정렬은 위 그림과 같이 리스트에서 한 칸씩 전진해가며 바로 앞에 있는 값과 비교해서 크면 스왑하고 아니면 지나간다. 그렇기 때문에 만약 리스트의 첫 번째 공간에있는 데이터가 리스트내에 제일 큰 값이라면 계속 그 값을 스왑해가면서 한 번의 루프에 그 값이 제일 마지막으로 이동해 있을 것이다. 만약 위 그림에서 리스트의 첫번째 공간의 데이터 5가 만약 11이었다고 한다면 첫 번째 루프에 11이 뒤에 있는 모든 값과 비교하면서 스왑해서 제일 마지막 공간에 위치하게 됐을 것이다. 아이디어 1. : 그렇다면 루프가 한 번씩 지날 때마다 비교하는 횟..