using System;

public    class Program

    {

        public void Main(string[] args)

        {

            int[] arr1 = { 9, 6, 3, 4, 5, 9, 3, 8, 7, 9,10,12 };

            Node<int> list = a(arr1);

            PrintList(list);

​

​

            string q = Console.ReadLine();

        }

​

​

        public static Node<int> ArrToList(int[] arr)

        {

            Node<int> firstNode = new Node<int>(arr[0]);

            Node<int> node = firstNode;

            Node<int> pos = firstNode;

​

            for (int i = 1; i < arr.Length; i++)

            {

                node = new Node<int>(arr[i]);

                pos.SetNext(node);

                pos = pos.GetNext();

            }

            return (firstNode);

        }

​

​

​

        public static void PrintList(Node<int> firstNode)

        {

            Node<int> pos = firstNode;

            while (pos != null)

            {

                Console.WriteLine(pos.GetValue());

                pos = pos.GetNext();

            }

        }

        public static Node<int> a(int[] arr)

        {

            Node<int> first = ArrToList(arr);

            Node<int> temp = first;

            Node<int> minTemp = first;

            int x;

            while(temp!= null)

            {

                if(temp.GetValue() < minTemp.GetValue())

                    minTemp = temp;

                temp = temp.GetNext();

            }

            x = minTemp.GetValue();

            minTemp.SetValue(first.GetValue());

            first.SetValue(x);

            Node<int> pos = first.GetNext();

            temp = pos;

            minTemp = pos;

            while(pos != null)

            {

                while(temp!= null)

                {

                    if(temp.GetValue() < minTemp.GetValue())

                        minTemp = temp;

                    temp = temp.GetNext();

                }

                x = minTemp.GetValue();

                minTemp.SetValue(pos.GetValue());

                pos.SetValue(x);

                pos = pos.GetNext();

                temp=pos;

                minTemp = pos;

            }

            return(first);

        }

    }

​

​

​

   public class Node<T>

    {

        private T value;

        private Node<T> next;

​

        public Node(T value)

        {

            this.value = value;

            this.next = null;

        }

        public Node(T value, Node<T> next)

        {

            this.value = value;

            this.next = next;

        }

        public T GetValue()

        {

            return this.value;

        }

        public Node<T> GetNext()

        {

            return this.next;

        }

        public bool HasNext()

        {

            return (this.next != null);

        }

        public void SetValue(T value)

        {

            this.value = value;

        }

        public void SetNext(Node<T> next)

        {

            this.next = next;

        }

        public override string ToString()

        {

            return this.value.ToString() + " ";

        }

    }

​