Рубрики

Проблема сортировки блинчиков

Мы обсуждали сортировку блинов в предыдущем посте. Следующее — проблема, основанная на Сортировке Блина.
По несортированному массиву отсортировать по массиву. Вам разрешено делать только следующую операцию над массивом.

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

Представьте себе гипотетическую машину, где flip (i) всегда занимает O (1) время . Напишите эффективную программу для сортировки заданного массива за O (nLogn) времени на заданной машине . Если мы применим тот же алгоритм здесь, время будет O (n ^ 2), потому что алгоритм вызывает findMax () в цикле и find findMax () занимает O (n) время даже на этой гипотетической машине.

Мы можем использовать сортировку вставки, которая использует бинарный поиск. Идея состоит в том, чтобы запустить цикл от второго элемента к последнему элементу (от i = 1 до n-1) и вставить одну за другой arr [i] в arr [0..i-1] (как стандартный алгоритм сортировки вставкой ) , Когда мы вставляем элемент arr [i], мы можем использовать бинарный поиск, чтобы найти позицию arr [i] за время O (Logi). Когда у нас есть позиция, мы можем использовать несколько операций переворота, чтобы поместить arr [i] на новое место. Ниже приведены абстрактные шаги.

// Standard Insertion Sort Loop that starts from second element
for (i=1; i  O(n)
{
  int key = arr[i];

  // Find index of ceiling of arr[i] in arr[0..i-1] using binary search
  j = celiSearch(arr, key, 0, i-1); ----> O(logn) (See this)
    
  // Apply some flip operations to put arr[i] at correct place
} 

Поскольку операция переворачивания занимает O (1) на заданной гипотетической машине, общее время работы вышеуказанного алгоритма составляет O (nlogn). Спасибо Кумару за предложенную выше проблему и алгоритм.

Давайте посмотрим, как работает вышеуказанный алгоритм. ceilSearch () фактически возвращает индекс наименьшего элемента, который больше, чем arr [i] в arr [0..i-1]. Если такого элемента нет, возвращается -1. Пусть возвращаемое значение будет j. Если j = -1, нам не нужно ничего делать, так как arr [i] уже является самым большим элементом среди arr [0..i]. В противном случае нам нужно поместить arr [i] непосредственно перед arr [j].
Итак, как применять операции переворачивания для помещения arr [i] непосредственно перед arr [j], используя значения i и j. Давайте возьмем пример, чтобы понять это. Пусть i будет 6, а текущий массив будет {12, 15, 18, 30, 35, 40, 20 , 6, 90, 80}. Чтобы поместить 20 на новое место, массив должен быть изменен на {12, 15, 18, 20 , 30, 35, 40, 6, 90, 80}. Мы применяем следующие шаги, чтобы поставить 20 на новом месте.

1) Найдите j, используя ceilSearch (в приведенном выше примере j равно 3).
2) flip (arr, j-1) (массив становится {18, 15, 12, 30, 35, 40, 20 , 6, 90, 80})
3) флип (обр, я-1); (массив становится {40, 35, 30, 12, 15, 18, 20 , 6, 90, 80})
4) флип (обр, я); (массив становится { 20 , 18, 15, 12, 30, 35, 40, 6, 90, 80})
5) flip (обр, j); (массив становится {12, 15, 18, 20 , 30, 35, 40, 6, 90, 80})

Ниже приведена реализация вышеуказанного алгоритма.

C ++

// C ++ программа задачи сортировки блинов
#include<bits/stdc++.h> 

using namespace std; 

  
/ * Функция на основе бинарного поиска для
получить индекс потолка х в
arr [low..high] * /

