Jak posortować stos mając do dyspozycji tylko operacje Push, Pop i IsEmpty?

Jak posortować stos mając do dyspozycji tylko operacje Push, Pop i IsEmpty?. Najłatwiej zrobić to rekurencyjnie

using System;
using System.Collections.Generic;


namespace CodeKata
{
    public static class StackSort
    {
        /// <summary>
        /// Sort the stack in the ascending order
        /// </summary>
        public static void SortStack<T>(Stack<T> stack) where T : IComparable<T> 
        {
            if (!stack.IsEmpty())
            {
                T top = stack.Pop();
                SortStack(stack);
                Insert(stack, top);
            }

        }

        private static void Insert<T>(Stack<T> stack, T value) where T : IComparable<T>
        {
            if (!stack.IsEmpty())
            {
                T top = stack.Pop();
                // top < value
                if (top.CompareTo(value) < 0)
                {
                    Insert(stack, value);
                    stack.Push(top);
                }
                else
                {
                    stack.Push(top);
                    stack.Push(value);
                }
            }
            else
            {
                stack.Push(value);
            }

        }

        private  static bool IsEmpty<T>(this Stack<T> stack) {
            return stack.Count == 0;
        }
    }
}

Powyższy algorytm kreatywnie wykorzystuje stos wysołań jako dodatkową strukturę danych. Najpierw wszystkie elementy ze stosu do posortowania
są zdejmowane a potem po kolei wstawiane na właściwe miejsce. Cała robotę wykonuje metody Insert do której przekazujemy posortowany stos i wartość do wstawienia a ona umieszcza ją na właściwej pozycji (w razie konieczności wywołując się rekurencyjnie).

Przykładowo, w przypadku sortowania stosu [4, 2, 3, 1] drzewo drzewo wywołań rekurencyjnych wygląda tak

SortStack([4, 2, 3, 1])
   SortStack([2, 3, 1])
      SortStack([3, 1])
         SortStack([1])
            SortStack([])
            []
            Insert([], 1)
            [1]
         [1]
         Insert([1], 3)
            Insert([], 3)
            [3]
         [1, 3]
      [1, 3]
      Insert([1, 3], 2)
         Insert([3], 2)
         [2, 3]
      [1, 2, 3]
   [1, 2, 3]
   Insert([1, 2, 3], 4)
      Insert([2, 3], 4)
         Insert([3], 4)
            Insert([], 4)
            [4]
         [3, 4]
      [2, 3, 4]
   [1, 2, 3, 4]
[1, 2, 3, 4]

Algorytm działa w czasie O(n2) i wymaga O(n) dodatkowej pamięci (mam nadzieję że uwierzycie mi na słowo – bo udowodnić tego nie potrafię. Może kilka lat temu…). Jest to bardziej widoczne w wersji bez rekurencji – ale o tym innym razem.
Warto też zauważyć, że stosując podobne podejście można rozwiązać inny problem – odwrócenie stosu

/// <summary>
/// Reverse the stack
/// </summary>
public static void ReverseStack<T>(Stack<T> stack)
{
	if (!stack.IsEmpty())
	{
		T top = stack.Pop();
		ReverseStack(stack);
		InsertAtBottom(stack, top);
	}
}

private static void InsertAtBottom<T>(Stack<T> stack, T value)
{
	if (!stack.IsEmpty())
	{
		T top = stack.Pop();
		InsertAtBottom(stack, value);
		stack.Push(top);
	}
	else
	{
		stack.Push(value);
	}
}

private  static bool IsEmpty<T>(this Stack<T> stack) {
	return stack.Count == 0;
}

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s