ترتیب دیں ضم کریںترتیب دیں ضم کریںعنوان:
ترتیب دیں ضم کریں
زبان:
سی
مصنف:
فلپ جے ایرڈلسکی
pje@efgh.com
http://www.alumni.caltech.edu/~pje/
تاریخ:
31 جولائی 1998
استعمال:
عوامی ڈومین؛ استعمال پر کوئی پابندی نہیں ہے
پورٹیبلٹی:
کوئی سی مرتب
مطلوبہ الفاظ:
ترتیب دیں
خلاصہ:
ایک فائل کو ترتیب دینے کے لئے ایک فنکشن ، صوابدیدی طور پر پڑھنے ، لکھنے اور موازنہ کرنے کے افعال اور ٹیپ انضمام الگورتھم کا استعمال کرتے ہوئے ، جو تمام معاملات میں O (n لاگ این) ہے۔ فنکشن ناقابل تسخیر اور دوبارہ داخل کرنے والا ہے۔
تقریب ولی_سورٹ () کالنگ پروگرام کے ذریعہ فراہم کردہ پڑھنے ، لکھنے اور موازنہ کرنے والے افعال کا استعمال کرتے ہوئے کسی بھی طرح کی فائل کو عملی طور پر ترتیب دے گی۔
یہ متغیر سائز کے ریکارڈ کو ترتیب دیتا ہے۔
اس کے لئے O (n log n) موازنہ کی ضرورت ہے ، جہاں n ابتدائی حکم سے قطع نظر ریکارڈوں کی تعداد ہے۔ کسی فائل کو ترتیب دینے کا وقت پیش قیاسی اور مستقل ہے۔ یہ کارکردگی عمومی قسم کے لئے بہترین سمجھی جاتی ہے۔
ریکارڈ کو کتنی بار پڑھنا چاہئے ، یا لکھنا پڑا ہے ، ایک ڈسک فائل بھی O (n لاگ n) ہے۔
الگورتھم تکراری ہے ، پنراورتی نہیں ، لہذا اسٹیک اوور فلو کا کوئی مسئلہ نہیں ہے۔ اسٹیک کی ضرورت پیش گوئ ، مستقل اور چھوٹی ہے۔
فائل کی دو کاپیاں رکھنے کے ل It اس میں لگ بھگ ڈسک اسپیس کی ضرورت ہے۔ ترتیب شدہ فائل اس جگہ میں رہ گئی ہے۔
اس میں تین ریکارڈ رکھنے کے لئے کم از کم کافی میموری کی ضرورت ہوتی ہے ، لیکن اگر یہ زیادہ میموری کے ساتھ فراہم کی جاتی ہے تو یہ تیزی سے چلے گا۔
یہ ایک وقت میں زیادہ سے زیادہ چار عارضی فائلیں بنانے کے ل t tmpfile () کہتا ہے۔
غیر ترتیب شدہ فائل کو تسلسل کے ساتھ پڑھا جاتا ہے ، اور ترتیب شدہ فائل ترتیب سے لکھی جاتی ہے۔ لہذا وہ ٹیپ ، I / O سلسلے یا دیگر سختی سے ترتیب والے آلات ہوسکتے ہیں۔
فنکشن کال مندرجہ ذیل ہے:
نتیجہ = ضم_سورٹ (غیر ترتیب شدہ_فائل ، ترتیب شدہ_فائل ، پڑھنا ، لکھنا ، موازنہ کرنا ،
پوائنٹر ، میکس_ ریکارڈ_ سائز ، بلاک_ سائز ، پی سیونٹ)؛
کالنگ پروگرام میں مندرجہ ذیل پیرامیٹرز کی فراہمی ضروری ہے۔
فائل * غیر ترتیب شدہ_فائل؛
فائل کو ترتیب دینے کے لئے ایک فائل پوائنٹر۔ فائل کو کامیابی کے ساتھ پڑھنے کے لئے کھول دیا گیا ہے ، اور فائل کے آغاز میں فائل پوائنٹر کو پوزیشن میں رکھنا چاہئے۔
فائل * ترتیب شدہ_فائل؛
ترتیب شدہ فائل کے لئے ایک فائل پوائنٹر۔ فائل کو تحریری طور پر کامیابی کے ساتھ کھول دیا گیا ہے ، اور فائل کے آغاز میں فائل پوائنٹر کو پوزیشن میں رکھنا چاہئے۔
int (* پڑھیں) ()؛
ایک فنکشن جو ایک ریکارڈ کو پڑھتا ہے۔
انٹ (* لکھنا) ()؛
ایک فنکشن جو ایک ریکارڈ لکھتا ہے۔
انٹ (* موازنہ) ()؛
ایک فنکشن جو دو ریکارڈوں کا موازنہ کرتا ہے۔
باطل * پوائنٹر؛
جب صارف بلایا جاتا ہے تو اسے (* پڑھیں) () ، (* لکھنا) () اور (* موازنہ) () افعال میں بھیجنا ہوتا ہے جب انہیں بلایا جاتا ہے۔
بغیر دستخط شدہ میکس_ریکارڈ_ سائز؛
ریکارڈ میں بائٹس کی زیادہ سے زیادہ تعداد ، جب اسے میموری میں پڑھا جاتا ہے۔ جب یہ فائل میں رہتا ہے تو ریکارڈ کے سائز کی طرح نہیں ہونا ضروری ہے۔
بغیر دستخط شدہ طویل بلاک_ سائز؛
میموری میں ترتیب دینے کے لئے ریکارڈوں کی تعداد ، یا 1L میموری میموریٹنگ اگر استعمال نہیں کرنا ہے۔
بغیر دستخط شدہ لمبا * محاسبہ؛
ریکارڈ گنتی (اگر ترتیب دینے میں کامیاب ہے) کو موصول کرنے کے لئے متغیر کی طرف اشارہ ، یا اگر اس معلومات کو واپس نہیں کرنا ہے تو NULL کریں۔
فنکشن مندرجہ ذیل اقدار کو واپس کرتا ہے:
INT نتیجہ؛
نتائج کا کوڈ:
0 ایک کامیاب ترتیب کے لئے
ناکافی میموری کے لئے 1
فائل بنانے میں خرابی کے ل for 2
3 فائل لکھنے میں غلطی کے ل
غیر ترتیب شدہ اور چھانٹی گئی فائلوں کو واپس نہیں کیا جائے گا یا بند نہیں کیا جائے گا۔ ہر فائل کو فائل کے اختتام پر رکھے جانے والے فائل پوائنٹر کے ساتھ ، کھلا چھوڑ دیا جائے گا۔ تاہم ، اگر دونوں فائل پوائنٹرز یکساں ہیں تو ، فائل کو دوبارہ سے لوٹا دیا جائے گا اور اس کے مطابق ترتیب شدہ ریکارڈ لکھے جائیں گے۔
(* پڑھیں) () فنکشن کوجرج_سورٹ () کے ذریعہ مندرجہ ذیل کہا جاتا ہے ، اور ہر بار جب بھی اسے ریکارڈ کیا جاتا ہے ایک ریکارڈ پڑھنا ضروری ہے (سوائے اس کے کہ جب غیر ترتیب شدہ فائل کا اختتام پتہ چلا ہو)۔
n = (* پڑھیں) (ایف پی ، بفر ، پوائنٹر)؛
فائل * ایف پی؛
غیر ترتیب شدہ فائل یا عارضی فائل کے ل t فائل پوائنٹر جو tmpfile () کال کرکے تیار کیا گیا ہے۔
باطل * بفر؛
ایک ریکارڈ حاصل کرنے کے لئے بفر کا اشارہ۔ یہ بفر زیادہ سے زیادہ میک_ ریکارڈ_سائز بائٹس رکھ سکتا ہے۔
باطل * پوائنٹر؛
اس اشارے کی ایک کاپی ملاوٹ_سورٹ () کی دلیل کے طور پر گزر گئی۔
انٹ این؛
ریکارڈ میں موجود بائٹس کی تعداد ، یا صفر اگر غیر ترتیب شدہ فائل کے آخر میں پڑھنے کی کوشش کی گئی ہو۔
جب یہ فنکشن صفر لوٹتا ہے تو ، اسے دوبارہ اسی فائل کے لئے نہیں بلایا جائے گا۔ عارضی فائل کے اختتام کو پڑھنے کی کوئی کوشش نہیں کی جائے گی۔
بیان کردہ زیادہ سے زیادہ سائز سے بڑا ریکارڈ کم کرنا یا کسی اور مناسب طریقے سے نمٹا جانا چاہئے۔ اگر تقریب میں بفر کو اوور فلو کی اجازت دی جاتی ہے ، یا اگر (* پڑھیں) () زیادہ سے زیادہ ریکارڈ سائز سے بڑی ہے تو بفر کو زیادہ بہہ جانے کی اجازت ہوگی۔
ریکارڈ فارمیٹ کو تبدیل کیا جاسکتا ہے جب اسے میموری میں پڑھا جاتا ہے ، بشرطیکہ:
تبدیلیاں (* لکھنا) () اور (* موازنہ) () افعال کے ساتھ مطابقت رکھتی ہیں ، اور
(* پڑھیں) () فنکشن کے ذریعہ لوٹی گئی قیمت ریکارڈ میں بائٹس کی تعداد ہونی چاہئے جبکہ یہ میموری بفر میں ہے۔
مثال کے طور پر ، DOS / Windows میں لائن ٹرمنیٹر \ r \ n میموری میں پڑھتے وقت اسے \ n میں تبدیل کیا جاسکتا ہے۔
(* لکھنا) () فنکشن کو مندرجہ ذیل کہا جاتا ہے ، اور جب بھی یہ کہا جاتا ہے ہر بار ایک ریکارڈ لکھنا ضروری ہے۔
n = (* لکھنا) (ایف پی ، بفر ، پوائنٹر)؛
فائل * ایف پی؛
ترتیب شدہ فائل یا عارضی فائل کیلئے tmpfile () کال کرکے فائل فائل پوائنٹر۔
باطل * بفر؛
میموری میں پڑھتے ہی ایک ریکارڈ رکھنے والے بفر کا اشارہ
(* پڑھیں) () کے ذریعہ میموری میں پڑھے جانے والے ایک بفر کا اشارہ ، جس میں ایک ریکارڈ ہے۔
باطل * پوائنٹر؛
اس اشارے کی ایک کاپی ملاوٹ_سورٹ () کی دلیل کے طور پر گزر گئی۔
انٹ این؛
ایک کامیاب تحریر کے لئے نانزورو؛ ناکافی ڈسک کی جگہ کے لئے صفر۔
نوٹ کریں کہ ریکارڈ کی لمبائی پیرامیٹر کے طور پر نہیں گزرتی ہے۔ اسے خود ریکارڈ میں یا کسی اور جگہ (* لکھنا) () فنکشن تک قابل رسائی ، واضح طور پر یا واضح طور پر موجود ہونا چاہئے۔
(* موازنہ) () فنکشن کو دو ریکارڈوں کا موازنہ کرنے کے لئے کہا جاتا ہے ، جیسا کہ:
n = (* موازنہ) (پی ، کیو ، پوائنٹر)؛
باطل * p؛
پہلے ریکارڈ پر مشتمل بفر کا اشارہ ، جیسا کہ (* پڑھیں) () کے ذریعہ میموری میں پڑھا جاتا ہے۔
باطل * ق؛
دوسرے ریکارڈ پر مشتمل بفر کی طرف اشارہ ، جیسا کہ (* پڑھیں) () کے ذریعہ میموری میں پڑھا جاتا ہے۔
باطل * پوائنٹر؛
اس اشارے کی ایک کاپی ملاوٹ_سورٹ () کی دلیل کے طور پر گزر گئی۔
انٹ این؛
موازنہ نتیجہ ، مندرجہ ذیل:
> 0 اگر * p ترتیب دیں تو * q کے بعد ہونا ہے
<0 اگر * p ترتیب دیں ترتیب میں * q سے پہلے ہونا ہے
0 اگر * p اور * q کا آرڈر غیر متعلقہ ہے
ترتیب مندرجہ ذیل ہے:
ریکارڈ غیر ترتیب شدہ فائل سے پڑھ کر بلاکس میں دو عارضی فائلوں کو لکھا جاتا ہے۔ ہر بلاک میں block_size دلیل کے ذریعہ بیان کردہ ریکارڈز کی تعداد ہوتی ہے (سوائے آخری بلاک کے ، جس میں کم ریکارڈ شامل ہوسکتے ہیں) ، اور عارضی فائل پر لکھنے سے پہلے اسے میموری سے ترتیب شدہ list_sort () کال کرکے میموری میں ترتیب دیا جاتا ہے۔
اس کے بعد عارضی فائلوں کو کئی پاسوں میں بلاکس کو ضم کرکے ترتیب دیا جاتا ہے۔ ہر پاس میں ، دو سورس فائلوں کے بلاکس کو دو بار سے زیادہ ریکارڈ رکھنے والے بلاکس میں ضم کیا جاتا ہے ، اور دو آؤٹ پٹ فائلوں پر لکھا جاتا ہے۔ یہ عمل اس وقت ختم ہوتا ہے جب بلاک کا سائز فائل کے سائز کے برابر یا اس سے زیادہ ہوجاتا ہے اور تمام ریکارڈ ایک ہی فائل میں ہوتے ہیں ، جو ترتیب شدہ فائل ہے۔
اگر ناکام ہوسکتا ہے تو اس طرح
malloc () پر کال کال کو NULL واپس کردیتی ہے کیونکہ کافی میموری موجود نہیں ہے ، یا
tmpfile () پر کال کال کو NULL واپس کردیتی ہے کیونکہ بہت ساری فائلیں کھلی ہوئی ہیں ، یا
کال پر (* لکھنا) () صفر لوٹتا ہے کیونکہ ڈسک کی ناکافی جگہ نہیں ہے۔
چاہے یہ ترتیب کامیاب ہے یا نہیں ، تمام مختص شدہ میموری بلاکس کو ختم کردیا جائے گا ، اور تمام عارضی فائلیں بند اور حذف ہوجائیں گی۔ اگر ترتیب ناکام ہوجاتی ہے تو ، غیر ترتیب شدہ اور ترتیب شدہ فائلوں کے لئے فائل پوائینٹرز جہاں کہیں بھی ہو باقی رہ جائیں گے۔
اگر ان افعال کو کہتے ہیں تو وہ مرجع ہیں:
(* موازنہ) ()
fclose ()
مفت ()
malloc ()
میمسی ()
(* پڑھیں) ()
رائیونڈ ()
tmpfile ()
(* لکھیں) ()
ڈاس / ونڈوز کے تحت ، tmpfile () ایک BINARY فائل بناتا ہے۔ تاہم ، اس سے عام طور پر کوئی پریشانی پیدا نہیں ہوتی ہے ، چاہے غیر ترتیب شدہ اور ترتیب شدہ فائلیں ٹیکسٹ فائلیں ہوں ، کیوں کہ ڈاس / ونڈوز تبادلوں کو مستقل طور پر ہینڈل کرتے ہیں۔
اگر ڈسک کی جگہ انتہائی تنگ ہے تو ، ترتیب شدہ فائل کے زیر قبضہ جگہ استعمال کرنے کے لئے ترتیب میں ترمیم کی جاسکتی ہے۔ غیر ترتیب شدہ فائل ، عارضی فائلیں ، اور ترتیب شدہ فائل پھر کسی ایسی جگہ میں فٹ ہوسکتی ہے جس کی ترتیب ان فائل کی شکل سے دگنی ہے۔ اس ترمیم کے ل، ، غیر ترتیب شدہ فائل کو پڑھنے کے بعد اسے حذف کرنے کے لئے صرف کوڈ داخل کریں۔ نوٹس کریں کہ اگر یہ تکنیک استعمال کی گئی ہے تو ، ترتیب شدہ اور غیر ترتیب شدہ فائلیں مختلف ہونی چاہئیں ، اور یہ کہ بحث کو منتقل کرنے کا ڈھانچہ قدرے کم خوبصورت ہوسکتا ہے کیونکہ فائل کو حذف کرنے کے لئے فنکشن کال میں عام طور پر فائل کی وضاحت کی ضرورت ہوتی ہے ، محض فائل پوائنٹر کی ضرورت نہیں ہوتی ہے۔
मर्ج_سورٹ () فنکشن مستحکم نہیں ہے۔ یعنی ، یہ دو ریکارڈوں کے متعلقہ عہدوں کو محفوظ نہیں رکھتا ہے جس کے لئے (* موازنہ) () فنکشن صفر لوٹاتا ہے۔ فنکشن اسٹیبل_ ڈرم_سورٹ () میں یہ پراپرٹی ہے۔ تاہم ، اضافی خصوصیت کی قیمت ہوتی ہے: یاد میں یا عارضی فائل میں ہونے کے دوران ہر ریکارڈ میں چار بائٹ ریکارڈ نمبر شامل کیا جاتا ہے۔ اگر ریکارڈز چھوٹے ہوں تو یہ کافی مقدار میں ، ڈسک اور میموری کی ضروریات کو بڑھاتا ہے۔
SORT کی افادیت مستحکم_ ڈوبی_سورٹ () کے استعمال کی وضاحت کرتی ہے۔ یہ ایک DOS یا UNIX فلٹر ہے جو ٹیکسٹ فائل کی لائنوں کو ترتیب دیتا ہے۔ زیادہ سے زیادہ لائن کی لمبائی MAX_LINE حروف ہے ، جس میں ہر لائن کے آخر میں کیریج ریٹرن اور لائن فیڈ شامل نہیں ہے۔ افادیت ترتیب کو ختم کردے گی اور خرابی کے پیغام کو ڈسپلے کرے گی اگر اس میں MAX_LINE حروف سے زیادہ حرف والی کوئی لکیر پڑھی جائے۔ MAX_LINE کی قدر 255 رکھی گئی ہے ، لیکن افادیت کو دوبارہ مرتب کرکے اسے تبدیل کیا جاسکتا ہے۔
افادیت کو مندرجہ ذیل کہا جاتا ہے:
SORT <غیر ترتیب شدہ_فائل> چھانٹ گئی_فائل M N
ترتیب میں کالم نمبر M تا N شامل ہیں ، شامل ہیں ، جہاں بائیں طرف کا کالم نمبر صفر ہے۔ اگر N کو چھوڑ دیا جاتا ہے تو ، ترتیب میں کالم M اور اس کے دائیں طرف تمام کالم شامل ہیں۔ اگر M اور N دونوں کو چھوڑ دیا جاتا ہے تو ، تمام کالم ترتیب میں استعمال ہوتے ہیں۔
ایک قطار N + 1 سے کم کالموں پر مشتمل ہے جیسے اس کے دائیں سرے پر نالوں سے بھرے ہوئے ہوں۔
کرداروں کو ان کے ASCII کوڈ کے ذریعہ درجہ بندی کیا جاتا ہے ، جسے UNSIGNED بائٹس کے طور پر سمجھا جاتا ہے۔
یہ پیکیج ایک اور پیکیج پر کال کرتا ہے:
منسلک فہرست میموری ترتیب
متن کی شکل میں ماخذ کوڈ:
انضمام
ڈوبنا
ترتیب