質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.61%

javaでTimSortをしたい

受付中

回答 0

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 925

kjfnfljnf

score 23

javaでTimSortアルゴリズムのプログラムを書いています。
insertionSortメソッドとmergeSortメソッドが正しく動くことは確認できていて、
timSortメソッド内で再帰プログラムを書きたいのですが、どのようなコードを書けば良いかわかりません。

insertionSort、またはmergeSortメソッドに
配列を入れると、正しくソートはしてくれますが、要素が多いと動きがとてつもなく遅くなります。
そこで、その2つのメソッドを利用したTimSortアルゴリズムを書きたいのですが、どのタイミングで何をどのメソッドに入れれば良いかが全く分かりません。

配列の長さが100だとすると、それを、50、25、12、という風に長さが10以下になるまではmergeSortを、
それ以降はinsertionSortを利用したいです。

public class Sorting
{
    ///////////////////////////////////////////////
    //  STEP 1 -- Make sorting methods generic
    ///////////////////////////////////////////////

    /**
     * Re-orders the contents given array using the insertion sort algorithm.
     * 
     * @param <E> Generic to store the different values.
     * @param data The array to be sorted.
     */
    public static <E extends Comparable<E>> void insertionSort(E[] data) 
    {
        E insert; // temporary variable to hold element to insert

        // loop over data.length - 1 elements
        for (int next = 0; next < data.length; next++) 
        { 
            insert = data[ next ]; // store value in current element
            int moveItem = next; // initialize location to place element

            while (moveItem > 0 && data[ moveItem - 1 ].compareTo(insert) > 0) 
            {           
                data[ moveItem ] = data[ moveItem - 1 ]; 
                moveItem--;
            } 

            data[ moveItem ] = insert; // place inserted element
        }
    }

    /**
     * Sorts passed data using Merge Sort by modifying the input array. 
     * 
     * @param <E> Generic to store the different values.
     * @param data The data to be sorted.
     */
    public static <E extends Comparable<E>> void mergeSort(E[] data)
    {
        mergeSortHelper(data, 0, data.length - 1);
    }

    /**
     * Recursive helper method for mergeSort.
     * 
     * @param <E> Generic to store the different values.
     * @param data The data in which the sub-array is located
     * @param left Lower index of the sub-array.
     * @param right Upper index of the sub-array.
     */
    private static <E extends Comparable<E>> void mergeSortHelper(E[] data, int left, int right)
    {
        //General Case: The sublist has at least one item in it.
        if ((right - left) >= 1)    
        {
            int middle1 = (left + right) / 2;
            int middle2 = middle1 + 1;

            mergeSortHelper(data, left, middle1);
            mergeSortHelper(data, middle2, right);

            merge(data, left, middle1, middle2, right);
        }
    }

    /**
     * Helper method for merge sort. Merges two sub-arrays into sorted order.
     *
     * @param <E> Generic to store the different values.
     * @param data The data in which the sub-arrays are located
     * @param left Lower index of first sub-array.
     * @param middle1 Upper index of first sub-array.
     * @param middle2 Lower index of second sub-array.
     * @param right Upper index of second sub-array.
     */
    @SuppressWarnings("unchecked")
    private static <E extends Comparable<E>> void merge(E[] data, int left, int middle1, int middle2, int right)
    {
        int leftIndex = left;                    // Local variables for tracking left and right
        int rightIndex = middle2;                // while merging.

        Object[] combined = new Object[data.length]; 

        int combinedIndex = left;               
        while (leftIndex <= middle1 && rightIndex <= right)
        {
            // Is the first item of the left subarray smaller?
            if (data[leftIndex].compareTo(data[rightIndex]) <= 0)
            {
                combined[combinedIndex++] = data[leftIndex++];
            }
            // Or is the first item in the right one smaller?
            else 
            {
                combined[combinedIndex++] = (E) (data[rightIndex++]);
            }
        }

        if (leftIndex == middle2)
        {
            while (rightIndex <= right)
            {
                combined[combinedIndex++] = data[rightIndex++];
            }
        }
        else
        {
            while (leftIndex <= middle1)
            {
                combined[combinedIndex++] = data[leftIndex++];
            }
        }
        for (int i = left; i <= right; i++)
        {
            data[i] = (E) (combined[i]);
        }        
    }


