Pancake Sort

Aspecte teoretice:

Bucătarul-șef al restaurantului este neglijent și de fiecare dată când pregătește un teanc de clătite, ele ies de dimensiuni diferite. Prin urmare, atunci când le-am livra la un client la masă, trebuie rearanjate (pentru ca cele mai mici să fie deasupra și cele mai mari să fie în partea de jos). Pentru aceasta, trebuie apucate mai multe clătite din partea de sus și apoi răsturnate, repetând acest procedeu de câte ori e necesar.

Analiza complexității:

Cea mai simplă variantă necesită cel mult 2n−3 inversări: cel mai mare element dintre cele nesortate deja se aduce pe prima poziție și apoi în poziția corectă; primele 3 elemente necesită cel mult 3 inversiuni.

Cazul nefavorabil: O(n)
Cazul mediu: O(n)
Cazul favorabil: O(n)

Exemplu Pas cu Pas:

Presupunem că avem un teanc cu 5 clătite în următoarea ordine: 5 2 3 4 1.
Pasul 1: Răsturnăm tot teancul pentru a pune cea mai mare clătită în partea de jos. 1 4 3 2 5
Pasul 2: Răsturnăm primele 4 clătite. 2 3 4 1 5
Pasul 3: Răsturnăm primele 3 clătite. 4 3 2 1 5
Pasul 4: Răsturnăm primele 4 clătite. 1 2 3 4 5

Implementare:

Cod Sursa C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace PancakeSortCS
{
    public static class PancakeSorter
    {
        public static void PancakeSort<T>(List<T> list) where T : IComparable
        {
            if (list.Count < 2)
            {
                return;
            }
            int i, a, max_num_pos;
            for (i = list.Count; i > 1; i--)
            {
                max_num_pos = 0;
                for (a = 0; a < i; a++)
                {
                    if (list[a].CompareTo(list[max_num_pos]) > 0)
                    {
                        max_num_pos = a;
                    }
                }
                if (max_num_pos == i - 1)
                {
                    continue;
                }
                if (max_num_pos > 0)
                {
                    Flip(list, list.Count, max_num_pos + 1);
                }
                Flip(list, list.Count, i);
            }
            return;
        }
        private static void Flip<T>(List<T> list, int length, int num)
        {
            for (int i = 0; i < --num; i++)
            {
                T swap = list[i];
                list[i] = list[num];
                list[num] = swap;
            }
        }
 
        public static void Main (string [] args)
    {
       
        List<int> lista = new List<int>();
        lista.Add(2);
        lista.Add(3);
        lista.Add(5);
        lista.Add(7); 
        lista.Add(1);
        lista.Add(4);
        lista.Add(6);
        lista.Add(9);
        lista.Add(8);
        PancakeSort(lista);
        
        foreach (int value in lista)
        {
            Console.WriteLine(value);
        }
        Console.ReadKey();
    }
    }
}

Cod Sursa C++

// PancakeSortCPP.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
 
using namespace std;
 
// pancake sort template (calls predicate to determine order)
template <typename BidIt, typename Pred>
void pancake_sort(BidIt first, BidIt last, Pred order)
{
    if (std::distance(first, last) < 2) return; // no sort needed
 
    for (; first != last; --last)
    {
        BidIt mid = std::max_element(first, last, order);
        if (mid == last - 1)
        {
            continue; // no flips needed
        }
        if (first != mid)
        {
            std::reverse(first, mid + 1); // flip element to front
        }
        std::reverse(first, last); // flip front to final position
    }
}
 
// pancake sort template (ascending order)
template <typename BidIt>
void pancake_sort(BidIt first, BidIt last)
{
    pancake_sort(first, last, std::less<typename std::iterator_traits<BidIt>::value_type>());
}
 
int main()
{
    std::vector<int> data;
    for (int i = 0; i < 20; ++i)
    {
        data.push_back(i); // generate test data
    }
    std::random_shuffle(data.begin(), data.end()); // scramble data
 
    std::copy(data.begin(), data.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";
 
    pancake_sort(data.begin(), data.end()); // ascending pancake sort
 
    std::copy(data.begin(), data.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";
	system("pause");
}

Cod Sursa JAVA

public class PancakeSortJAVA{   int[] heap;   public String toString()   {     String info = "";     for (int x: heap)       info += x + " ";     return info;   }  public void flip(int n)   {     for (int i = 0; i < (n+1) / 2; ++I)     {       int tmp = heap[i];       heap[i] = heap[n-i];       heap[n-i] = tmp;     }     System.out.println(“flip(0..” + n + “): ” + toString());   }  public int[] minmax(int n)   {     int xm, xM;     xm = xM = heap[0];     int posm = 0, posM = 0;     for (int i = 1; i < n; ++I)     {       if (heap[i] < xm)       {         xm = heap[i];         posm = i;       }       else if (heap[i] > xM)       {         xM = heap[i];         posM = i;       }     }     return new int[] {posm, posM};   }   public void sort(int n, int dir)   {     if (n == 0)       return;     int[] mM = minmax(n);     int bestXPos = mM[dir];     int altXPos = mM[1-dir];     boolean flipped = false;     if (bestXPos == n-1)     {       –n;     }     else if (bestXPos == 0)     {       flip(n-1);       –n;     }     else if (altXPos == n-1)     {       dir = 1-dir;       –n;       flipped = true;     }     else     {       flip(bestXPos);     }     sort(n, dir);     if (flipped)     {       flip(n);     }   }   PancakeSortJAVA(int[] numbers)   {     heap = numbers;     sort(numbers.length, 1);   }   public static void main(String[] args)   {     int[] numbers = new int[args.length];     for (int i = 0; i < args.length; ++i)     numbers[i] = Integer.valueOf(args[i]);     PancakeSortJAVA pancakes = new PancakeSortJAVA(numbers);     System.out.println(pancakes);   } }

 

Rezultat: