Qsort
qsort تابعی در کتابخانه استاندارد سی است که یک الگوریتم مرتبسازی چندریختی را پیادهسازی میکند و به کمک آن میتوان آرایهای از اشیاء دلخواه را با استفاده از یک تابع مقایسه که توسط خود برنامهنویس تعریف میشود، مرتب کرد. نام این تابع از روی الگوریتم quicker sort (گونهای از الگوریتم مرتبسازی سریع) گرفته شده است که در ابتدا در کتابخانه سی یونیکس پیادهسازی شده بود.
چندریختی در تابع qsort، با استفاده از گرفتن یک اشارهگر به تابعی که عمل مقایسه سهجانبه را انجام میدهد و همینطور با گرفتن اندازه هر عضو موجود در آرایه مورد نظر پیادهسازی میشود. استاندارد سی ایجاب میکند که تابع مقایسه ترتیب خطی بر روی عناصر موجود در آرایه ورودی ایجاد کند.
در نسخه ۳ یونیکس که در سال ۱۹۷۳ منتشر شد، یک تابع qsort وجود داشت اما این تابع در آن هنگام یک زیرروال به زبان اسمبلی بود نه به زبان سی. یک نسخهٔ سی از این تابع با رابطی مشابه همان رابطی که در کتابخانه استاندارد وجود دارد در نسخه ۶ یونیکس به کار گرفته شد. این تابع در سال ۱۹۸۳ در برکلی بازنویسی شد و در نهایت در سال ۱۹۸۹ توسط کمیته آنسی سی استاندارد شد.
مثال
مثال زیر نشان میدهد که چگونه میتوان آرایهای از عناصر int را با استفاده از qsort مرتب کرد:
#include <stdlib.h>
/* Comparison function. Receives two generic (void) pointers. */
int compare(const void *p, const void *q)
{
int x = *(const int *)p;
int y = *(const int *)q;
/* to avoid undefined behaviour through signed integer overflow,
avoid: return x - y; */
int ret;
if (x == y)
ret = 0;
else
ret = (x < y) ? -1 : 1;
return ret;
}
/* Sort an array of n integers, pointed to by a. */
void sort_ints(int *a, size_t n)
{
qsort(a, n, sizeof(int), compare);
}
منابع
Wikipedia contributors. Qsort. Wikipedia, The Free Encyclopedia. February 13, 2015, 18:46 UTC. Available at: http://en.wikipedia.org/w/index.php?title=Qsort&oldid=646986838. Accessed February 17, 2015.
Content Disclaimer
Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.
- The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
- There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
- It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
- Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
- Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.