Dada una array no ordenada, la tarea es ordenar la array dada. Solo se le permite realizar la siguiente operación en la array.
- flip(arr, i): array inversa de 0 a i
Ejemplos:
Entrada: arr[] = { 23, 10, 20, 11, 12, 6, 7 }
Salida: { 6, 7, 10, 11, 12, 20, 23}Entrada: arr[] = { 0, 1, 1, 0, 0 }
Salida: { 0, 0, 0, 1, 1 }
Enfoque: a diferencia de un algoritmo de clasificación tradicional, que intenta clasificar con la menor cantidad de comparaciones posibles, el objetivo es clasificar la secuencia en la menor cantidad de reversiones posible.
La idea es hacer algo similar a Selection Sort . Colocamos uno por uno el elemento máximo al final y reducimos el tamaño de la array actual en uno.
Los siguientes son los pasos detallados. Deje que la array dada sea arr[] y el tamaño de la array sea n.
- Comience desde el tamaño actual igual a n y reduzca el tamaño actual en uno mientras sea mayor que 1. Deje que el tamaño actual sea curr_size.
- Haz lo siguiente para cada curr_size
- Encuentre el índice del elemento máximo en arr[0 to curr_szie-1]. Deje que el índice sea ‘mi’
- Llamada flip (arr, mi)
- Llamar a flip(arr, curr_size – 1)
Vea el siguiente video para la visualización del algoritmo anterior.
http://www.youtube.com/embed/kk-_DDgoXfk
A continuación se muestra la implementación:
C
// C program to
// sort array using
// pancake sort
#include <stdio.h>
#include <stdlib.h>
/* Reverses 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--;
}
}
// Returns index of the
// maximum element in
// 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;
}
// The main function that
// sorts given array using
// flip operations
void pancakeSort(int* arr, int n)
{
// Start from the complete
// array and one by one
// reduce current size
// by one
for (int curr_size = n; curr_size > 1;
--curr_size)
{
// Find index of the
// maximum element in
// arr[0..curr_size-1]
int mi = findMax(arr, curr_size);
// Move the maximum
// element to end of
// current array if
// it's not already
// at the end
if (mi != curr_size - 1) {
// To move at the end,
// first move maximum
// number to beginning
flip(arr, mi);
// Now move the maximum
// number to end by
// reversing current array
flip(arr, curr_size - 1);
}
}
}
// A utility function to print
// n array of size n
void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
printf("%d ", arr[i]);
}
// Driver program to test above function
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++ program to
// sort array using
// pancake sort
#include<bits/stdc++.h>
using namespace std;
/* Reverses 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--;
}
}
// Returns index of the
// maximum element in
// 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;
}
// The main function that
// sorts given array using
// flip operations
void pancakeSort(int *arr, int n)
{
// Start from the complete
// array and one by one
// reduce current size
// by one
for (int curr_size = n; curr_size > 1;
--curr_size)
{
// Find index of the
// maximum element in
// arr[0..curr_size-1]
int mi = findMax(arr, curr_size);
// Move the maximum
// element to end of
// current array if
// it's not already
// at the end
if (mi != curr_size-1)
{
// To move at the end,
// first move maximum
// number to beginning
flip(arr, mi);
// Now move the maximum
// number to end by
// reversing current array
flip(arr, curr_size-1);
}
}
}
// A utility function to print
// n array of size n
void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
cout<< arr[i]<<" ";
}
// Driver program to test above function
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;
}
//This code is contributed by rathbhupendra
Java
// Java program to
// sort array using
// pancake sort
import java.io.*;
class PancakeSort {
/* Reverses 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--;
}
}
// Returns index of the
// maximum element in
// 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;
}
// The main function that
// sorts given array using
// flip operations
static int pancakeSort(int arr[], int n)
{
// Start from the complete
// array and one by one
// reduce current size by one
for (int curr_size = n; curr_size > 1;
--curr_size)
{
// Find index of the
// maximum element in
// arr[0..curr_size-1]
int mi = findMax(arr, curr_size);
// Move the maximum element
// to end of current array
// if it's not already at
// the end
if (mi != curr_size-1)
{
// To move at the end,
// first move maximum
// number to beginning
flip(arr, mi);
// Now move the maximum
// number to end by
// reversing current array
flip(arr, curr_size-1);
}
}
return 0;
}
/* Utility function to print array 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("");
}
/* Driver function to check for above functions*/
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);
}
}
/* This code is contributed by Devesh Agrawal*/
Python3
# Python3 program to
# sort array using
# pancake sort
# 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
# Returns index of the maximum
# element in 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
# The main function that
# sorts given array
# using flip operations
def pancakeSort(arr, n):
# Start from the complete
# array and one by one
# reduce current size
# by one
curr_size = n
while curr_size > 1:
# Find index of the maximum
# element in
# arr[0..curr_size-1]
mi = findMax(arr, curr_size)
# Move the maximum element
# to end of current array
# if it's not already at
# the end
if mi != curr_size-1:
# To move at the end,
# first move maximum
# number to beginning
flip(arr, mi)
# Now move the maximum
# number to end by
# reversing current array
flip(arr, curr_size-1)
curr_size -= 1
# A utility function to
# print an array of size n
def printArray(arr, n):
for i in range(0,n):
print ("%d"%( arr[i]),end=" ")
# Driver program
arr = [23, 10, 20, 11, 12, 6, 7]
n = len(arr)
pancakeSort(arr, n);
print ("Sorted Array ")
printArray(arr,n)
# This code is contributed by shreyanshi_arun.
C#
// C# program to sort array using
// pancake sort
using System;
class GFG {
// Reverses 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--;
}
}
// Returns index of the
// maximum element in
// 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;
}
// The main function that
// sorts given array using
// flip operations
static int pancakeSort(int []arr, int n)
{
// Start from the complete
// array and one by one
// reduce current size by one
for (int curr_size = n; curr_size > 1;
--curr_size)
{
// Find index of the
// maximum element in
// arr[0..curr_size-1]
int mi = findMax(arr, curr_size);
// Move the maximum element
// to end of current array
// if it's not already at
// the end
if (mi != curr_size - 1)
{
// To move at the end,
// first move maximum
// number to beginning
flip(arr, mi);
// Now move the maximum
// number to end by
// reversing current array
flip(arr, curr_size - 1);
}
}
return 0;
}
// Utility function to print
// array arr[]
static void printArray(int []arr,
int arr_size)
{
for (int i = 0; i < arr_size; i++)
Console.Write(arr[i] + " ");
Console.Write("");
}
// Driver function to check for
// above functions
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);
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program to
// sort array using
// pancake sort
/* Reverses arr[0..i] */
function flip(&$arr, $i)
{
$start = 0;
while ($start < $i)
{
$temp = $arr[$start];
$arr[$start] = $arr[$i];
$arr[$i] = $temp;
$start++;
$i--;
}
}
// Returns index of the
// maximum element in
// 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;
}
// The main function that
// sorts given array using
// flip operations
function pancakeSort(&$arr, $n)
{
// Start from the complete
// array and one by one
// reduce current size
// by one
for ($curr_size = $n; $curr_size > 1;
--$curr_size)
{
// Find index of the
// maximum element in
// arr[0..curr_size-1]
$mi = findMax($arr, $curr_size);
// Move the maximum
// element to end of
// current array if
// it's not already
// at the end
if ($mi != $curr_size-1)
{
// To move at the end,
// first move maximum
// number to beginning
flip($arr, $mi);
// Now move the maximum
// number to end by
// reversing current array
flip($arr, $curr_size-1);
}
}
}
// A utility function to print
// n array of size n
function printArray($arr, $n)
{
for ($i = 0; $i < $n; ++$i)
print($arr[$i]." ");
}
// Driver code
$arr = array(23, 10, 20, 11, 12, 6, 7);
$n = count($arr);
pancakeSort($arr, $n);
echo("Sorted Array \n");
printArray($arr, $n);
return 0;
// This code is contributed by chandan_jnu
?>
Javascript
<script>
// JavaScript program to sort array using pancake sort
// Reverses arr[0..i]
function flip(arr, i)
{
let temp, start = 0;
while (start < i)
{
temp = arr[start];
arr[start] = arr[i];
arr[i] = temp;
start++;
i--;
}
}
// Returns index of the
// maximum element in
// arr[0..n-1]
function findMax(arr, n)
{
let mi, i;
for (mi = 0, i = 0; i < n; ++i)
if (arr[i] > arr[mi])
mi = i;
return mi;
}
// The main function that
// sorts given array using
// flip operations
function pancakeSort(arr, n)
{
// Start from the complete
// array and one by one
// reduce current size by one
for (let curr_size = n; curr_size > 1; --curr_size)
{
// Find index of the
// maximum element in
// arr[0..curr_size-1]
let mi = findMax(arr, curr_size);
// Move the maximum element
// to end of current array
// if it's not already at
// the end
if (mi != curr_size - 1)
{
// To move at the end,
// first move maximum
// number to beginning
flip(arr, mi);
// Now move the maximum
// number to end by
// reversing current array
flip(arr, curr_size - 1);
}
}
return 0;
}
// Utility function to print
// array arr[]
function printArray(arr, arr_size)
{
for (let i = 0; i < arr_size; i++)
document.write(arr[i] + " ");
document.write("");
}
let arr = [23, 10, 20, 11, 12, 6, 7];
let n = arr.length;
pancakeSort(arr, n);
document.write("Sorted Array: " + "</br>");
printArray(arr, n);
</script>
Producción
Sorted Array 6 7 10 11 12 20 23
Complejidad de tiempo: O(n 2 ), las operaciones de cambio total de O(n) se realizan en el código anterior
Espacio auxiliar: O(1)
Echa un vistazo al curso de autoaprendizaje de DSA
Referencias:
http://en.wikipedia.org/wiki/Pancake_sorting
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA