راهنماییی در مورد الگوریتم های مرتب سازی به روش حبابی و quik sort ؟؟؟

سلام
دوستان اگه هر کدومتون الگوریتم های مرتب سازی به روش های حبابی QUIK SORT و بلده بگه و یه برنامه هم در این دو مورد بنویسید .:10: مرتب سازی کویک سرت رو حتما توضیح بدید !

دوست من به اینجا یه سر بزن ببین به دردت می خوره

کد:

---

http://vbnet.mvps.org/index.html?code/sort/qsoverview.htm

---

:20:

اینم الگوریتم خوکشل quicksort به زبان جاوا:


کد:

کد:

---

void quicksort (int[] a, int lo, int hi){// lo is the lower index, hi is the upper index// of the region of array a that is to be sorted int i=lo, j=hi, h; int x=a[(lo+hi)/2]; // partition do { while (a[i]<x) i++; while (a[j]>x) j--; if (i<=j) { h=a[i]; a[i]=a[j]; a[j]=h; i++; j--; } } while (i<=j); // recursion if (lo<j) quicksort(a, lo, j); if (i<hi) quicksort(a, i, hi);}

---

---------------------------------------------------------------------------------------
تحلیل الگوریتم:
بهترین حالت برای الگوریتم quicksort زمانی است که در هر مرحله از تقسیم لیست به دو بخش , دو بخش با اندازه مساوی تولید بشن.در این حالت برای مرتب کردن n عنصر , زمان اجرا برابر:

کد:
O(n log(n))
به علت اینکه عمق بازگشتی برابر log(n) است و توی هر مرحله با n تا عنصر سروکار داریم.توی شکل قسمت a رو ببینید(یادتون باشه که فرض کردیم یه حالت خاص رخ بده که توی هر مرحله بازگشتی اندازه لیست هایی که تشکیل میشن برابر باشه)
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]

بدترین زمان اجرای این الگوریتم وقتی اتفاق میفته که در هر مرحله بازگشتی یک تکه نامتقارن تولید بشه , یعنی اینکه یه بخش فقط شامل یه عنصر باشه و بخش دیگه شامل بقیه عناصر باشه(شکل بالا قسمت c).که توی این وضعیت عمق بازگشتی n-1 میشه و زمان اجرای الگوریتم برابر:

کد:
O(n^2)
بطور معمول ما انتظار داریم قسمت بندی بصورت ی باشه که توی (شکل بالا b )نمایش داده شده.


توی quicksort انتخاب pivot موفقیت عمل قسمت بندی رو تضمین میکنه.
فرض کنید که اولین عنصر لیست به عنوان pivot انتخاب بشه.این مسیله میتونه ما رو به سمت بدترین حالت برای الگوریتم سوق بده در صورتیکه لیست از همون ابتدا نسبتاً مرتب باشه (یا بطور معکوس مرتب باشه), این کار باعث میشه که تقریبا تمام عناصر یا در smaller than pivot قرار بگیرن یا در larger than pivot که این عمل همونطوری که بحث شد زمان اجرا رو بالا میبره.
یک روش متداول که برای انتخاب pivot بکار گرفته میشه , روش median-of-three یا "میانگین سه" هست. توی این روش میانگین عنصر اول ,عنصر میانی و عنصر آخر هر لیست بعنوان pivot در اون لیست انتخاب میشه که معمولا به عنصر وسط لیست نزدیکتره.و باعث میشه پیچیدگی زمانی الگوریتم کم بشه.

یه مشکل دیگه که توی الگوریتم های بازگشتی باهاش سروکار داریم پیچیدگی فضا برای پشته فراخوانی هاست.بطوریکه هر چی عمق بازگشتی بیشتر باشه , پشته بزگتره.یه راه حل برای این مسیله اینه که بجای اینکه در هر مرحله همیشه لیست سمت چپ رو انتخاب کنیم , اول لیست کوچیکتر رو مرتب میکنیم .این عمل از عمق بازگشتی و سربار ناشی از بازگشتی میکاهد.

---------------------------------------------------------------------------------------------------------------------------
البته یه توضیح اونم اینکه اینا با یه سرچ کوچولو به دست اومده و کاملا کپی هستن [ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]

و این یکی هم که دیگه خود vb هست

کد:

---

Option Explicit ' a position, which is *hopefully* never used:Public Const N_POS = -2147483648# Public Sub Swap(ByRef Data() As Variant, _                Index1 As Long, _                Index2 As Long) 
 If Index1 <> Index2 Then     
 Dim tmp As Variant     
  If IsObject(Data(Index1)) Then 
          Set tmp = Data(Index1)     
 Else 
        tmp = Data(Index1)       
End If
        If IsObject(Data(Index2)) Then
          Set Data(Index1) = Data(Index2)
        Else 
          Data(Index1) = Data(Index2)
      End If
        If IsObject(tmp) Then
          Set Data(Index2) = tmp
      Else
          Data(Index2) = tmp
      End If
        Set tmp = Nothing
  End IfEnd Sub Public Sub QuickSort(ByRef Data() As Variant, _                 
  Optional ByVal Lower As Long = N_POS, _                 
  Optional ByVal Upper As Long = N_POS)
  If Lower = N_POS Then     
  Lower = LBound(Data) 
 End If   
 If Upper = N_POS Then
      Upper = UBound(Data)   
End If 
  If Lower < Upper Then     
 Dim Right As Long
      Dim Left  As Long
        Left = Lower + 1
      Right = Upper + 1
        Do While Left < Right 
      If Data(Left) <= Data(Lower) Then
              Left = Left + 1     
      Else 
            Right = Right - 1
 
  Swap Data, Left, Right 
  End If 
    Loop
    Left = Left - 1 
    Swap Data, Lower, Left
    QuickSort Data, Lower, Left - 1 
    QuickSort Data, Right, Upper
    End If
End Sub

---

و البته تو این سایت این الگوریتم به زبانهای مختلف برنامه نویسی وجود داره:

کد:

---

http://en.wikibooks.org/wiki/Algorithm_implementation/Sorting/Quicksort

---

از اونجایی که کد یه مقدار بهم ریخت فکر کنم به سایت مراجعه کنید بهتر باشه...
اینم فارسیش

کد:

---

http://fa.wikipedia.org/wiki/%DA%A9%D9%88%DB%8C%DB%8C%DA%A9%E2%80%8C%D8%B3%D9%88%D8%B1%D8%AA

---

اینم جالب بود

کد:

---

http://www.mycsresource.net/articles/programming/sorting_algos/quicksort/

---

و البته این یکی از هم جالب تر

کد:

---

http://forum.p30world.com/showthread.php?t=20199

---