code

code
mail@pastecode.io avatar
unknown
abc
2 years ago
2.7 kB
3
Indexable
Never
using System;
using System.Diagnostics;

namespace DaThuc
{
    class Program
    {
        static void Main()
        {
            Random r = new Random();
            int n = int.Parse(Console.ReadLine());
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
            {
                a[i] = r.Next(-10, 11);
            }
            //Console.Write("Nhap k: ");
            //int k = int.Parse(Console.ReadLine());
            Stopwatch st1 = new Stopwatch();
            st1.Start();
            quicksort1(a, 0, n - 1);
            for (int i = 0; i < a.Length; i++)
            {
                Console.Write(a[i] + " ");
            }
            Console.WriteLine();
            st1.Stop();
            Stopwatch st2 = new Stopwatch();
            st2.Start();
            quicksort2(a, 0, n - 1);
            for (int i = 0; i < a.Length; i++)
            {
                Console.Write(a[i] + " ");
            }
            Console.WriteLine();
            //Tinh2(k,a.Clone() as int[]);
            st2.Stop();
            Stopwatch st3 = new Stopwatch();
            st3.Start();
            //Console.WriteLine("Gia tri da thuc C3 = " + Tinh3(n, x));
            st3.Stop();
            Console.WriteLine("Thoi Gian chay lan luot cua ba cach tren la: C1: {0}  C2: {1}  C3: {2}", st1.Elapsed, st2.Elapsed, st3.Elapsed);
        }
        static void swap(ref int a,ref int b)
        {
            int temp = a;
            a = b;
            b = temp;
        }
        static int partition(int[] arr, int l, int h)
        {
            int x = arr[h];
            int i = l - 1;
            for (int j = l; j <= h - 1; j++)
            {
                if (arr[j] <= x)
                {
                    i++;
                    swap(ref arr[i],ref arr[j]);
                }
            }
            swap(ref arr[i + 1],ref arr[h]);
            return (i + 1);
        }
        static void quicksort1(int[] arr, int l, int h)
        {
            if (l < h)
            {
                int p = partition(arr, l, h);
                quicksort1(arr, l, p - 1);
                quicksort1(arr, p + 1, h);
            }
        }
        static void quicksort2(int[] arr, int l, int h)
        {
            if (l < h)
            {
                int pivot = partition(arr, l, h);

                if (pivot > 1)
                {
                    partition(arr, l, pivot - 1);
                }
                if (pivot + 1 < h)
                {
                    partition(arr, pivot + 1, h);
                }
            }

        }
    }
}