arrays - マージソートアルゴリズムを使用してその場でソートする方法は?

Question

質問が具体的すぎないことはわかっています。

私が望むのは、通常のマージソートをインプレースマージソート (または一定の余分なスペースオーバーヘッドを伴うマージソート) に変換する方法を教えてくれる人だけです。

私が（ネット上で）見つけることができるのは、「複雑すぎる」または「このテキストの範囲外」というページだけです。

インプレース (余分なスペースなし) をマージする既知の唯一の方法は、複雑すぎて実用的なプログラムにはなりません。（ここから撮影）

複雑すぎるとはいえ、マージソートをその場で行う方法の基本的な概念は何ですか?

score 161 · Accepted Answer

Knuth はこれを演習として残しました (Vol 3, 5.2.5)。インプレースマージソートが存在します。それらは慎重に実装する必要があります。

まず、ここで説明されているような単純なインプレースマージは適切なソリューションではありません。パフォーマンスをO(N ² )にダウングレードします。

アイデアは、マージの作業領域として残りを使用しながら、配列の一部をソートすることです。

たとえば、次のマージ関数のように。

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++);
}

配列を取り、xs2 つの並べ替えられたサブ配列はそれぞれ範囲[i, m)およびとして表されます[j, n)。作業領域はから始まりwます。ほとんどの教科書に記載されている標準のマージアルゴリズムと比較すると、このアルゴリズムは、並べ替えられたサブ配列と作業領域の間で内容を交換します。その結果、以前の作業領域にはマージされた並べ替えられた要素が含まれ、作業領域に格納されていた以前の要素は 2 つのサブ配列に移動されます。

ただし、満たさなければならない制約が 2 つあります。

作業域は、配列の境界内にある必要があります。つまり、境界外エラーを発生させることなく、交換される要素を保持するのに十分な大きさである必要があります。
作業領域は、2 つの並べ替えられた配列のいずれかとオーバーラップできます。ただし、マージされていない要素が上書きされないようにする必要があります。

このマージアルゴリズムが定義されているので、配列の半分を並べ替えることができるソリューションを想像するのは簡単です。次の問題は、以下に示すように、ワークエリアに格納された残りの未ソート部分をどのように処理するかです。

... unsorted 1/2 array ... | ... sorted 1/2 array ...

直観的なアイデアの 1 つは、作業領域の別の半分を再帰的に並べ替えることです。したがって、まだ並べ替えられていない要素は 1/4 だけです。

... unsorted 1/4 array ... | sorted 1/4 array B | sorted 1/2 array A ...

この段階での重要なポイントは、ソートされた 1/4 要素 B をソートされた 1/2 要素 A と遅かれ早かれマージする必要があるということです。

A と B をマージするのに十分な大きさの 1/4 要素のみを保持する作業領域が残っていますか? 残念ながら、そうではありません。

ただし、上記の 2 番目の制約は、マージされていない要素が上書きされないというマージシーケンスを保証できれば、作業領域をいずれかのサブ配列とオーバーラップするように配置することで、それを悪用できるというヒントを与えてくれます。

実際には、作業領域の後半をソートする代わりに、前半をソートし、次のように 2 つのソートされた配列の間に作業領域を置くことができます。

... sorted 1/4 array B | unsorted work area | ... sorted 1/2 array A ...

このセットアップは、サブアレイ A とオーバーラップする作業領域を効果的に配置します。「実用的なインプレースマージソート」。Nordic Journal of Computing、1996]。

したがって、残っている唯一のことは、上記のステップを繰り返すことです。これにより、作業領域が 1/2、1/4、1/8 から減少します。作業領域が十分に小さくなったら (たとえば、要素が 2 つしか残っていない場合)、このアルゴリズムを終了するには、自明な挿入ソートに切り替えます。

これは、この論文に基づいた ANSI C での実装です。

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 が以前に定義されている場所。

完全なソースコードはここにあり、詳細な説明はここにあります

