C # быстрая сортировка со случайным поворотом - PullRequest
Новая
       28

C # быстрая сортировка со случайным поворотом

0 голосов
/ 31 октября 2010

Я пытаюсь изменить алгоритм heapSort на версию со случайным поворотом, и я не знаю, что делать.

Может ли кто-нибудь мне помочь?

Это код: 

//QuickSort w C#
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace QuickSort
{
    class Program
    {
        //Zamienia miejscami , zwykły swap
        static void Swap<T>(ref T lhs, ref T rhs)
        {
            T temp;
            temp = lhs;
            lhs = rhs;
            rhs = temp;
        }

        //Procedura qiucksort
        static void qsort(int[] tab, int left, int right)
        {
            if (left < right)
            {    
                int m = left;

                for (int i = left + 1; i <= right; i++)
                    if (tab[i] < tab[left])
                        Swap(ref tab[++m], ref tab[i]);

                Swap(ref tab[left], ref tab[m]);

                qsort(tab, left, m - 1);
                qsort(tab, m + 1, right);
            }       
        }


        static void Main(string[] args)
        {
            int[] a = { 0, 12, 34, 9, 54, 12, 77, -3, -20 };
            int i;
            int left = 0;
            int right = 8;

            Console.WriteLine("Data before sort ");
            for (i = 0; i < a.Length; i++)
                Console.Write(" {0} ", a[i]);
            Console.WriteLine();
            //Wywołanie procedury qsort
            qsort(a, left, right);

            Console.WriteLine("Data after sort");
            for (i = 0; i < a.Length; i++)
                Console.Write(" {0} ", a[i]);
            Console.WriteLine();
            Console.ReadLine();            
        }
    }
}

Это измененный код со случайным поворотом, этот код вылетает при: Swap(ref tab[++m], ref tab[i]); 


//QuickSort in C# with random pivot
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;</p>

<p>namespace QuickSort
{
    class Program
    {
        //common Swap function
        static void Swap(ref T lhs, ref T rhs)
        {
            T temp;
            temp = lhs;
            lhs = rhs;
            rhs = temp;
        }</p>

<pre><code>    //qiucksort procedure
    static void qsort(int[] tab, int left, int right)
    {
        if (left < right)
        {

            System.Random myRandom = new System.Random(); //Creating instance of random variable

            int m = myRandom.Next(left, right); //pivot = random number between left a right
           Swap(ref tab[left],ref tab[m]);

            for (int i = left + 1; i <= right; i++)
                if (tab[i] < tab[left])
                    Swap(ref tab[++m], ref tab[i]);

            Swap(ref tab[left], ref tab[m]);

            qsort(tab, left, m - 1);
            qsort(tab, m + 1, right);
        }


    }






    static void Main(string[] args)
    {
        Console.Title = "QuickSort";
        int[] a = { 0, 12, 34, 9, 54, 12, 77, -3};
        int i;
        int left = 0;
        int right = 7;


        Console.WriteLine("Data before sort ");
        for (i = 0; i < a.Length; i++)
            Console.Write(" {0} ", a[i]);
        Console.WriteLine();
        //call quicksort procedure
        qsort(a, left, right);

        Console.WriteLine("Data after sort");
        for (i = 0; i < a.Length; i++)
            Console.Write(" {0} ", a[i]);
        Console.WriteLine();
        Console.ReadLine();



    }
}

}

1 Ответ

2 голосов
/ 31 октября 2010

Ваш текущий стержень является первым элементом, вы выбираете его с помощью 

 int m = left;

Чтобы использовать случайный стержень, сначала

  • выберите случайный индекс p в диапазоне [слева, справа],
  • поменяйте вкладку [влево] и вкладку [p]

Потому что в противном случае вам пришлось бы радикально изменить свой алгоритм разбиения (который, к сожалению, встроенный).

Но

Случайный разворот далеко не идеален.Если это на полпути серьезно, рассмотрим опорную точку среднего из трех

...