병합 정렬 알고리즘을 사용하여 내부 정렬하는 방법은 무엇입니까?
나는 그 질문이 너무 구체적이지 않다는 것을 압니다.
제가 원하는 것은 일반 병합 정렬을 인플레이스 병합 정렬(또는 공간 오버헤드가 일정한 병합 정렬)로 변환하는 방법을 알려주는 사람입니다.
(인터넷에서) 찾을 수 있는 것은 "너무 복잡하다" 또는 "이 텍스트의 범위를 벗어났다"는 페이지뿐입니다.
추가 공간 없이 인플레이스(in-place)로 병합할 수 있는 알려진 유일한 방법은 너무 복잡하여 실제 프로그램으로 축소할 수 없습니다.(여기서부터 시작)
너무 복잡하더라도 병합 정렬을 제자리에 만드는 방법의 기본 개념은 무엇입니까?
Knuth는 이것을 연습으로 남겼습니다(3권, 5.2.5).내부 병합 정렬이 있습니다.그들은 신중하게 구현되어야 합니다.
첫째, 여기에 설명된 것과 같은 단순한 내부 병합은 올바른 솔루션이 아닙니다.성능을 O(N2)로 다운그레이드합니다.
이 방법은 배열의 일부를 정렬하고 나머지는 병합을 위한 작업 영역으로 사용하는 것입니다.
예를 들어 다음 병합 함수와 같습니다.
void wmerge(Key* xs, int i, int m, int j, int n, int w) {
while (i < m && j < n)
swap(xs, w++, xs[i] < xs[j] ? i++ : j++);
while (i < m)
swap(xs, w++, i++);
while (j < n)
swap(xs, w++, j++);
}
이 열이필니다합요배▁array▁the로 되어 있습니다.xs된 두 의 하위 정 된 두 개 하 범 가 범 표 니 됩 다 시 로 위 주 arrays 렬 위 의 ▁ranges 다 니 ▁are ▁the ▁as ▁represent 됩 ▁sorted 표 시[i, m)그리고.[j, n)각각 다음과 같다.작업 영역은 다음에서 시작합니다.w대부분의 교과서에서 제공되는 표준 병합 알고리즘과 비교하여, 이 알고리즘은 정렬된 하위 배열과 작업 영역 간에 내용을 교환합니다.따라서 이전 작업 영역에는 병합된 정렬된 요소가 포함되고 작업 영역에 저장된 이전 요소는 두 개의 하위 배열로 이동됩니다.
그러나 다음 두 가지 제약 조건을 충족해야 합니다.
- 작업 영역은 배열의 범위 내에 있어야 합니다.즉, 경계 밖 오류를 발생시키지 않고 교환된 요소를 보관할 수 있을 정도로 커야 합니다.
- 작업 영역은 정렬된 두 배열 중 하나와 겹칠 수 있지만 병합되지 않은 요소를 덮어쓰지 않아야 합니다.
이 병합 알고리즘을 정의하면 어레이의 절반을 정렬할 수 있는 솔루션을 쉽게 상상할 수 있습니다.다음 질문은 아래와 같이 작업 영역에 저장된 나머지 정렬되지 않은 부품을 처리하는 방법입니다.
... unsorted 1/2 array ... | ... sorted 1/2 array ...
한 가지 직관적인 아이디어는 작업 영역의 다른 절반을 재귀적으로 정렬하는 것입니다. 따라서 아직 1/4의 요소만 정렬되지 않았습니다.
... unsorted 1/4 array ... | sorted 1/4 array B | sorted 1/2 array A ...
이 단계의 핵심은 우리가 조만간 정렬된 1/4 요소 B를 정렬된 1/2 요소 A와 병합해야 한다는 것입니다.
4분의 1의 요소만 수용하는 작업 영역이 A와 B를 병합할 수 있는 크기로 남아 있습니까?불행하게도, 그렇지 않습니다.
그러나 위에서 언급한 두 번째 제약 조건은 병합되지 않은 요소가 덮어쓰기되지 않도록 병합 시퀀스를 보장할 수 있는 경우 작업 영역을 두 하위 배열 중 하나와 겹치도록 배열하여 이를 이용할 수 있다는 힌트를 제공합니다.
실제로 작업 영역의 후반부를 정렬하는 대신 전반부를 정렬하고 다음과 같이 정렬된 두 배열 사이에 작업 영역을 배치할 수 있습니다.
... sorted 1/4 array B | unsorted work area | ... sorted 1/2 array A ...
이 설정은 하위 배열 A와 작업 영역 겹침을 효과적으로 배열합니다.이 아이디어는 [Jyrki Katajainen, Tomi Pasanen, Jukka Teuhola]에서 제안되었습니다.''실용적인 인플레이스 병합 정렬''Nordic Journal of Computing, 1996].
따라서 작업 영역이 1/2, 1/4, 1/8에서 감소하는 위의 단계를 반복하는 것만 남았습니다. … 작업 영역이 충분히 작아지면(예: 두 개의 요소만 남아 있음), 이 알고리즘을 종료하기 위해 사소한 삽입 정렬로 전환할 수 있습니다.
다음은 본 논문을 기반으로 한 ANSIC의 구현입니다.
void imsort(Key* xs, int l, int u);
void swap(Key* xs, int i, int j) {
Key tmp = xs[i]; xs[i] = xs[j]; xs[j] = tmp;
}
/*
* sort xs[l, u), and put result to working area w.
* constraint, len(w) == u - l
*/
void wsort(Key* xs, int l, int u, int w) {
int m;
if (u - l > 1) {
m = l + (u - l) / 2;
imsort(xs, l, m);
imsort(xs, m, u);
wmerge(xs, l, m, m, u, w);
}
else
while (l < u)
swap(xs, l++, w++);
}
void imsort(Key* xs, int l, int u) {
int m, n, w;
if (u - l > 1) {
m = l + (u - l) / 2;
w = l + u - m;
wsort(xs, l, m, w); /* the last half contains sorted elements */
while (w - l > 2) {
n = w;
w = l + (n - l + 1) / 2;
wsort(xs, w, n, l); /* the first half of the previous working area contains sorted elements */
wmerge(xs, l, l + n - w, n, u, w);
}
for (n = w; n > l; --n) /*switch to insertion sort*/
for (m = n; m < u && xs[m] < xs[m-1]; ++m)
swap(xs, m, m - 1);
}
}
여기서 wmerge는 이전에 정의되었습니다.
전체 소스 코드는 여기에서 찾을 수 있으며 자세한 설명은 여기에서 찾을 수 있습니다.
그런데 이 버전은 스왑 작업이 더 필요하기 때문에 가장 빠른 병합 정렬이 아닙니다.제가 테스트한 바로는 재귀할 때마다 추가 공간을 할당하는 표준 버전보다 빠릅니다.그러나 기존 어레이를 미리 두 배로 늘리고 추가 병합에 사용하는 최적화된 버전보다 느립니다.
이 문서에서는 "큰 결과"를 비롯하여 다음과 같은 몇 가지 변형된 인플레이스 병합 정렬(PDF)에 대해 설명합니다.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.5514&rep=rep1&type=pdf
이동 횟수가 적은 인플레이스 정렬
Jyrki Katajainen, Tomi A.파사넨
O(1) 추가 공간, O(n log n / log n) 요소 이동, n log2 n + O(n log n) 비교를 사용하여 n개 요소의 배열을 정렬할 수 있는 것으로 나타났습니다.이것은 O(n log n) 비교를 보장하면서 최악의 경우 o(n log n) 이동을 필요로 하는 최초의 인플레이스 정렬 알고리즘이지만, 관련된 상수 요인 때문에 알고리듬은 주로 이론적 관심사입니다.
저는 이것도 관련이 있다고 생각합니다.저는 그것의 인쇄물을 동료가 저에게 건네주었지만, 읽지는 않았습니다.기본 이론을 다루는 것처럼 보이지만, 저는 얼마나 포괄적으로 다음과 같은 주제를 판단할 만큼 충분히 친숙하지 않습니다.
http://comjnl.oxfordjournals.org/cgi/content/abstract/38/8/681
최적의 안정적 병합
안토니오스 심보니스
이 논문은 크기가 각각 m과 n, m ≤ n인 두 시퀀스 A와 B를 O(m+n) 할당, O(mllog(n/m+1) 비교와 일정한 양의 추가 공간만 사용하여 안정적으로 병합하는 방법을 보여줍니다.이 결과는 알려진 모든 하한과 일치합니다...
그것은 정말로 쉽지도 않고 효율적이지도 않으며, 저는 당신이 꼭 해야만 하는 경우가 아니라면 하지 않는 것을 제안합니다(그리고 이것이 숙제가 아니라면 아마도 그럴 필요가 없을 것입니다. 왜냐하면 인플레이스 병합의 적용은 대부분 이론적이기 때문입니다.당신은 대신 퀵소트를 사용할 수 없나요?Quicksort는 몇 가지 간단한 최적화를 통해 더 빨라질 것이며 추가 메모리는 O(log N)입니다.
어쨌든, 만약 당신이 그것을 해야 한다면 당신은 해야 합니다.제가 발견한 것은 하나와 둘입니다.인플레이스 병합 정렬에 대해 잘 모르지만, 기본적인 아이디어는 회전을 사용하여 추가 메모리를 사용하지 않고 두 어레이를 쉽게 병합하는 것입니다.
이 속도는 기존에 없는 병합 정렬보다 느립니다.
중요한 단계는 병합 자체를 제자리에 두는 것입니다.그 출처들이 밝혀내는 것만큼 어렵지는 않지만, 시도할 때 무언가를 잃게 됩니다.
병합의 한 단계를 살펴보면 다음과 같습니다.
[...list-sorted...|x...list-A...|y...list-B...]
우리는 정렬된 시퀀스가 다른 모든 것보다 작다는 것, x가 A의 다른 모든 것보다 작다는 것, y가 B의 다른 모든 것보다 작다는 것을 알고 있습니다.x가 y보다 작거나 같을 경우 포인터를 1의 A 시작 부분으로 이동하면 됩니다.y가 x보다 작은 경우, 정렬하려면 A 전체를 셔플로 통과해야 합니다.그 마지막 단계가 이것을 비싸게 만드는 것입니다(퇴화된 경우 제외).
일반적으로 (특히 배열에 실제로는 문자열이나 구조체에 대한 포인터와 같은 요소당 단일 단어만 포함되어 있는 경우) 시간에 따라 공간을 교환하고 앞뒤로 정렬하는 별도의 임시 배열을 갖는 것이 더 저렴합니다.
C에서 버퍼리스 병합 정렬의 예입니다.
#define SWAP(type, a, b) \
do { type t=(a);(a)=(b);(b)=t; } while (0)
static void reverse_(int* a, int* b)
{
for ( --b; a < b; a++, b-- )
SWAP(int, *a, *b);
}
static int* rotate_(int* a, int* b, int* c)
/* swap the sequence [a,b) with [b,c). */
{
if (a != b && b != c)
{
reverse_(a, b);
reverse_(b, c);
reverse_(a, c);
}
return a + (c - b);
}
static int* lower_bound_(int* a, int* b, const int key)
/* find first element not less than @p key in sorted sequence or end of
* sequence (@p b) if not found. */
{
int i;
for ( i = b-a; i != 0; i /= 2 )
{
int* mid = a + i/2;
if (*mid < key)
a = mid + 1, i--;
}
return a;
}
static int* upper_bound_(int* a, int* b, const int key)
/* find first element greater than @p key in sorted sequence or end of
* sequence (@p b) if not found. */
{
int i;
for ( i = b-a; i != 0; i /= 2 )
{
int* mid = a + i/2;
if (*mid <= key)
a = mid + 1, i--;
}
return a;
}
static void ip_merge_(int* a, int* b, int* c)
/* inplace merge. */
{
int n1 = b - a;
int n2 = c - b;
if (n1 == 0 || n2 == 0)
return;
if (n1 == 1 && n2 == 1)
{
if (*b < *a)
SWAP(int, *a, *b);
}
else
{
int* p, * q;
if (n1 <= n2)
p = upper_bound_(a, b, *(q = b+n2/2));
else
q = lower_bound_(b, c, *(p = a+n1/2));
b = rotate_(p, b, q);
ip_merge_(a, p, b);
ip_merge_(b, q, c);
}
}
void mergesort(int* v, int n)
{
if (n > 1)
{
int h = n/2;
mergesort(v, h); mergesort(v+h, n-h);
ip_merge_(v, v+h, v+n);
}
}
적응형 병합 정렬(최적화)의 예입니다.
모든 크기의 보조 버퍼를 사용할 수 있을 때(추가 메모리 없이도 작동) 병합을 가속화하기 위해 지원 코드와 수정 사항을 추가합니다.순방향 및 역방향 병합, 링 회전, 작은 시퀀스 병합 및 정렬, 반복 병합 정렬을 사용합니다.
#include <stdlib.h>
#include <string.h>
static int* copy_(const int* a, const int* b, int* out)
{
int count = b - a;
if (a != out)
memcpy(out, a, count*sizeof(int));
return out + count;
}
static int* copy_backward_(const int* a, const int* b, int* out)
{
int count = b - a;
if (b != out)
memmove(out - count, a, count*sizeof(int));
return out - count;
}
static int* merge_(const int* a1, const int* b1, const int* a2,
const int* b2, int* out)
{
while ( a1 != b1 && a2 != b2 )
*out++ = (*a1 <= *a2) ? *a1++ : *a2++;
return copy_(a2, b2, copy_(a1, b1, out));
}
static int* merge_backward_(const int* a1, const int* b1,
const int* a2, const int* b2, int* out)
{
while ( a1 != b1 && a2 != b2 )
*--out = (*(b1-1) > *(b2-1)) ? *--b1 : *--b2;
return copy_backward_(a1, b1, copy_backward_(a2, b2, out));
}
static unsigned int gcd_(unsigned int m, unsigned int n)
{
while ( n != 0 )
{
unsigned int t = m % n;
m = n;
n = t;
}
return m;
}
static void rotate_inner_(const int length, const int stride,
int* first, int* last)
{
int* p, * next = first, x = *first;
while ( 1 )
{
p = next;
if ((next += stride) >= last)
next -= length;
if (next == first)
break;
*p = *next;
}
*p = x;
}
static int* rotate_(int* a, int* b, int* c)
/* swap the sequence [a,b) with [b,c). */
{
if (a != b && b != c)
{
int n1 = c - a;
int n2 = b - a;
int* i = a;
int* j = a + gcd_(n1, n2);
for ( ; i != j; i++ )
rotate_inner_(n1, n2, i, c);
}
return a + (c - b);
}
static void ip_merge_small_(int* a, int* b, int* c)
/* inplace merge.
* @note faster for small sequences. */
{
while ( a != b && b != c )
if (*a <= *b)
a++;
else
{
int* p = b+1;
while ( p != c && *p < *a )
p++;
rotate_(a, b, p);
b = p;
}
}
static void ip_merge_(int* a, int* b, int* c, int* t, const int ts)
/* inplace merge.
* @note works with or without additional memory. */
{
int n1 = b - a;
int n2 = c - b;
if (n1 <= n2 && n1 <= ts)
{
merge_(t, copy_(a, b, t), b, c, a);
}
else if (n2 <= ts)
{
merge_backward_(a, b, t, copy_(b, c, t), c);
}
/* merge without buffer. */
else if (n1 + n2 < 48)
{
ip_merge_small_(a, b, c);
}
else
{
int* p, * q;
if (n1 <= n2)
p = upper_bound_(a, b, *(q = b+n2/2));
else
q = lower_bound_(b, c, *(p = a+n1/2));
b = rotate_(p, b, q);
ip_merge_(a, p, b, t, ts);
ip_merge_(b, q, c, t, ts);
}
}
static void ip_merge_chunk_(const int cs, int* a, int* b, int* t,
const int ts)
{
int* p = a + cs*2;
for ( ; p <= b; a = p, p += cs*2 )
ip_merge_(a, a+cs, p, t, ts);
if (a+cs < b)
ip_merge_(a, a+cs, b, t, ts);
}
static void smallsort_(int* a, int* b)
/* insertion sort.
* @note any stable sort with low setup cost will do. */
{
int* p, * q;
for ( p = a+1; p < b; p++ )
{
int x = *p;
for ( q = p; a < q && x < *(q-1); q-- )
*q = *(q-1);
*q = x;
}
}
static void smallsort_chunk_(const int cs, int* a, int* b)
{
int* p = a + cs;
for ( ; p <= b; a = p, p += cs )
smallsort_(a, p);
smallsort_(a, b);
}
static void mergesort_lower_(int* v, int n, int* t, const int ts)
{
int cs = 16;
smallsort_chunk_(cs, v, v+n);
for ( ; cs < n; cs *= 2 )
ip_merge_chunk_(cs, v, v+n, t, ts);
}
static void* get_buffer_(int size, int* final)
{
void* p = NULL;
while ( size != 0 && (p = malloc(size)) == NULL )
size /= 2;
*final = size;
return p;
}
void mergesort(int* v, int n)
{
/* @note buffer size may be in the range [0,(n+1)/2]. */
int request = (n+1)/2 * sizeof(int);
int actual;
int* t = (int*) get_buffer_(request, &actual);
/* @note allocation failure okay. */
int tsize = actual / sizeof(int);
mergesort_lower_(v, n, t, tsize);
free(t);
}
이 답변에는 Bing-Chao Huang과 Michael A의 Practical In-Place Merge 논문에 설명된 알고리듬을 구현하는 코드 예제가 있습니다.랭스턴.자세한 내용을 이해할 수 없다는 것은 인정해야 하지만 병합 단계의 주어진 복잡성은 O(n)입니다.
실제적인 관점에서 볼 때, 순수한 인플레이스 구현이 실제 시나리오에서 더 나은 성능을 발휘하지 못한다는 증거가 있습니다.예를 들어 C++ 표준은 std::inplace_merge를 정의하며, 이는 이름이 임플레이스 병합 작업을 의미하는 것과 같습니다.
C++ 라이브러리가 일반적으로 매우 잘 최적화되어 있다고 가정하면 어떻게 구현되는지 보는 것이 흥미롭습니다.
libstdc++(GCC 코드 베이스의 일부): std::inplace_merge
이 구현은 __inplace_merge에 위임하며, 임시 버퍼를 할당하여 문제를 회피합니다.
typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
_TmpBuf __buf(__first, __len1 + __len2);
if (__buf.begin() == 0)
std::__merge_without_buffer
(__first, __middle, __last, __len1, __len2, __comp);
else
std::__merge_adaptive
(__first, __middle, __last, __len1, __len2, __buf.begin(),
_DistanceType(__buf.size()), __comp);
그렇지 않으면 구현(__merge_without_buffer)으로 되돌아갑니다. 이 구현에는 추가 메모리가 필요하지 않지만 O(n) 시간 내에 더 이상 실행되지 않습니다.
libc++(Clang 코드 베이스의 일부): std::inplace_merge
비슷해 보입니다.버퍼 할당을 시도하는 함수에 위임합니다.충분한 요소를 확보했는지 여부에 따라 구현을 선택합니다.상수 메모리 폴백 함수를 __buffered_inplace_merge라고 합니다.
Fallback도 O(n) 시간일 수 있지만, 중요한 것은 임시 메모리를 사용할 수 있는 경우 구현을 사용하지 않는다는 것입니다.
C++ 표준은 필요한 복잡성을 O(n)에서 O(N log N)로 낮춤으로써 구현이 이 접근 방식을 선택할 수 있는 자유를 명시적으로 제공합니다.
복잡성: 충분한 추가 메모리를 사용할 수 있는 경우 정확히 N-1 비교입니다.메모리가 부족하면 O(N 로그 N) 비교를 수행합니다.
물론, 이것은 O(n) 시간의 일정한 공간 인플레이스 병합을 절대 사용해서는 안 된다는 증거로 받아들일 수 없습니다.반면에, 만약 그것이 더 빠르다면, 최적화된 C++ 라이브러리는 아마도 그러한 유형의 구현으로 전환될 것입니다.
이것은 내 C 버전입니다.
void mergesort(int *a, int len) {
int temp, listsize, xsize;
for (listsize = 1; listsize <= len; listsize*=2) {
for (int i = 0, j = listsize; (j+listsize) <= len; i += (listsize*2), j += (listsize*2)) {
merge(& a[i], listsize, listsize);
}
}
listsize /= 2;
xsize = len % listsize;
if (xsize > 1)
mergesort(& a[len-xsize], xsize);
merge(a, listsize, xsize);
}
void merge(int *a, int sizei, int sizej) {
int temp;
int ii = 0;
int ji = sizei;
int flength = sizei+sizej;
for (int f = 0; f < (flength-1); f++) {
if (sizei == 0 || sizej == 0)
break;
if (a[ii] < a[ji]) {
ii++;
sizei--;
}
else {
temp = a[ji];
for (int z = (ji-1); z >= ii; z--)
a[z+1] = a[z];
ii++;
a[f] = temp;
ji++;
sizej--;
}
}
}
제가 게임에 늦었다는 것은 알지만, 여기 제가 어제 쓴 해결책이 있습니다.저는 이것을 다른 곳에도 게시했지만, 이것은 SO에서 가장 인기 있는 병합 스레드인 것 같습니다.저는 이 알고리즘이 다른 곳에 게시된 것을 본 적이 없기 때문에, 이것이 몇몇 사람들에게 도움이 되기를 바랍니다.
이 알고리즘은 이해할 수 있도록 가장 간단한 형태로 되어 있습니다.추가 속도를 위해 크게 조정할 수 있습니다.평균 시간 복잡도는 안정적인 인플레이스 어레이 병합의 경우 O(n.log₂n)이고 전체 정렬의 경우 O(n.(log₂n)²입니다.
// Stable Merge In Place Sort
//
//
// The following code is written to illustrate the base algorithm. A good
// number of optimizations can be applied to boost its overall speed
// For all its simplicity, it does still perform somewhat decently.
// Average case time complexity appears to be: O(n.(log₂n)²)
#include <stddef.h>
#include <stdio.h>
#define swap(x, y) (t=(x), (x)=(y), (y)=t)
// Both sorted sub-arrays must be adjacent in 'a'
// Assumes that both 'an' and 'bn' are always non-zero
// 'an' is the length of the first sorted section in 'a', referred to as A
// 'bn' is the length of the second sorted section in 'a', referred to as B
static void
merge_inplace(int A[], size_t an, size_t bn)
{
int t, *B = &A[an];
size_t pa, pb; // Swap partition pointers within A and B
// Find the portion to swap. We're looking for how much from the
// start of B can swap with the end of A, such that every element
// in A is less than or equal to any element in B. This is quite
// simple when both sub-arrays come at us pre-sorted
for(pa = an, pb = 0; pa>0 && pb<bn && B[pb] < A[pa-1]; pa--, pb++);
// Now swap last part of A with first part of B according to the
// indicies we found
for (size_t index=pa; index < an; index++)
swap(A[index], B[index-pa]);
// Now merge the two sub-array pairings. We need to check that either array
// didn't wholly swap out the other and cause the remaining portion to be zero
if (pa>0 && (an-pa)>0)
merge_inplace(A, pa, an-pa);
if (pb>0 && (bn-pb)>0)
merge_inplace(B, pb, bn-pb);
} // merge_inplace
// Implements a recursive merge-sort algorithm with an optional
// insertion sort for when the splits get too small. 'n' must
// ALWAYS be 2 or more. It enforces this when calling itself
static void
merge_sort(int a[], size_t n)
{
size_t m = n/2;
// Sort first and second halves only if the target 'n' will be > 1
if (m > 1)
merge_sort(a, m);
if ((n-m)>1)
merge_sort(a+m, n-m);
// Now merge the two sorted sub-arrays together. We know that since
// n > 1, then both m and n-m MUST be non-zero, and so we will never
// violate the condition of not passing in zero length sub-arrays
merge_inplace(a, m, n-m);
} // merge_sort
// Print an array */
static void
print_array(int a[], size_t size)
{
if (size > 0) {
printf("%d", a[0]);
for (size_t i = 1; i < size; i++)
printf(" %d", a[i]);
}
printf("\n");
} // print_array
// Test driver
int
main()
{
int a[] = { 17, 3, 16, 5, 14, 8, 10, 7, 15, 1, 13, 4, 9, 12, 11, 6, 2 };
size_t n = sizeof(a) / sizeof(a[0]);
merge_sort(a, n);
print_array(a, n);
return 0;
} // main
C++ 표준:: inplace_merge를 활용하여 inplace 병합 정렬을 다음과 같이 구현할 수 있습니다.
template< class _Type >
inline void merge_sort_inplace(_Type* src, size_t l, size_t r)
{
if (r <= l) return;
size_t m = l + ( r - l ) / 2; // computes the average without overflow
merge_sort_inplace(src, l, m);
merge_sort_inplace(src, m + 1, r);
std::inplace_merge(src + l, src + m + 1, src + r + 1);
}
병렬 구현을 포함한 더 많은 정렬 알고리즘은 오픈 소스이며 무료인 https://github.com/DragonSpit/ParallelAlgorithms repo에서 사용할 수 있습니다.
저는 삽입 정렬 알고리즘을 사용하여 JAVA에서 병합 정렬을 위한 자리 병합 알고리즘을 다음 단계를 사용하여 시도했습니다.
두 개의 정렬된 배열을 사용할 수 있습니다.
각 배열의 첫 번째 값을 비교하고 가장 작은 값을 첫 번째 배열에 넣습니다.
삽입 정렬(왼쪽에서 오른쪽으로 이동)을 사용하여 큰 값을 두 번째 배열에 배치합니다.
그런 다음 첫 번째 배열의 두 번째 값과 두 번째 배열의 첫 번째 값을 다시 비교하고 동일하게 수행합니다.그러나 스와핑이 발생하면 추가 항목을 비교하는 건너뛰기에 대한 단서가 있지만, 스와핑만 필요합니다.
저는 삽입 정렬에서 비교를 덜 유지하기 위해 여기서 약간의 최적화를 만들었습니다.
이 솔루션의 유일한 단점은 두 번째 어레이에서 어레이 요소를 더 많이 스와핑해야 한다는 것입니다.
예)
첫 번째__배열: 3, 7, 8, 9
두 번째 배열: 1, 2, 4, 5
그런 다음 7, 8, 9는 두 번째 배열을 만들어 모든 요소를 매번 하나씩 교환(왼쪽으로 이동)하여 마지막 배열에 자신을 배치합니다.
따라서 여기서의 가정은 두 항목을 비교하는 것에 비해 항목을 교환하는 것은 무시할 수 있습니다.
https://github.com/skanagavelu/algorithams/blob/master/src/sorting/MergeSort.java
package sorting;
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) {
int[] array = { 5, 6, 10, 3, 9, 2, 12, 1, 8, 7 };
mergeSort(array, 0, array.length -1);
System.out.println(Arrays.toString(array));
int[] array1 = {4, 7, 2};
System.out.println(Arrays.toString(array1));
mergeSort(array1, 0, array1.length -1);
System.out.println(Arrays.toString(array1));
System.out.println("\n\n");
int[] array2 = {4, 7, 9};
System.out.println(Arrays.toString(array2));
mergeSort(array2, 0, array2.length -1);
System.out.println(Arrays.toString(array2));
System.out.println("\n\n");
int[] array3 = {4, 7, 5};
System.out.println(Arrays.toString(array3));
mergeSort(array3, 0, array3.length -1);
System.out.println(Arrays.toString(array3));
System.out.println("\n\n");
int[] array4 = {7, 4, 2};
System.out.println(Arrays.toString(array4));
mergeSort(array4, 0, array4.length -1);
System.out.println(Arrays.toString(array4));
System.out.println("\n\n");
int[] array5 = {7, 4, 9};
System.out.println(Arrays.toString(array5));
mergeSort(array5, 0, array5.length -1);
System.out.println(Arrays.toString(array5));
System.out.println("\n\n");
int[] array6 = {7, 4, 5};
System.out.println(Arrays.toString(array6));
mergeSort(array6, 0, array6.length -1);
System.out.println(Arrays.toString(array6));
System.out.println("\n\n");
//Handling array of size two
int[] array7 = {7, 4};
System.out.println(Arrays.toString(array7));
mergeSort(array7, 0, array7.length -1);
System.out.println(Arrays.toString(array7));
System.out.println("\n\n");
int input1[] = {1};
int input2[] = {4,2};
int input3[] = {6,2,9};
int input4[] = {6,-1,10,4,11,14,19,12,18};
System.out.println(Arrays.toString(input1));
mergeSort(input1, 0, input1.length-1);
System.out.println(Arrays.toString(input1));
System.out.println("\n\n");
System.out.println(Arrays.toString(input2));
mergeSort(input2, 0, input2.length-1);
System.out.println(Arrays.toString(input2));
System.out.println("\n\n");
System.out.println(Arrays.toString(input3));
mergeSort(input3, 0, input3.length-1);
System.out.println(Arrays.toString(input3));
System.out.println("\n\n");
System.out.println(Arrays.toString(input4));
mergeSort(input4, 0, input4.length-1);
System.out.println(Arrays.toString(input4));
System.out.println("\n\n");
}
private static void mergeSort(int[] array, int p, int r) {
//Both below mid finding is fine.
int mid = (r - p)/2 + p;
int mid1 = (r + p)/2;
if(mid != mid1) {
System.out.println(" Mid is mismatching:" + mid + "/" + mid1+ " for p:"+p+" r:"+r);
}
if(p < r) {
mergeSort(array, p, mid);
mergeSort(array, mid+1, r);
// merge(array, p, mid, r);
inPlaceMerge(array, p, mid, r);
}
}
//Regular merge
private static void merge(int[] array, int p, int mid, int r) {
int lengthOfLeftArray = mid - p + 1; // This is important to add +1.
int lengthOfRightArray = r - mid;
int[] left = new int[lengthOfLeftArray];
int[] right = new int[lengthOfRightArray];
for(int i = p, j = 0; i <= mid; ){
left[j++] = array[i++];
}
for(int i = mid + 1, j = 0; i <= r; ){
right[j++] = array[i++];
}
int i = 0, j = 0;
for(; i < left.length && j < right.length; ) {
if(left[i] < right[j]){
array[p++] = left[i++];
} else {
array[p++] = right[j++];
}
}
while(j < right.length){
array[p++] = right[j++];
}
while(i < left.length){
array[p++] = left[i++];
}
}
//InPlaceMerge no extra array
private static void inPlaceMerge(int[] array, int p, int mid, int r) {
int secondArrayStart = mid+1;
int prevPlaced = mid+1;
int q = mid+1;
while(p < mid+1 && q <= r){
boolean swapped = false;
if(array[p] > array[q]) {
swap(array, p, q);
swapped = true;
}
if(q != secondArrayStart && array[p] > array[secondArrayStart]) {
swap(array, p, secondArrayStart);
swapped = true;
}
//Check swapped value is in right place of second sorted array
if(swapped && secondArrayStart+1 <= r && array[secondArrayStart+1] < array[secondArrayStart]) {
prevPlaced = placeInOrder(array, secondArrayStart, prevPlaced);
}
p++;
if(q < r) { //q+1 <= r) {
q++;
}
}
}
private static int placeInOrder(int[] array, int secondArrayStart, int prevPlaced) {
int i = secondArrayStart;
for(; i < array.length; i++) {
//Simply swap till the prevPlaced position
if(secondArrayStart < prevPlaced) {
swap(array, secondArrayStart, secondArrayStart+1);
secondArrayStart++;
continue;
}
if(array[i] < array[secondArrayStart]) {
swap(array, i, secondArrayStart);
secondArrayStart++;
} else if(i != secondArrayStart && array[i] > array[secondArrayStart]){
break;
}
}
return secondArrayStart;
}
private static void swap(int[] array, int m, int n){
int temp = array[m];
array[m] = array[n];
array[n] = temp;
}
}
언급URL : https://stackoverflow.com/questions/2571049/how-to-sort-in-place-using-the-merge-sort-algorithm
'programing' 카테고리의 다른 글
| 루비 모듈에서 인스턴스 메소드를 포함하지 않고 호출할 수 있습니까? (0) | 2023.06.03 |
|---|---|
| LIMIT/OFFset을 사용하여 쿼리 실행 및 총 행 수 가져오기 (0) | 2023.05.29 |
| 딜러들이 신속하게? (0) | 2023.05.29 |
| eclipse.ini -vm 옵션을 설정하려면 어떻게 해야 합니까? (0) | 2023.05.29 |
| Postgre 상태 확인 방법SQL 서버 Mac OS X (0) | 2023.05.29 |