Рубрики

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

По несортированному массиву отсортировать по массиву. Вам разрешено делать только следующую операцию над массивом.

flip(arr, i): Reverse array from 0 to i 

/ * Java программа для сортировки массива с использованием блиновой сортировки * /

import java.io.*;

  

class PancakeSort {

  

    / * Обращает arr [0..i] * /

    static void flip(int arr[], int i)

    {

        int temp, start = 0;

        while (start < i) {

            temp = arr[start];

            arr[start] = arr[i];

            arr[i] = temp;

            start++;

            i--;

        }

    }

  

    / * Возвращает индекс максимального элемента в arr [0..n-1] * /

    static int findMax(int arr[], int n)

    {

        int mi, i;

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

            if (arr[i] > arr[mi])

                mi = i;

        return mi;

    }

  

    // Основная функция, которая сортирует данный массив с помощью flip

    // операции

    static int pancakeSort(int arr[], int n)

    {

        // Начать с полного массива и один за другим

        // уменьшить текущий размер на один

        for (int curr_size = n; curr_size > 1; --curr_size) {

            // Найти индекс максимального элемента в

            // arr [0..curr_size-1]

            int mi = findMax(arr, curr_size);

  

            // Переместить максимальный элемент в конец текущего

            // массив, если он еще не в конце

            if (mi != curr_size - 1) {

                // Чтобы двигаться в конце, первый ход максимум

                // номер в начало

                flip(arr, mi);

  

                // Теперь перемещаем максимальное число в конец

                // обращаем текущий массив

                flip(arr, curr_size - 1);

            }

        }

        return 0;

    }

  

    / * Утилита для печати массива arr [] * /

    static void printArray(int arr[], int arr_size)

    {

        for (int i = 0; i < arr_size; i++)

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

        System.out.println("");

    }

  

    / * Функция драйвера для проверки вышеуказанных функций * /

    public static void main(String[] args)

    {

        int arr[] = { 23, 10, 20, 11, 12, 6, 7 };

        int n = arr.length;

        pancakeSort(arr, n);

        System.out.println("Sorted Array:  ");

        printArray(arr, n);

    }

}
/ * Этот код предоставлен Девешом Агравалом * /

Выход:

Sorted Array:  
6 7 10 11 12 20 23

Пожалуйста, обратитесь к полной статье о сортировке блинов для более подробной информации!

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

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

0.00 (0%) 0 votes