    ///////////////////////////////////////////////////////
    // STEP 2  - Refactor Insertion Sort
    //
    //Write the helper method described below and then 
    // simplify insertionSort to eliminate duplicate code
    ///////////////////////////////////////////////////////

    /**
     * insertionSortRange is a generic method that allows for
     * sorting a sub-range of Comparable array values using the 
     * insertion sort algorithm.  
     * 
     * Ranges are specified with the parameters left and right, 
     * which are inclusive.
     * 
     * @param <E> Generic to store the different values.
     * @param data  The array of data to sort
     * @param left  The index of the left-most position to sort
     * @param right The index of the right most position to sort
     */
    //Write the method header and body for insertionSortRange here
    public static <E extends Comparable<E>> void insertionSortRange(E[] data, int left, int right) 
    {
        E insert; // temporary variable to hold element to insert
        int leftPosi = left - 1;
        int rightPosi = right + 1;
        // loop over data.length - 1 elements
        for (int next = leftPosi; next < rightPosi; next++) 
        { 
            insert = data[ next ]; // store value in current element
            int moveItem = next; // initialize location to place element

            // shift items in the sorted part of the array to make room for next element
            // making sure we don't step off the front of the array
            while (moveItem > leftPosi && data[ moveItem - 1 ].compareTo(insert) > 0) 
            {           
                data[ moveItem ] = data[ moveItem - 1 ]; // shift element right one slot
                moveItem--;
            } 

            data[ moveItem ] = insert; // place inserted element
        }
    }


    //////////////////////////////////////////////////////
    // STEP 3 - Complete TimSort
    //////////////////////////////////////////////////////

    /**
     * timSort is a generic sorting method that sorts an array of Comparable
     * data using the TimSort algorithm.  Make sure this method is public so
     * that we can test it.
     * 
     * @param <E> Generic to store the different values.
     * @param data  The array of data to be sorted
     */
    //Write the method header for timSort here.  Just uncomment the body, do not edit it.

    public static <E extends Comparable<E>> void timSort(E[] data) 
    {
        timSortHelper(data, 0, data.length - 1);

    }


    /**
     * timSortHelper is a generic sorting method that sorts a sub-array array of Comparable
     * data using the TimSort algorithm.  This method should be public for testing purposes
     * but would normally be private.
     * 
     * Ranges are specified with the parameters left and right, 
     * which are inclusive.
     * 
     * @param <E> Generic to store the different values.
     * @param data  The array of data to sort
     * @param left  The index of the left-most position to sort
     * @param right The index of the right most position to sort
     */
    public static <E extends Comparable<E>> void timSortHelper(E[] data, int left, int right) 
    {
        //このメソッド内の仕事が分かりません。
    }
}

timSortHelper内をどのように書けば良いのでしょうか。
よろしくお願いします。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正の依頼

  • dice142

    2018/10/22 11:46

    「どのように書けばよいでしょうか」との質問ですが、ご自身でお書きになってますよね? どうなってほしいか、現状どうなっているのかを記載されると回答が得られやすいかと思います。

    キャンセル

  • dice142

    2018/10/22 12:57

    いや、コードを消すのではなくて、書いてみたコードでどうなるのかとか、結果はどうなって欲しいかとかそういう情報を追記していただきたかったのですが。

    キャンセル

  • 退会済みユーザー

    2018/10/23 22:36

    複数のユーザーから「やってほしいことだけを記載した丸投げの質問」という意見がありました
    「質問を編集する」ボタンから編集を行い、調査したこと・試したことを記入していただくと、回答が得られやすくなります。

まだ回答がついていません

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.61%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る