ایک پروگرامنگ کے طریقہ کار کے طور Quicksort

1960 میں، K. A. Hoar، معلومات کے تیزی سے چھانٹ رہا ہے کے لئے ایک طریقہ تیار سب سے زیادہ مشہور ہو گیا. آج یہ وسیع پیمانے پر، پروگرامنگ میں استعمال کیا جاتا ہے اس کے مثبت خصوصیات میں سے ایک بہت کچھ ہے کہ: یہ عام مقدمات کے لئے استعمال کیا جا سکتا، یہ فہرستوں کی مختلف اقسام کے ساتھ مطابقت رکھتا ہے اور لاگو کرنے کے لئے آسان اضافی یاد میں ایک چھوٹا سا اضافہ کی ضرورت ہے. کا استعمال کرتے ہوئے کام کی غلطیوں کی ایک بہت کی اجازت دی ہے، اور یہ کسی حد تک غیر مستحکم ہے لیکن Quicksort ہے جس میں خرابیوں ہیں.

تاہم، یہ سب سے زیادہ تعلیم حاصل کی ورژن ہے. پہلی ادائیگی Hoare کے بعد، بہت سے اس کے گھنے مطالعہ کرتے ہیں. بڑی بیس ہے جس میں عملی ثبوت کی طرف سے underpinned نوکری، پر خرچ وقت کو تلاش کرنے کے نظریاتی سوالات پر قائم کیا گیا تھا. بنیادی الگورتھم اور اضافہ کی رفتار کو بہتر بنانے کے اصلی تجاویز تھیں.

Quicksort یہ ہر جگہ پایا جا سکتا ہے، بہت عام ہے. اس کی بنیاد پر طریقہ کار TList.Sort، تمام ورژن (سوائے 1) Delphi کے، یہ سی میں qsort مکمل کرنے کے لئے، ++ لیا وقت کی لائبریری تقریب میں موجود لاگو کیا جاتا ہے.

آپریشن کے بنیادی اصول ایک "تقسیم کرو اور فتح" کے طور پر تیار کیا جا سکتا ہے. یہ دو گروپوں میں فہرست توڑنے وقت ہوتی ہے اور خود کی طرف سے ہر حصے کے لئے حل کر رہے ہیں. ایک بنیاد کے عنصر کی طرف سے مقرر کیا جاتا ہے اور نسبتا ان کی پوری فہرست rearranged کیا گیا ہے: اس سے زیادہ توجہ علیحدگی کے عمل، مندرجہ ذیل اس وقت ہوتی ہے جس کے دوران میں ادا کیا جاتا ہے کہ کیا جانا چاہئے مندرجہ ذیل ہے. امیدواروں کے ایک گروپ کے بائیں تعمیر، قدر جس کی دیگر تمام کی منتقلی کے قوانین کے مقابلے میں کم ہے. اس کے مطابق فہرست میں اہم عنصر اس کی مناسب جگہ میں ہے کہ باہر کر دیتا ہے. اگلے مرحلے - بیس رشتہ دار عناصر کے دونوں اطراف کے لئے ایک چیلنج پنراورتی چھنٹائی کام کرتا ہے. ایسا لگتا ہے کہ حل کیا جا کرنے کے لئے ہے، عمل کی فہرست میں صرف ایک عنصر پر مشتمل ہے صرف اس صورت میں کام کرتا ہے ختم ہو جاتی ہے. اس طرح، ایک فوری چھانٹیں کے طور پر ایک پروگرامنگ کی تقریب میں مہارت حاصل کرنے کے لئے، یہ ضروری نچلے درجے کی یلگوردمز کا کام جاننے کی ہے: ایک) بیس رکنی کا انتخاب؛ ب) سب سے زیادہ مؤثر کی Permutation کی ایک فہرست چھوٹے اور بڑے اقدار کے ساتھ دو سیٹ پیدا کرنے کے لئے.

پہلی اصولوں سے واقف کریں. بیس رکنی انتخاب کرتے وقت، مثالی طور پر اوسط کی فہرست میں سے منتخب کیا جانا چاہئے. اس کے بعد وقفے پر دو برابر حصوں میں تقسیم کیا جاتا ہے. بس کا حساب اوسط قیمت کی فہرست میں بہت مشکل ہے، تو بھی سب سے تیز چھنٹائی اس حسابان طرف بائ پاس. لیکن زیادہ سے زیادہ یا کم از کم قیمت کے ساتھ بنیادی عنصر کے انتخاب - بھی نہیں بہترین آپشن. صورت میں ایک کی طرح عزم خالی فہرستوں کی ضمانت دی جائے گی، اور دوسرا مکمل تخلیق کرتا ہے. لہذا یہ نتیجہ نکالا بیس رکن کے طور پر اوسط سے قریب ہے کہ کسی ایک کو منتخب کیا جانا چاہئے، لیکن زیادہ سے زیادہ اور کم سے کم ہے.

کسی ایک کا انتخاب مقرر کیا جاتا ہے ایک بار، آپ سڑن الگورتھم پر آگے بڑھنے کر سکتے ہیں. یہ اندرونی تکمے فوری چھانٹیں نام نہاد. سب کچھ دو ریپڈ رسائی اشاریہ جات پر بنایا گیا ہے: پہلا، عناصر اس کے برعکس، دائیں، دوسرا بائیں سے زیادہ جانا دائیں سے بائیں سے. شروع ہوتا آپریشن پر عملدرآمد کا حق: انڈیکس فہرست پر ہے اور اہم کو تمام قیمتوں کا آپس میں موازنہ. عنصر بنیادی سے کم یا برابر ہے جب سائیکل مکمل ہے. یہ ایک موازنہ نہیں ہے اور شہادت کی قدر میں کمی واقع ہوتی ہے. بائیں ہاتھ کا کام زیادہ یا برابر قدر زیادہ ختم ہو گیا ہے جب. یہاں، مقابلے کی قدر میں اضافہ.

quicksort مشتمل ہے جس میں علیحدگی الگورتھم کے اس مرحلے میں، دو حالات پیدا ہو سکتی ہے. پہلے بائیں طرف انڈیکس صحیح سے کم ہے کہ ہے. یہ خامی کی طرف اشارہ کرتا ہے، پھر عناصر جس پر یہ فہرست میں بیان کیا گیا تھا غلط حکم میں ہیں موجود ہیں. پیداوار - ان مقامات میں تبدیلی. جب کالم دونوں کے برابر یا اس سے تجاوز کر جاتا ہے دوسری صورت حال ہے. اس فہرست میں ایک کامیاب علیحدگی طرف اشارہ کرتا ہے، یہ ہے کہ، کام اب مکمل ہے.