Рубрики

Блинная сортировка

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

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

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

Идея состоит в том, чтобы сделать что-то похожее на Selection Sort . Мы один за другим размещаем максимальный элемент в конце и уменьшаем размер текущего массива на единицу.

Ниже приведены подробные шаги. Пусть заданный массив будет arr [], а размер массива будет n.
1) Начните с текущего размера, равного n, и уменьшите текущий размер на единицу, пока он больше 1. Пусть текущий размер будет curr_size. Делайте следующее для каждого curr_size
…… а) Найти индекс максимального элемента в arr [0..curr_szie-1]. Пусть индекс будет ми
…… б) Call flip (обр, ми)
… C) вызовите flip (arr, curr_size-1)

Смотрите следующее видео для визуализации вышеуказанного алгоритма.

http://www.youtube.com/embed/kk-_DDgoXfk

С

// C программа для
// сортируем массив используя
// блины
#include <stdlib.h>
#include <stdio.h>

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

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]

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;

}

  
// Основная функция, которая
// сортирует указанный массив, используя
// перевернуть операции

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

        }

    }

}

  
// Утилита для печати
// n массив размером n

void printArray(int arr[], int n)

{

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

        printf("%d ", arr[i]);

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

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

    int n = sizeof(arr)/sizeof(arr[0]);

  

    pancakeSort(arr, n);

  

    puts("Sorted Array ");

    printArray(arr, n);

  

    return 0;

}

CPP

// C ++ программа для
// сортируем массив используя
// блины
#include<bits/stdc++.h> 

using namespace std; 

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

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]

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; 

  
// Основная функция, которая
// сортирует указанный массив, используя
// перевернуть операции

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

        

    

  
// Утилита для печати
// n массив размером n

void printArray(int arr[], int n) 

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

        cout<< arr[i]<<" "

  
// Программа драйвера для проверки вышеуказанной функции

int main() 

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

    int n = sizeof(arr)/sizeof(arr[0]); 

  

    pancakeSort(arr, n); 

  

    cout<<"Sorted Array "<<endl; 

    printArray(arr, n); 

  

    return 0; 

  
// Этот код предоставлен rathbhupendra

Джава

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

    }

  

    // Основная функция, которая

    // сортирует указанный массив, используя

    // перевернуть операции

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

    }

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

python3

# Python3 программа для
# сортировать массив используя
# блины

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

def flip(arr, i):

    start = 0

    while start < i:

        temp = arr[start]

        arr[start] = arr[i]

        arr[i] = temp

        start += 1

        i -= 1

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

def findMax(arr, n):

    mi = 0

    for i in range(0,n):

        if arr[i] > arr[mi]:

            mi = i

    return mi

  
# Основная функция, которая
# сортирует данный массив
# использование операций переворота

def pancakeSort(arr, n):

      

    # Начните с полного

    # массив и один за другим

    # уменьшить текущий размер

    # одним

    curr_size = n

    while curr_size > 1:

        # Найти индекс максимума

        # элемент в

        # arr [0..curr_size-1]

        mi = findMax(arr, curr_size)

  

        # Переместить максимальный элемент

        # до конца текущего массива

        # если это еще не в

        # конец

        if mi != curr_size-1:

            # Чтобы двигаться в конце,

            # первый ход максимум

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

            flip(arr, mi)

  

            # Теперь переместите максимум

            # номер до конца

            # реверсировать текущий массив

            flip(arr, curr_size-1)

        curr_size -= 1

  
# Полезная функция для
# распечатать массив размером n

def printArray(arr, n):

    for i in range(0,n):

        print ("%d"%( arr[i]),end=" ")

  
# Драйверная программа

arr = [23, 10, 20, 11, 12, 6, 7]

n = len(arr)

pancakeSort(arr, n);

print ("Sorted Array ")

printArray(arr,n)

  
# Этот код предоставлен shreyanshi_arun.

C #

// C # программа для сортировки массива с помощью
// блины

using System;

  

class GFG {

  

    // Обращает 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;

    }

  

    // Основная функция, которая

    // сортирует указанный массив, используя

    // перевернуть операции

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

            Console.Write(arr[i] + " ");

              

        Console.Write("");

    }

  

    // Функция драйвера для проверки

    // вышеуказанные функции

    public static void Main ()

    {

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

        int n = arr.Length;

          

        pancakeSort(arr, n);

          

        Console.Write("Sorted Array: ");

        printArray(arr, n);

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// PHP программа для
// сортируем массив используя
// блины

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

function flip(&$arr, $i)

{

    $start = 0;

    while ($start < $i)

    {

        $temp = $arr[$start];

        $arr[$start] = $arr[$i];

        $arr[$i] = $temp;

        $start++;

        $i--;

    }

}

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

function findMax($arr, $n)

{

    $mi = 0;

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

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

                $mi = $i;

    return $mi;

}

  
// Основная функция, которая
// сортирует указанный массив, используя
// перевернуть операции

function pancakeSort(&$arr, $n)

{

    // Начнем с полного

    // массив и один за другим

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

    // одним

    for ($curr_size = $n; $curr_size > 1; --$curr_size)

    {

        // Найти индекс

        // максимальный элемент в

        // arr [0..curr_size-1]

        $mi = findMax($arr, $curr_size);

  

        // Переместить максимум

        // элемент до конца

        // текущий массив, если

        // это еще не

        // в конце

        if ($mi != $curr_size-1)

        {

            // для перемещения в конце,

            // максимум первого хода

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

            flip($arr, $mi);

  

            // Теперь перемещаем максимум

            // номер до

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

            flip($arr, $curr_size-1);

        }

    }

}

  
// Утилита для печати
// n массив размером n

function printArray($arr, $n)

{

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

        print($arr[$i]." ");

}

  
// Код драйвера

$arr = array(23, 10, 20, 11, 12, 6, 7);

$n = count($arr);

  

pancakeSort($arr, $n);

  

echo("Sorted Array \n");

printArray($arr, $n);

  

return 0;

      
// Этот код предоставлен chandan_jnu
?>


Выход:

Sorted Array
6 7 10 11 12 20 23

Всего операций O (n) переворот выполняются в приведенном выше коде. Общая сложность времени O (n ^ 2).

Ссылки:
http://en.wikipedia.org/wiki/Pancake_sorting

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

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

Блинная сортировка

0.00 (0%) 0 votes