개념 데이터에서 최소값과 최대값을 빠르고 쉽게 찾기 위한 완전이진트리 형태의 자료구조 완전이진트리: 마지막 레벨을 제외한 모든 레벨이 채워지고 마지막 레벨만 좌 → 우 구조 모든 노드의 데이터는 부모노드는 자식 노드의 값보다 크거나 같다 힙 정렬 root노드를 맨 마지막 인덱스 노드와 swap 맨 마지막 인덱스 노드는 없는 노드 취급하고 root 노드에서 heapify 작업 다시 root노드를 맨 마지막 인덱스 노드와 swap (2번에서 작업한 노드 제외) 반복 힙 정렬과 힙의 시간복잡도 힙의 시간 복잡도 힙의 높이는 O(log(n)) → 왼쪽, 오른쪽 자식은 (root * 2), (root * 2 + 1)이기에 log(n)번씩 건너서 확인하기 때문이고 이것을 전체 길이 n번만큼 반복하기에 힙의 시간 복잡도는 O(nlog(n))...
개념 다른 원소들과 비교만으로 정렬을 수행하는 비교 정렬 분할 정복 알고리즘 중 하나 분할정복이란 → 문제를 2개로 분리하고 해결한 다음 결과를 다시 합치는 전략 매우 빠른 속도를 자랑하며 python의 sort가 퀵정렬로 구현 리스트에 pivot을 지정 후 pivot을 기준으로 작은 요소는 왼쪽, 큰 요소는 오른쪽으로 옮기는 전략 분할 : pivot을 기준으로 2개(좌, 우) 배열로 분할한다. 정복 : 분할한 배열들의 크기가 분할이 불가능할때까지 순환 호출한다....
개념 가장 작은 값을 찾아 맨 왼쪽(앞) index로 위치 변경 0번 index, 1번 index 반복 매번 가장 작은 데이터를 선택하여 정렬 각 위치에 어떤 값이 들어갈지 찾는 정렬 비교와 교환으로 이루어진 알고리즘 순서(오름차순 기준) 주어진 데이터의 →(왼쪽에서 오른쪽) 방향으로 확인한다. 임시로 0번 인덱스를 최소값으로 지정한다. 한칸씩 오른쪽으로 이동하며 비교한다. 길이의 끝까지 돌면서 임시로 지정한 값보다 값이 더 작으면 해당 데이터의 index를 최소 index로 변경한다. 반복이 끝난 후 구해진 최소값 index를 가지고 임시로 지정한 변수와 swap 처리를 해준다....
개념 데이터를 앞에서 하나씩 확인 후 특정 조건에 부합하는 위치(좌 or 우)에 삽입 왼쪽은 이미 정렬되어 있는 가정으로 접근 선택정렬에 비해 실행시간 측면으로 조금 효율적 처음 key값은 두번째(index 1)부터 시작 비교, 시프트(이동), 삽입등이 사용되는 알고리즘 순서(오름차순 기준) 1번 인덱스부터 시작하는 반복문을 만든다. 임시로 1번 인덱스값과 데이터를 가지고 ← 방향으로 반복 비교한다. 왼쪽은 이미 정렬되어 있다는 가정 왼쪽 값이 크다면 큰 값을 현재 position으로 변경해주고 position을 -1 해준다....
개념 서로 인접한(연속된) 두 원소를 확인해 정렬하는 알고리즘 인접한 2개의 원소를 확인하여 조건에 맞는 순서로 교환 비교와 교환으로 이루어진 알고리즘 순서(오름차순 기준) 연속된 두 항목을 가리킨 후 비교한다. 두 항목의 값의 크기가 뒤바뀌어 있으면 값을 교환한다. 비교 포인터를 오른쪽 한칸씩 이동한다. 배열의 끝까지 또는 정렬된 항목까지 1~2단계를 반복한다. 특징 장점 구현이 간단 단점 순차적으로 확인하기 때문에 크기에 맞지 않는 비교가 발생 순차적으로 확인하기 때문에 N개의 길이가 있다면 N번 교환 발생 예제 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 def buble_sort(input_list): unsorted_until_idx = len(input_list) - 1 is_sorted = False while not is_sorted: is_sorted = True for i in range(unsorted_until_idx): if input_list[i] > input_list[i + 1]: temp = input_list[i] input_list[i] = input_list[i + 1] input_list[i + 1] = temp is_sorted = False return input_list...