int ceilSearch(int arr[], int low, int high, int x) 

    int mid; 

  

    / * Если х меньше или равен

    к первому элементу,

    затем верните первый элемент * /

    if(x <= arr[low]) 

        return low; 

  

    / * Если х больше чем

    последний элемент, затем вернуть -1 * /

    if(x > arr[high]) 

        return -1; 

  

    / * получить индекс среднего

    элемент arr [low..high] * /

    mid = (low + high)/2; / * низкий + (высокий - низкий) / 2 * /

  

    / * Если х совпадает со средним

    элемент, затем верните середину * /

    if(arr[mid] == x) 

        return mid; 

  

    / * Если x больше, чем arr [mid],

    тогда либо обр [середина + 1]

    потолок х или потолок

    лежит в обр [средняя + 1 ... высокая] * /

    if(arr[mid] < x) 

    

        if(mid + 1 <= high && x <= arr[mid+1]) 

            return mid + 1; 

        else

            return ceilSearch(arr, mid+1, high, x); 

    

  

    / * Если x меньше arr [mid], то либо arr [mid]

    потолок x или потолок в arr [mid-1 ... high] * /

    if (mid - 1 >= low && x > arr[mid-1]) 

        return mid; 

    else

        return ceilSearch(arr, low, mid - 1, x); 

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

    

  
/ * Функция для сортировки массива, используя
сортировка вставок, бинарный поиск и переворачивание * /

void insertionSort(int arr[], int size) 

    int i, j; 

  

    // Начинаем со второго элемента

    // и одну за другой вставляем arr [i]

    // в уже отсортированном arr [0..i-1]

    for(i = 1; i < size; i++) 

    

        // Находим наименьший элемент в arr [0..i-1]

        // который также больше чем

        // или равно arr [i]

        int j = ceilSearch(arr, 0, i-1, arr[i]); 

  

        // Проверяем, не было ли элемента

        // больше чем arr [i]

        if (j != -1) 

        

            // Поместить arr [i] перед arr [j] используя

            // следующие четыре операции переворота

            flip(arr, j-1); 

            flip(arr, i-1); 

            flip(arr, i); 

            flip(arr, j); 

        

    

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

void printArray(int arr[], int n) 

    int i; 

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

        cout<<arr[i]<<" "

  
/ * Код водителя * /

int main() 

    int arr[] = {18, 40, 35, 12, 30, 35, 20, 6, 90, 80}; 

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

    insertionSort(arr, n); 

    printArray(arr, n); 

    return 0; 

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

С

// C программа задачи сортировки блинчиков
#include <stdlib.h>
#include <stdio.h>

  
/ * Функция на основе бинарного поиска для получения индекса потолка x в

   arr [low..high] * /

int ceilSearch(int arr[], int low, int high, int x)

{

    int mid;

  

    / * Если x меньше или равен первому элементу,

      затем верните первый элемент * /

    if(x <= arr[low])

        return low;

  

    / * Если x больше, чем последний элемент, вернуть -1 * /

    if(x > arr[high])

        return -1;

  

    / * получить индекс среднего элемента arr [low..high] * /

    mid = (low + high)/2;  / * низкий + (высокий - низкий) / 2 * /

  

    / * Если x совпадает со средним элементом, вернуть mid * /

    if(arr[mid] == x)

        return mid;

  

    / * Если x больше, чем arr [mid], то либо arr [mid + 1]

      потолок x или потолок в arr [mid + 1 ... high] * /

    if(arr[mid] < x)

    {

        if(mid + 1 <= high && x <= arr[mid+1])

            return mid + 1;

        else

            return ceilSearch(arr, mid+1, high, x);

    }

  

    / * Если x меньше arr [mid], то либо arr [mid]

       потолок x или потолок в arr [mid-1 ... high] * /

    if (mid - 1 >= low && x > arr[mid-1])

        return mid;

    else

        return ceilSearch(arr, low, mid - 1, x);

}

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

    }

}

  
/ * Функция для сортировки массива с использованием сортировки вставкой, двоичного поиска и отражения * /

void insertionSort(int arr[], int size)

{

    int i, j;

  

    // Начинаем со второго элемента и вставляем один за другим arr [i]

    // в уже отсортированном arr [0..i-1]

    for(i = 1; i < size; i++)

    {

        // Находим наименьший элемент в arr [0..i-1], который также больше чем

        // или равно arr [i]

        int j = ceilSearch(arr, 0, i-1, arr[i]);

  

        // Проверяем, не было ли элемента больше, чем arr [i]

        if (j != -1)

        {

            // Поместить arr [i] перед arr [j], используя следующие четыре операции переворота

            flip(arr, j-1);

            flip(arr, i-1);

            flip(arr, i);

            flip(arr, j);

        }

    }

}

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

