Рубрики

Java-программа для быстрой итеративной сортировки

// Java реализация итеративной быстрой сортировки

class IterativeQuickSort {

    void swap(int arr[], int i, int j)

    {

        int t = arr[i];

        arr[i] = arr[j];

        arr[j] = t;

    }

  

    / * Эта функция одинакова как в итеративной, так и в

       рекурсивный * /

    int partition(int arr[], int l, int h)

    {

        int x = arr[h];

        int i = (l - 1);

  

        for (int j = l; j <= h - 1; j++) {

            if (arr[j] <= x) {

                i++;

                // поменять местами arr [i] и arr [j]

                swap(arr, i, j);

            }

        }

        // поменять местами arr [i + 1] и arr [h]

        swap(arr, i + 1, h);

        return (i + 1);

    }

  

    // Сортировка arr [l..h] с использованием итеративной быстрой сортировки

    void QuickSort(int arr[], int l, int h)

    {

        // создаем вспомогательный стек

        int stack[] = new int[h - l + 1];

  

        // инициализировать вершину стека

        int top = -1;

  

        // помещаем начальные значения в стек

        stack[++top] = l;

        stack[++top] = h;

  

        // сохраняем элементы, пока стек не будет пустым

        while (top >= 0) {

            // поп ч и л

            h = stack[top--];

            l = stack[top--];

  

            // установить элемент поворота в правильное положение

            int p = partition(arr, l, h);

  

            // Если есть элементы на левой стороне оси,

            // затем сдвигаем левую сторону в стек

            if (p - 1 > l) {

                stack[++top] = l;

                stack[++top] = p - 1;

            }

  

            // Если есть элементы на правой стороне оси,

            // затем вставляем правую сторону в стек

            if (p + 1 < h) {

                stack[++top] = p + 1;

                stack[++top] = h;

            }

        }

    }

  

    // Утилита для печати содержимого arr

    void printArr(int arr[], int n)

    {

        int i;

        for (i = 0; i < n; ++i)

            System.out.print(arr[i] + " ");

    }

  

    // Код драйвера для проверки выше

    public static void main(String args[])

    {

        IterativeQuickSort ob = new IterativeQuickSort();

        int arr[] = { 4, 3, 5, 2, 1, 3, 2, 3 };

        ob.QuickSort(arr, 0, arr.length - 1);

        ob.printArr(arr, arr.length);

    }

}
/ * Этот код предоставлен Раджатом Мишрой * /

Выход:

1 2 2 3 3 3 4 5

Вышеупомянутые оптимизации для быстрой рекурсивной сортировки также могут быть применены к итерационной версии.

1) Процесс разбиения одинаков как в рекурсивном, так и итеративном. Те же методы для выбора оптимального центра также могут быть применены к итерационной версии.

Рекомендуемые посты:

Java-программа для быстрой итеративной сортировки

0.00 (0%) 0 votes