Study Blog

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

지난 글에서 퀵 정렬에 대해 살펴보았다.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보다 작거나 키값이 ..

선택 정렬이란?- 가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업을 반복하며 정렬하는 알고리즘- 원솟값을 비교하는 횟수: (n² - n) / 2번- 시간복잡도 측면에서 퀵 정렬과 같은 다른 정렬방법이나 파이썬 내장 라이브러리를 사용한 정렬 방법보다 비효율적 선택 정렬의 수행 과정1. 선택 정렬은 첫 번째 원소를 두 번째 원소부터 마지막 원소까지 차례대로 비교하여 가장 작은 원소를 찾아 첫 번째에 놓음2. 두 번째 원소를 세 번째 원소부터 마지막 원소까지와 차례대로 비교, 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복선택 정렬은 위와 같은 과정으로 수행된다.다시 한 번 간단히 정리하면, 선택 정렬은 아직 정렬하지 않은 범위에서 값이 가장 작은 원소를 선택, 아직 정렬하지 않은 부분의 맨 앞 ..