void printArray(int arr[], int n)

{

    int i;

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

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

}

  
/ * Драйверная программа для проверки сортировки вставок * /

int main()

{

    int arr[] = {18, 40, 35, 12, 30, 35, 20, 6, 90, 80};

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

    insertionSort(arr, n);

    printArray(arr, n);

    return 0;

}

Джава

// Java-программа задачи сортировки блинов

class GfG {

  
/ * Функция на основе бинарного поиска для получения индекса потолка x в
arr [low..high] * /

static int ceilSearch(int arr[], int low, int high, int x) 

    int mid; 

  

    / * Если x меньше или равен первому элементу,

    затем верните первый элемент * /

    if(x <= arr[low]) 

        return low; 

  

    / * Если x больше, чем последний элемент, вернуть -1 * /

    if(x > arr[high]) 

        return -1

  

    / * получить индекс среднего элемента arr [low..high] * /

// низкий + (высокий - низкий) / 2

    mid = (low + high)/2

  

    / * Если x совпадает со средним элементом, вернуть mid * /

    if(arr[mid] == x) 

        return mid; 

  

    / * Если x больше, чем arr [mid], то либо arr [mid + 1]

    потолок x или потолок в arr [mid + 1 ... high] * /

    if(arr[mid] < x) 

    

        if(mid + 1 <= high && x <= arr[mid+1]) 

            return mid + 1

        else

            return ceilSearch(arr, mid+1, high, x); 

    

  

    / * Если x меньше arr [mid], то либо arr [mid]

    потолок x или потолок в arr [mid-1 ... high] * /

    if (mid - 1 >= low && x > arr[mid-1]) 

        return mid; 

    else

        return ceilSearch(arr, low, mid - 1, x); 

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

    

  
/ * Функция для сортировки массива с использованием сортировки вставкой, двоичного поиска и отражения * /

static void insertionSort(int arr[], int size) 

    int i; 

  

    // Начинаем со второго элемента и вставляем один за другим arr [i]

    // в уже отсортированном arr [0..i-1]

    for(i = 1; i < size; i++) 

    

        // Находим наименьший элемент в arr [0..i-1], который также больше чем

        // или равно arr [i]

        int j = ceilSearch(arr, 0, i-1, arr[i]); 

  

        // Проверяем, не было ли элемента больше, чем arr [i]

