25 июля 2012

Сортировка вставкой

Сортировка вставкой (insertion sort).
Суть проблемы состоит в сортировке массива входных чисел.



На вход программы подаётся массив А {a1,a2,a3,..,an}.
На выходе получаем отсортированный массив А' {a'1,a'2,a'3,..,a'n} , где a'1<=a'2<=a'3<=..<=a'n.



Сортировка вставкой напоминает способ, к которому прибегают игроки для сортировки имеющихся на руках карт. Пусть вначале в левой руке нет ни одной карты, и все они лежат на столе рубашкой вверх. Далее со стола берется по одной карте, каждая из которых помещается в нужное место среди карт, которые находятся в левой руке. 
Код программы:




using System;



class Program

{

    static void Main(string[] args)

    {

        int[] A = generateArray(6);

        Console.WriteLine("Начальный массив");

        viewer(A);

        for (int j=1;j<A.Length;j++)

        {

            int key = A[j];

            int i=j-1;

            while (i >= 0 && A[i] < key)

            {

                A[i + 1] = A[i];

                i--;

                Console.WriteLine("Изменение в массиве № {0} - элемент № {1}:", j,i+2);

                viewer(A);

            }

            A[i + 1] = key;

            Console.WriteLine("Готовый к изменению массив № {0}:",j);

            viewer(A);



        }

        Console.WriteLine("Итоговый массив:");

        viewer(A);

    }



    static void viewer(int[] A)

    {

        for (int j = 0; j < A.Length; j++)

        {

            Console.WriteLine(A[j]);

        }

        Console.WriteLine();

        Console.ReadKey();

    }



    static int[] generateArray(int length)

    {

        int[] tempArray = new int[length];

        Random r = new Random();

        for (int i = 0; i < length; i++)

        {

            tempArray[i] = r.Next(0, 10);

        }

        return tempArray;

    }

}
Если необходимо сделать сортировку по убыванию, то меняем строку:

while (i >= 0 && A[i] > key)

Комментариев нет: