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.