یکی از مشکلات استفاده از تابع sort‎ برای مرتب کردن عناصر این است که اگر عناصر ما از ساختاری باشند که داده‌های زیادی در آن ذخیره شده، عملیّات مرتب کردن کند می‌شود، چون یکی از اعمالی که در تابع ‎sort‎ انجام می‌شود، جابه‌جا کردن دو عنصر است؛ موقعی که تعداد بایت‌های هر کدام از اشیایی‎ که از ساختار تعریف کرده‌ایم زیاد باشد این عمل زیاد طول می‌کشد، یک روش خوب این است که اشاره‌گرهایی‎ به اشیا نگه داریم، سپس یک تابع برای مقایسه‌ی اشیایی که دو اشاره‌گر به آنها اشاره می‌کنند بنویسیم و از آن برای مرتب کردن اشیا استفاده کنیم. ساختار زیر را در نظر بگیرید:

‎struct student{‎
   ‎double height‎, ‎mean;‎
   ‎int weight,ncourse;‎
‎};‎

متغیّر ‎height‎ نشان‌دهنده‌ی قد یک دانشجو، ‎weight نشان‌دهنده‌ی وزن یک دانشجو، ‎mean نشان‌دهنده‌ی معدل یک دانشجو و ‎ncourse‎ نشان‌دهنده‌ی تعداد درس‌هایی‌است که او تا به‌حال گذرانده است‎.

‎ برنامه‌ای بنویسید که اعمال زیر را انجام دهد.

• ‎ یک عدد ‎$n$‎ از ورودی بخواند، یک آرایه به طول ‎$n$‎ عنصر به نام ‎$a$‎ در فضای ‎heap‎ بسازد. ‎
• برای هر کدام از ‎$n$‎ شیء موجود در آرایه چهار مشخصه‌ی آن دانشجو را از ورودی استاندارد بخواند.
• یک آرایه‌ی دیگر به نام ‎$b$‎ از نوع اشاره‌گر به ‎student‎ تعریف کنید و اشاره‌گر به ‎$n$‎ دانشجو را در آن ذخیره کنید.
• یک تابع برای مقایسه‌ی دو اشاره‌گر به ‎student‎ تعریف کنید، این تابع بایستی بگونه‌ای باشد که در پایان اشاره‌گر به دانشجوها ابتدا بر حسب معدل‌هاشان و در صورت تساوی معدّل‌ها بر حسب تعداد درس‌های گذرانده شده توسط آن‌ها مرتب شده باشند.
• اشاره‌گرهای موجود در آرایه‌ی ‎$b$‎ را با استفاده از تابع بالا و تابع sort‎ مرتب کنید، سپس با استفاده از ترتیب اشاره‌گرهای موجود در ‎$b$‎، اشیای موجود در آرایه‌ی ‎$a$‎ را در زمان ‎$O(n)$‎ مرتب کنید، شما می‌توانید برای انجام این کار از حافظه‌ی اضافی حداکثر ‎$O(n)$‎ استفاده کنید.

• سوال قبل