مرتب سازی در C++

این یک تابع عمومی در کتابخانهٔ استاندارد ++C برای انجام مرتب‌سازی مقایسه‌ای است. این تابع از کتابخانه الگوی استاندارد (STL) نشأت می‌گیرد.

الگوریتم مرتب‌سازی ویژه بوسیله استاندارد زبانی اجباری نیست و ممکن است در اجراهای مختلف، متفاوت باشد؛ اما پیچیدگی زمانی مجانبی تابع مشخص است: فراخوانی برای مرتب‌سازی باید مقایسه ((O(N*log(N را در زمانی که برای طیفی از عناصر N اعمال می‌شود را اجرا کند.

کاربرد

این تابع از سرتیتر

header<algorithm>

از کتابخانه استاندارد C + + استفاده می کند و سه آرگومان دارد:

- پیمایشگر دسترسی تصادفی (Random Access Iterator) اول : first

- پیمایشگر دسترسی تصادفی (Random Access Iterator) آخر:

last

- مقایسه گر: comp

در اینجا، دو متغیر first و last یک نوع قالب بندی است که باید یک پیمایشگر دسترسی تصادفی باشند، و first و last باید یک توالی از مقادیر را تعریف کنند، یعنی عنصر انتها (last) با استفاده مکرر از عملگر افزایش باید قابل دسترسی باشد. آرگومان سوم، همچنین از نوع قالب بندی، بیانگر یک گزاره مقایسه است. این گزاره مقایسه باید یک دستور بسیار ضعیف را برای عناصر متوالی است که باید مرتب شوند را تعریف کند. آرگومان سوم اختیاری است.اگر گزاره سومی در کار نبود , عملیات "کوچکتر "(>) استفاده می شود که در زبان c++ به اصطلاح "پربار" شده است.

این کد از انواع اعداد صحیح (به ترتیب صعودی)استفاده کرده و آن را چاپ می‌کند. تبدیل به آرایه به صورت iterators عمل می‌کند.

#include <algorithm>
#include <iostream>
using namespace std;
int main() {
  int array[] = { 23, 5, -10, 0, 0, 321, 1, 2, 99, 30 };
  size_t size = sizeof(array) / sizeof(array[0]); 
  sort(array, array + size);
  for (size_t i = 0; i < size; ++i) {
     cout << array[i] << ' ';
  }
  cout << endl;
}

همان عملکرد با استفاده از یک ظرف برداری، با استفاده از روش شروع و پایان آن برای بدست آوردن iterators:

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main() {
  vector<int> vec { 23, 5, -10, 0, 0, 321, 1, 2, 99, 30 };
  sort(vec.begin(), vec.end());
  for (int i = 0; i < vec.size(); ++i) {
     cout << vec[i] << ' ';
  }
  cout << endl;
}

کلیت

به طور کلی مشخص شده‌است، به طوری که می‌تواند روی هر کانتینر دسترسی تصادفی و هر روش تعیین این که یک عنصر x از چنین ظرفی باید قبل از عنصر دیگری y قرار داده شود، کار کند.

اگر چه بطور کلی مشخص‌شده، به راحتی در تمام مشکلات مرتب‌سازی اعمال نمی‌شود. یک مساله خاص که موضوع مورد مطالعه قرار گرفته‌است موارد زیر است:

اجازه دهید A و B دو آرایه باشند، که در آن رابطه بین عنصر A [ i ] و عنصر B [ i ] برای تمام شاخص‌های معتبر i وجود دارد.

مرتب‌سازی A در حالی که رابطه با B را حفظ می‌کند، به عنوان مثال، همان جایگشت مشابه B را اعمال می‌کند.

کار قبلی را بدون کپی کردن عناصر A و B به آرایه جدیدی از جفت، مرتب‌سازی و انتقال عناصر به آرایه اصلی انجام دهید (که به فضای موقت O (n)نیاز دارد.

یک راه‌حل برای این مسئله به وسیله آ.ویلیامز در سال 2002 پیشنهاد شده‌است ، که یک نوع پیمایشگر سفارشی برای جفت آرایه اجرا کرد و برخی از مشکلات موجود در اجرای صحیح این نوع پیمایشگر را مورد بررسی قرار داد. راه‌حل ویلیامز به وسیله کی.اولاندر مطالعه و اصلاح شد.

پیوند به بیرون

• C++ reference for std::sort
• Another C++ reference for std::sort