Study Blog

힙 정렬이란? 힙 정렬은 힙의 특성을 이용하여 정렬하는 알고리즘 최소값이나 최대값을 빠르게 찾기 위해 완전 이진 트리를 이용하는 트리구조, 형제 트리의 대소관계가 일정하지 않은 것을 부분 순서 트리라고도 함 '부모의 값이 자식의 값보다 항상 크다 or 작다'는 조건을 만족하는 완전 이진 트리(왼쪽부터 자식 노드를 추가하여 상태를 유지하는 것) ⭐️그림으로 이해하는 용어 정리 최대 힙: 큰 값이 위로 오게끔 정렬(아래 그림 참고) 최소 힙: 작은 값이 위로 오게끔 정렬(아래 그림 참고) 이진: 부모가 가질 수 있는 자식 노드의 최대 개수가 2개인 것(아래 그림 참고) 루트: 트리의 최상단 노드(아래 그림 참고) 리프노드(단말노드): 트리의 최하단 노드(자식이 없는 노드) 힙의 원소를 배열에 저장하는 순서 ..

병합 정렬이란? - 배열을 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복(재귀) - 퀵 정렬과 다르게 피벗값이 존재하지 않음(배열 항상 반으로 쪼개기 때문) - 병합할 때 2의 배수만큼 병합함 - 시간 복잡도는 O(n log n) 을 보장 - 작업용 배열을 생성할 때 추가적인 데이터 공간이 필요하므로 메모리 활용면에서는 비효율적이라는 문제가 있음 정렬을 마친 두 배열의 병합 과정 병합을 마치면 위와 같이 정렬이 완료되는데 그 과정을 자세히 들여다 보면 세 가지 과정으로 수행된다. 1) 각 배열의 커서인 pa, pb, pc를 만들고 각각 0을 저장, 각 배열의 원소 수를 담는 na, nb, nc를 만들고 원소의 길이를 저장. 2) pa와 pb를 비교하여 작은 값을 pc에 저장...

지난 글에서 퀵 정렬에 대해 살펴보았다. https://vibeee.tistory.com/47 [정렬 알고리즘] 퀵 정렬 퀵 정렬이란? - 일반적으로 사용되는 아주 빠른(quick) 정렬 알고리즘 - Charles A. R Hoare에 의해 고안됨 - 중심 축이 되는 값(피벗)을 선택하여 그룹을 나누어가는 방법 - 재귀적으로 호출하여 진행하 vibeee.tistory.com 퀵 정렬에서의 피벗 퀵 정렬의 경우 피벗을 선택하는 방법에 따라 성능이 달라지기 때문에 결국 피벗을 선택하는 방법이 성능을 좌우한다고 볼 수 있다. 아래 예시를 통해 피벗을 선택하는 예시를 살펴보자. 먼저 위와 같은 배열이 있을 때, 맨 앞 원소(8)를 선택한다고 해보자. 만약 8이 피벗으로 선택된다면, 0~7과 8이 있는 두 가지 ..

퀵 정렬이란? - 일반적으로 사용되는 아주 빠른(quick) 정렬 알고리즘 - Charles A. R Hoare에 의해 고안됨 - 중심 축이 되는 값(피벗)을 선택하여 그룹을 나누어가는 방법 - 재귀적으로 호출하여 진행하는 것이 기본적인 형태 퀵 정렬은 아래와 같이 진행된다. 먼저 키가 168cm인 학생 A를 선택해서 피벗으로 삼고 이 학생을 기준으로 168cm 미만인 그룹과 168cm 이상인 그룹으로 나누고, 이 과정을 반복해서 피벗을 선택하여 나누기를 반복하여 모든 그룹이 1명씩 남으면 정렬이 완료된다. 피벗은 다른 말로 중심축이라고도 하는데, 임의로 선택할 수 있고, 선택된 피벗은 2개로 나눈 그룹 어디에 넣어도 상관이 없다. 배열을 두 그룹으로 나누기 1) 피벗, pl(왼쪽 커서), pr(오른쪽 ..

단순 삽입 정렬이란? - 주목한 원소보다 더 앞쪽에서 알맞은 위치로 삽입하며 정렬하는 알고리즘 - 원소의 비교 횟수와 교환 횟수는 모두 n² / 2번 단순 삽입 정렬의 진행 과정 1. 두 번째 원소인 4부터 주목한다. 4는 6보다 앞쪽에 위치해야 하기때문에 맨 앞에 삽입하고 6을 오른쪽으로 옮긴다. 2. 세 번째 원소인 1에 주목한다. 1은 4보다 앞쪽에 위치해야 하기때문에 맨 앞에 삽입하고 4와 6을 오른쪽으로 옮긴다. 3. 단순 삽입 정렬은 위와 같이 '아직 정렬되지 않은 부분의 맨 앞 원소를 정렬된 부분의 알맞은 위치에 삽입' 하는 과정을 반복한다. 단순 삽입 정렬은 다음과 같이 종료 조건이 두 가지이다. 1. 정렬된 배열의 왼쪽 끝에 도달한 경우 -> 가장 값이 작은 것이다. 2. tmp보다 작거..