Smooth sort

 
 
 
Сообщения:1
Где можно найти реализацию Smooth sort на Java? Нашел на Гит Хабе реализацию, но не сортирует. Вот сам код
https://github.com/ChrisKitching/JavaExternalSort/blob/master/src/uk/ac/cam/cdk23/fjava/tick0/SmoothSort.java

Также переписал код с C# но тоже проблемы, зацикливается, может тут что-то не так?
public class Smooth {
    public static void main(String[] args) {
        String st[] = {"hello", "everyone", "it", "is", "me"};
        SmoothSort(st, st.length - 2);
        System.out.println(st[0]);
    }

     private static boolean IsAscending(String A, String B) {
        return (A.length() <= B.length());
        // return (StringType.StrCmp(A, B, false) <= 0);
    }

    private static void UP(int IA, int IB, int temp) {
        temp = IA;
        IA += IB + 1;
        IB = temp;
    }

    private static void DOWN(int IA, int IB, int temp) {
        temp = IB;
        IB = IA - IB - 1;
        IA = temp;
    }

    private static int q, r, p, b, c, r1, b1, c1;
    private static String[] A;

    private static void Sift() {
        int r0, r2, temp = 0;
        String t;
        r0 = r1;
        t = A[r0];

        while (b1 >= 3) {
            r2 = r1 - b1 + c1;

            if (!IsAscending(A[r1 - 1], A[r2])) {
                r2 = r1 - 1;
                DOWN(b1, c1, temp);
            }

            if (IsAscending(A[r2], t)) {
                b1 = 1;
            } else {
                A[r1] = A[r2];
                r1 = r2;
                DOWN(b1, c1, temp);
            }
        }
        if (r1 > r0)
            // if (Convert.ToBoolean(r1 - r0))
            A[r1] = t;
    }

    private static void Trinkle() {
        int p1, r2, r3, r0, temp = 0;
        String t;
        p1 = p;
        b1 = b;
        c1 = c;
        r0 = r1;
        t = A[r0];

        while (p1 > 0) {
            while ((p1 & 1) == 0) {
                p1 >>= 1;
                UP(b1, c1, temp);
            }

            r3 = r1 - b1;

            if ((p1 == 1) || IsAscending(A[r3], t)) {
                p1 = 0;
            } else {
                --p1;

                if (b1 == 1) {
                    A[r1] = A[r3];
                    r1 = r3;
                } else {
                    if (b1 >= 3) {
                        r2 = r1 - b1 + c1;

                        if (!IsAscending(A[r1 - 1], A[r2])) {
                            r2 = r1 - 1;
                            DOWN(b1, c1, temp);
                            p1 <<= 1;
                        }
                        if (IsAscending(A[r2], A[r3])) {
                            A[r1] = A[r3];
                            r1 = r3;
                        } else {
                            A[r1] = A[r2];
                            r1 = r2;
                            DOWN(b1, c1, temp);
                            p1 = 0;
                        }
                    }
                }
            }
        }
        if (r0 > r1)
            // if (Convert.ToBoolean(r0 - r1))
            A[r1] = t;

        Sift();
    }

    private static void SemiTrinkle() {
        String T;
        r1 = r - c;

        if (!IsAscending(A[r1], A[r])) {
            T = A[r];
            A[r] = A[r1];
            A[r1] = T;
            Trinkle();
        }
    }

    public static void SmoothSort(String[] Aarg, int N) {
        int temp = 0;
        A = Aarg;
        q = 1;
        r = 0;
        p = 1;
        b = 1;
        c = 1;

        while (q < N) {
            r1 = r;
            if ((p & 7) == 3) {
                b1 = b;
                c1 = c;
                Sift();
                p = (p + 1) >> 2;
                UP( b,  c,  temp);
                UP( b,  c,  temp);
            } else if ((p & 3) == 1) {
                if (q + c < N) {
                    b1 = b;
                    c1 = c;
                    Sift();
                } else {
                    Trinkle();
                }

                DOWN( b,  c,  temp);
                p <<= 1;

                while (b > 1) {
                    DOWN( b,  c,  temp);
                    p <<= 1;
                }

                ++p;
            }

            ++q;
            ++r;
        }

        r1 = r;
        Trinkle();

        while (q > 1) {
            --q;

            if (b == 1) {
                --r;
                --p;

                while ((p & 1) == 0) {
                    p >>= 1;
                    UP( b,  c,  temp);
                }
            } else {
                if (b >= 3) {
                    --p;
                    r = r - b + c;
                    if (p > 0)
                        SemiTrinkle();

                    DOWN( b,  c,  temp);
                    p = (p << 1) + 1;
                    r = r + c;
                    SemiTrinkle();
                    DOWN( b,  c,  temp);
                    p = (p << 1) + 1;
                }
            }
        }
    }
}

Здесь реализация на C# https://www.programmingalgorithms.com/algorithm/smooth-sort?lang=C%23
Изменен:12 мар 2018 14:51
 
Модераторы:alon4iknazicaTaky_
Сейчас эту тему просматривают:Нет