Study Blog

도수 정렬은 원소의 대소 관계를 판단하지 않고 빠르게 정렬하는 알고리즘으로, 분포수 세기 정렬이라고도 한다. 도수 정렬 알아보기지금까지 학습한 정렬 알고리즘에서는 두 원소의 키값을 비교하여 정렬했다. 하지만 도수 정렬은 원소를 비교할 필요가 없다는 특징이 있다. 아래 그림은 10점 만점 테스트에서 학생 9명의 점수를 도수 정렬하는 알고리즘을 나타낸 것이다.정렬할 배열은 a, 원소 수는 n, 점수의 최댓값은 max이다. 1단계: 도수 분포표 만들기먼저 아래 그림처럼 배열 a에 있는 학생들의 점수를 바탕으로 '각 점수에 해당하는 학생이 몇 명인가'를 나타내는 도수 분포표를 만들어야 한다. 도수 분포표를 저장하는 곳은 원소 수가 11개인 배열 f이다.(0~10점을 나타내기 위해 원소는 총 11개이다)먼저 배열..

병합 정렬이란?- 배열을 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복(재귀)- 퀵 정렬과 다르게 피벗값이 존재하지 않음(배열 항상 반으로 쪼개기 때문)- 병합할 때 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(오른쪽 커서) 선택..

하노이의 탑 기본 개념하노이의 탑은 작은 원반이 위에, 큰 원반이 아래에 위치하는 규칙을 지키면서 기둥 3개를 이용해서 원반을 옮기는 문제이다.먼저 크기가 모두 다른 원반이 첫 번째 기둥에 쌓여 있는 상태로 시작한다(이때 작은 원반은 위에, 큰 원반은 아래에 있다.)이 상태에서 모든 원반을 세 번째 기둥에 최소 횟수로 옮기면 된다.원반은 1개씩 옮길 수 있으며 큰 원반은 작은 원반 위에 쌓을 수 없다. 원반이 3개일 때원반을 그룹으로 묶어서 옮기는 과정을 살펴보자(그룹으로 묶는 이유는 위에서 살펴봤듯이 어차피 가장 하단에 있는 원반을 제외한 나머지 원반들이 옮겨지는 과정은 동일하기 때문이다.)원반 1과 원반 2를 그룹으로 묶으면 가장 먼저 이 그룹을 중간 기둥으로 옮긴 후에 가장 큰 원반 3을 목표 기둥..