ところで、このバージョンはより多くのスワップ操作を必要とするため、最速のマージソートではありません。私のテストによると、再帰ごとに余分なスペースを割り当てる標準バージョンよりも高速です。ただし、元の配列を事前に 2 倍にし、それをさらにマージするために使用する最適化バージョンよりも低速です。

score 63 · Accepted Answer

Including its "big result", this paper describes a couple of variants of in-place merge sort (PDF):

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.5514&rep=rep1&type=pdf

In-place sorting with fewer moves

Jyrki Katajainen, Tomi A. Pasanen

It is shown that an array of n elements can be sorted using O(1) extra space, O(n log n / log log n) element moves, and n log₂n + O(n log log n) comparisons. This is the first in-place sorting algorithm requiring o(n log n) moves in the worst case while guaranteeing O(n log n) comparisons, but due to the constant factors involved the algorithm is predominantly of theoretical interest.

I think this is relevant too. I have a printout of it lying around, passed on to me by a colleague, but I haven't read it. It seems to cover basic theory, but I'm not familiar enough with the topic to judge how comprehensively:

http://comjnl.oxfordjournals.org/cgi/content/abstract/38/8/681

Optimal Stable Merging

Antonios Symvonis

This paper shows how to stably merge two sequences A and B of sizes m and n, m ≤ n, respectively, with O(m+n) assignments, O(mlog(n/m+1)) comparisons and using only a constant amount of additional space. This result matches all known lower bounds...

score 13 · Accepted Answer

It really isn't easy or efficient, and I suggest you don't do it unless you really have to (and you probably don't have to unless this is homework since the applications of inplace merging are mostly theoretical). Can't you use quicksort instead? Quicksort will be faster anyway with a few simpler optimizations and its extra memory is O(log N).

Anyway, if you must do it then you must. Here's what I found: one and two. I'm not familiar with the inplace merge sort, but it seems like the basic idea is to use rotations to facilitate merging two arrays without using extra memory.

Note that this is slower even than the classic merge sort that's not inplace.

score 11 · Accepted Answer

The critical step is getting the merge itself to be in-place. It's not as difficult as those sources make out, but you lose something when you try.

Looking at one step of the merge:

[...list-sorted...|x...list-A...|y...list-B...]

We know that the sorted sequence is less than everything else, that x is less than everything else in A, and that y is less than everything else in B. In the case where x is less than or equal to y, you just move your pointer to the start of A on one. In the case where y is less than x, you've got to shuffle y past the whole of A to sorted. That last step is what makes this expensive (except in degenerate cases).

It's generally cheaper (especially when the arrays only actually contain single words per element, e.g., a pointer to a string or structure) to trade off some space for time and have a separate temporary array that you sort back and forth between.

score 3 · Accepted Answer

これは私の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--;
    }
  }
}

score -6 · Accepted Answer

次の手順を使用して、挿入ソートアルゴリズムを使用して、JAVAでマージソートのマージアルゴリズムをインプレースで試しました。
1) 2 つのソートされた配列が利用可能です。
2) 各配列の最初の値を比較します。最小値を最初の配列に配置します。
3) 挿入ソート (左から右へトラバース) を使用して、大きい方の値を 2 番目の配列に配置します。
4) 次に、最初の配列の 2 番目の値と 2 番目の配列の最初の値を再度比較し、同じことを行います。しかし、スワッピングが発生した場合、さらにアイテムを比較するのをスキップする手がかりがありますが、必要なのはスワッピングだけです。

ここでいくつかの最適化を行いました。挿入ソートでより少ない比較を維持します。
このソリューションで見つかった唯一の欠点は、2 番目の配列の配列要素をより大きく交換する必要があることです。

例えば）

最初___配列: 3、7、8、9

2 番目の配列: 1、2、4、5

次に、7, 8, 9 は、2 番目の配列を作成し、そのすべての要素を 1 つずつスワップ (左に 1 つ移動) して、自分自身を最後に配置します。

したがって、ここでの前提は、アイテムの交換は、2 つのアイテムの比較に比べて無視できるということです。

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;
}
}

arrays - マージソートアルゴリズムを使用してその場でソートする方法は?

10 に答える 10

Related

Reference