تصویر ثابت

پایگاه رسمی مهندس محسن اشکبوس

کارشناس ارشد طراحی سامانه های نرم افزاری تحت وب و شیرپوینت

پایگاه رسمی مهندس محسن اشکبوس

کارشناس ارشد طراحی سامانه های نرم افزاری تحت وب و شیرپوینت

آخرین نظرات

الگوریتم مرتب سازی QuickSort

اشکبوس محسن | چهارشنبه, ۲ بهمن ۱۳۹۲، ۰۵:۱۳ ب.ظ

QuickSort یک الگوریتم تقسیم و غلبه است .

این الگوریتم بر اساس الگوریتم پارتیشن کار می کند و یک عنصر محوری (Pivot) که معمولاً اولین عنصر از چپ است را در نظر می گیرد و طوری عناصر را به کمک الگوریتم پارتیشن مرتب می کند که در هر گذر تمامی عناصر سمت چپ عنصر محوری از آن کوچکتر و تمامی عناصر سمت راست عنصر محوری از آن بزرگتر هستند.و الگوریتم به صورت بازگشتی  این روند را ادامه می دهد تا کلیه عناصر مرتب شوند.

مرتبه زمانی این الگوریتم در بدترین حالت :  

 O(N^2)                                                           

و در بهترین حالت :

 O(nlogn)                                                         

کدی(کد C#) که در اینجا قرار میدهم  عناصری آرایه ای از جنس String را مرتب می کند.

 

 

کد :

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace Quicksort
{
    class Program
    {
        static void Main(string[] args)
        {
            // Create an unsorted array of string elements
            string[] unsorted = { "z","e","x","c","m","q","a"};
 
            // Print the unsorted array
            for (int i = 0; i < unsorted.Length; i++)
            {
                Console.Write(unsorted[i] + " ");
            }
 
            Console.WriteLine();
 
            // Sort the array
            Quicksort(unsorted, 0, unsorted.Length - 1);
 
            // Print the sorted array
            for (int i = 0; i < unsorted.Length; i++)
            {
                Console.Write(unsorted[i] + " ");
            }
 
            Console.WriteLine();
 
            Console.ReadLine();
        }
 
        public static void Quicksort(IComparable[] elements, int left, int right)
        {
            int i = left, j = right;
            IComparable pivot = elements[(left + right) / 2];
 
            while (i <= j)
            {
                while (elements[i].CompareTo(pivot) < 0)
                {
                    i++;
                }
 
                while (elements[j].CompareTo(pivot) > 0)
                {
                    j--;
                }
 
                if (i <= j)
                {
                    // Swap
                    IComparable tmp = elements[i];
                    elements[i] = elements[j];
                    elements[j] = tmp;
 
                    i++;
                    j--;
                }
            }
 
            // Recursive calls
            if (left < j)
            {
                Quicksort(elements, left, j);
            }
 
            if (i < right)
            {
                Quicksort(elements, i, right);
            }
        }
 
    }
}

 

 

 

 

 

خروجی

 

z e x c m q a
a c e m q x z

نظرات  (۰)

هیچ نظری هنوز ثبت نشده است

ارسال نظر

ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
تجدید کد امنیتی