초코레

요소의 대소 관계를 판단하지 않고 빠르게 정렬할 수 있는 알고리즘 if문 대신 for문만을 사용해 정렬할 수 있는 매우 아름다운 알고리즘 데이터의 비교, 교환 작업이 필요 없어 매우 빠르다. 단일 for문만을 사용하여 재귀 호출, 이중 for문이 없어 아주 효율적인 알고리즘 하지만 도수분포표가 필요하기 때문에 데이터의 최솟값과 최댓값을 미리 알고 있는 경우에만 사용할 수 있다. 각 단계(for문)에서 배열 요소를 건너뛰지 않고 순서대로 스캔하기 때문에 같은 값에 대해서 순서가 바뀌는 일이 없어 안정적인 알고리즘이다. 도수 정렬 알고리즘은 도수분포표 작성, 누석도수분포표 작성, 목적 배열 만들기, 배열 복사의 4단계로 이루어진다. 10점 만점의 테스트에서 학생 9명의 점수에 대해 도수 정렬하기 도수분포표 ..

힙(heap)을 사용하여 정렬하는 알고리즘 힙은 '부모 값 >= 자식 값' 라는 조건을 만족하는 완전이진트리이다. 완전이진트리의 특징은 '완전이진' 상태이다. 완전 : 부모는 자식을 왼쪽부터 추가하는 모양을 유지한다는 뜻 이진 : 부모가 가질 수 있는 자식의 개수는 최대 2개라는 뜻 따라서 힙의 가장 위쪽에 있는 루트가 가장 큰 값이 된다. 힙은 형제의 대소 관계는 정해져 있기 않기 때문에 부분순서트리(partial ordered tree)라고도 한다. 힙의 요소를 배열에 저장하면 부모와 자식의 인덱스 관계는 다음과 같다. 부모는 a[(i - 1) / 2] 왼쪽 자식은 a[i * 2 + 1] 오른쪽 자식은 a[i * 2 + 2] 힙 정렬은 '가장 큰 값이 루트에 위치'한다는 특징을 이용하는 정렬 알고리즘..

배열을 앞부분과 뒷부분으로 나누어 각각 정렬한 다음 병합하는 작업을 반복하여 정렬을 수행하는 알고리즘 정렬을 마친 배열의 병합을 응용하여 분할 정복법에 따라 정렬하는 알고리즘 먼저 배열을 앞부분과 뒷부분으로 나눈다. 이때 앞뒤의 각 배열을 정렬할 때는 다시 병합 정렬을 적용한다. 나눈 두 배열을 각각 정렬하고 병합하면 배열 모두를 정렬할 수 있다. 배열의 요소 개수가 2개 이상인 경우에 배열의 앞부분과 뒷부분을 각각 병합 정렬로 정렬하고 병합한다. java.util.Arrays 패키지에서 배열을 정렬하는 클래스 메서드인 sort를 제공한다. 기본 자료형의 배열을 정렬하는 sort 메서드는 퀵 정렬 알고리즘을 개선한 것으로 안정적이진 않다. 클래스 객체 배열을 정렬하는 sort 메서드는 병합 정렬을 개선한..

가장 빠른 정렬 알고리즘 중 하나 피벗을 기준으로 피벗보다 작은 요소로 이루어진 부분과 피벗보다 큰 요소 이루어진 부분으로 나눔을 반복함으로써 최종적으로 정렬 된다. 즉 각 그룹에 대해 피벗 설정과 그룹 나눔을 반복하여 모든 그룹의 개수가 1이 되면 정렬을 마친다. 서로 이웃하지 않고 멀리 떨어져 있는 요소를 교환해야 하므로 안정적이지 않은 알고리즘이다. 시간 복잡도는 O(n log n) 정렬할 배열의 초깃값이나 피벗의 선택 방법에 따라 시간 복잡도가 증가하는 경우도 있다. 최악의 시간 복잡도는 O(n^2)이 된다. 배열을 두 그룹으로 나누기 피벗 이하의 요소를 배열 왼쪽으로 옮긴다. a[pl] >= x 가 성립할 때까지 pl을 오른쪽으로 스캔 피벗 이상의 요소를 배열 오른쪽으로 옮긴다. a[pr] pr..