        if (j != -1

        

            // Поместить arr [i] перед arr [j], используя следующие четыре операции переворота

            flip(arr, j-1); 

            flip(arr, i-1); 

            flip(arr, i); 

            flip(arr, j); 

        

    

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

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

    int i; 

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

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

  
/ * Драйверная программа для проверки сортировки вставок * /

public static void main(String[] args) 

    int arr[] = {18, 40, 35, 12, 30, 35, 20, 6, 90, 80}; 

    int n = arr.length; 

    insertionSort(arr, n); 

    printArray(arr, n); 


питон

# Python-программа задачи сортировки блинов
#A Функция на основе бинарного поиска для получения индекса потолка x в arr [low..high]

  

def ceilSearch(arr,low,high,x):

      

    # Если x меньше или равен первому элементу,

    # затем вернуть первый элемент

    if x <= arr[low]:

        return low

      

    # Если x больше, чем последний элемент, вернуть -1

    if x > arr[high]:

        return -1

          

    # получить индекс среднего элемента arr [low..high]

    mid = (low + high)/2  #low + (high-low) / 2

      

    # Если x совпадает со средним элементом, тогда вернуть середину

    if(arr[mid] == x):

        return mid

      

    # Если x больше, чем arr [mid], то либо arr [mid + 1]

    # потолок x или потолок в обр [средняя + 1 ... высокая]

    if(arr[mid] < x):

        if(mid + 1 <= high and x <= arr[mid+1]):

            return mid + 1

        else:

            return ceilSearch(arr, mid+1, high, x)

      

    # Если x меньше, чем arr [mid], то либо arr [mid]

    # Потолок x или потолок находится в arr [mid-1 ... high]

    if (mid - 1 >= low and x > arr[mid-1]):

        return mid

    else:

        return ceilSearch(arr, low, mid - 1, x)

          
#Reverses 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

  
# Функция сортировки массива с использованием вставки, бинарного поиска и отражения

def insertionSort(arr):

      

    # Начинаем со второго элемента и вставляем один за другим arr [i]

    # в уже отсортированном arr [0..i-1]

    for i in range(1,len(arr)):

        # Найти самый маленький элемент в arr [0..i-1], который также больше, чем

        # или равно arr [i]

        j = ceilSearch(arr, 0, i-1, arr[i])

          

        # Проверьте, не было ли элемента больше, чем arr [i]

        if (j != -1):

            # Положите arr [i] перед arr [j], используя следующие четыре операции переворота

            flip(arr, j-1)

            flip(arr, i-1)

            flip(arr, i)

            flip(arr, j)

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

def printArray(arr):

    for i in range(0,len(arr)):

        print arr[i],

      
# Драйвер для проверки вышеуказанной функции

arr=[18, 40, 35, 12, 30, 35, 20, 6, 90, 80]

insertionSort(arr)
printArray(arr)

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

C #

// C # программа задачи сортировки блинов

using System;

  

class GFG 

  
// Функция на основе бинарного поиска, чтобы получить
// индекс потолка x в arr [low..high]

static int ceilSearch(int []arr, int low, 

                      int high, int x) 

    int mid; 

  

    // Если х меньше или равен

    // первый элемент,

    // затем возвращаем первый элемент

    if(x <= arr[low]) 

        return low; 

  

    // Если х больше, чем последний элемент,

    // затем возвращаем -1

    if(x > arr[high]) 

        return -1; 

  

    // получаем индекс среднего элемента

    // из arr [low..high]

    // низкий + (высокий - низкий) / 2

    mid = (low + high) / 2; 

  

    // Если х совпадает со средним элементом,

    // затем возвращаем середину

    if(arr[mid] == x) 

        return mid; 

  

    // Если x больше, чем arr [mid],

    // тогда либо arr [mid + 1] это потолок x,

    // или потолок находится в arr [mid + 1 ... high]

    if(arr[mid] < x) 

    

        if(mid + 1 <= high && x <= arr[mid + 1]) 

            return mid + 1; 

        else

            return ceilSearch(arr, mid + 1, high, x); 

    

  

    // Если x меньше, чем arr [mid],

    // тогда либо arr [mid] является потолком x

    // или потолок лежит в arr [mid-1 ... high]

    if (mid - 1 >= low && x > arr[mid - 1]) 

        return mid; 

    else

        return ceilSearch(arr, low, mid - 1, x); 

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

    

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

static void insertionSort(int []arr, int size) 

    int i; 

  

    // Начнем со второго элемента и

    // вставляем одну за другой arr [i] в

    // уже отсортировано обр [0..i-1]

    for(i = 1; i < size; i++) 

    

        // Находим наименьший элемент в arr [0..i-1]

        // который также больше или равен arr [i]

        int j = ceilSearch(arr, 0, i - 1, arr[i]); 

  

        // Проверяем, не было ли элемента больше, чем arr [i]

        if (j != -1) 

        

            // Поместить arr [i] перед arr [j] используя

            // следующие четыре операции переворота

            flip(arr, j - 1); 

            flip(arr, i - 1); 

            flip(arr, i); 

            flip(arr, j); 

        

    

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

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

    int i; 

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

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

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

public static void Main(String[] args) 

    int []arr = {18, 40, 35, 12, 30, 

                 35, 20, 6, 90, 80}; 

    int n = arr.Length; 

    insertionSort(arr, n); 

    printArray(arr, n); 


  
// Этот код предоставлен Принчи Сингхом

Выход:

6 12 18 20 30 35 35 40 80 90

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

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

Проблема сортировки блинчиков

0.00 (0%) 0 votes