단순 삽입 정렬의 장점은 살리고 단점은 보완하여 좀 더 빠르게 정렬하는 알고리즘 먼저 정렬할 배열의 요소를 그룹으로 나눠 각 그룹별로 단순 삽입 정렬을 수행하고, 그 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를 줄이는 방법 퀵 정렬이 고안되기 전까지 가장 빠른 알고리즘으로 알려져 있었다. 4칸만큼 떨어진 요소를 모아 그룹을 4개로 나누어 정렬하는 방법을 '4-정렬'이라고 한다. 4-정렬 → 2-정렬 → 1-정렬을 적용하면 정렬을 마치게 된다. 4-정렬, 2-정렬로 조금이라고 정렬에 가까운 상태로 만든 다음 마지막으로 단순 삽입 정렬을 수행하여 정렬을 마친다. 여러 개의 그룹으로 나누어 정렬하는 이유는 단순 삽입 정렬의 장점은 살리고 단점은 보완하기 위해서이다. 셸 정렬 과정에서 수행하는 각각의 정..

아직 정렬되지 않은 부분의 첫 번째 요소를 정렬된 열의 '알맞은 위치에 삽입'하는 작업을 n - 1회 반복하여 정렬하는 알고리즘 2번째 요소부터 선택하여 진행한다. 선택한 요소의 왼쪽에 이웃한 요소가 더 크면 그 값을 선택한 요소에 대입하고 앞으로 이동하면서 이 작업을 반복한다. 그러다가 선택한 요소 값 이하의 요소를 만나면 그 보다 앞쪽은 검사할 필요가 없으므로 해당 위치에 선택한 요소 값을 대입한다. 떨어져 있는 요소들이 서로 뒤바뀌지 않아 안정적인 알고리즘이다. 시간 복잡도는 O(n^2) 장점 : 정렬을 마쳤거나 정렬을 마친 상태에 가까우면 정렬 속도가 매우 빨라진다. 단점 : 삽입할 위치가 멀리 떨어져 있으면 이동(대입)해야 하는 횟수가 많아진다. 1234567891011//단순 삽입 정렬stat..

가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘 서로 떨어져 있는 요소를 교환하는 것이기 때문에 안정적이지 않다. 안정된 정렬이란 같은 값을 가진 요소의 순서가 정렬 전후에도 유지되는 것을 말한다. 안정되지 않은 알고리즘은 정렬 후에 같은 값의 요소의 순서가 바뀔 수도 있다. 시간 복잡도는 O(n^2) 단순 선택 정렬의 교환 과정 아직 정렬하지 않은 부분에서 가장 작은 키의 값(a[min])을 선택한다. a[min]과 아직 정렬하지 않은 부분의 첫 번째 요소를 교환한다. 1 2 3 4 5 6 7 8 9 10 11 // 단순 선택 정렬 static void selectionSort(int[] a, int n) { for (int i = 0; i

이웃한 두 요소의 대소 관계를 비교/교환을 반복하여 최종적으로 배열을 정렬시키는 알고리즘 6 4 3 7 1 9 8 먼저 오른쪽 끝에 있는 두 요소부터 비교/교환한다. 오름차순으로 정렬한다면 왼쪽 요소 값이 오른쪽 요소 값보다 클 때 교환한다. 그 다음 오른쪽에서 2, 3번째 요소를 비교/교환한다. 이 작업을 첫 번째 요소까지 반복한다. 길이가 n인 배열에서 n - 1회 비교/교환을 하면 가장 작은 요소가 왼쪽 끝으로 이동한다. 이런 하나의 사이클을 패스(pass)라고 하며, 첫 번째 패스가 끝나면 두 번째 패스는 왼쪽 끝으로 이동한 요소를 제외한 배열에 대해 비교/교환을 한다. 두 번째 패스의 비교 횟수는 첫 번째 패스보다 정렬한 요소가 하나 줄었기 때문에 1회 적은 n - 2회이다. 모든 정렬이 끝나려..