زبان سلام
ویرایشگر آنلاین

کتابخانه‌ی استاندارد · عدد و مجموعه

مرتب سازی sort

مرتب کردن وکتورها با مقایسه‌ی پیش‌فرض یا دلخواه، جستجوی دودویی و ده‌ها الگوریتم مرتب‌سازی برای یادگیری.

واردسازی مرتب سازی
در این صفحه
  1. روال‌ها

برای بیشتر کارها همین دو روال کافی‌اند: مرتب برای عددها و رشته‌ها، و مرتب سازی با وقتی خودتان تعیین می‌کنید چه چیزی «کوچک‌تر» است؛ مثلاً دانشجوها بر اساس نمره.

روال‌های با نام الگوریتم (سریع، ادغامی، حبابی و…) همه یک کار می‌کنند و نتیجه‌شان یکی است. بیشترشان برای آموزش و مقایسه‌ی الگوریتم‌ها آمده‌اند. مرتب خودش یک الگوریتم سریع و مطمئن انتخاب می‌کند.

روال‌هایی که نامشان «شده» دارد (مرتب شده) یک وکتور تازه برمی‌گردانند و وکتور اصلی را تغییر نمی‌دهند؛ بقیه خود وکتور را مرتب می‌کنند.

روال‌ها

مرتب سازی هرمی HeapSort

روال مرتب سازی هرمی<T>(v: وکتور<T>)
مرتب‌سازی هرمی؛ همیشه سریع (n log n) و بدون حافظه‌ی اضافه.
sort-Algorithms.salam
واردسازی مرتب سازی

روال ریشه:
    داده := [۹، ۴، ۷، ۱، ۸، ۲، ۶، ۳، ۵، ۰]
    تکرار ۱۳ در ر:
        ناپایا و۱ := وکتور {} برگردان وکتور<صحیح>
        هر ع در داده:
            و۱.بیفزا(ع)
        پایان
        ترابرد ر:
            ۰: مرتب سازی.مرتب سازی سریع(و۱) بشکن پایان
            ۱: مرتب سازی.مرتب سازی ادغامی(و۱) بشکن پایان
            ۲: مرتب سازی.مرتب سازی هرمی(و۱) بشکن پایان
            ۳: مرتب سازی.مرتب سازی درجی(و۱) بشکن پایان
            ۴: مرتب سازی.مرتب سازی درجی دودویی(و۱) بشکن پایان
            ۵: مرتب سازی.مرتب سازی انتخابی(و۱) بشکن پایان
            ۶: مرتب سازی.مرتب سازی حبابی(و۱) بشکن پایان
            ۷: مرتب سازی.مرتب سازی شل(و۱) بشکن پایان
            ۸: مرتب سازی.مرتب سازی شانه ای(و۱) بشکن پایان
            ۹: مرتب سازی.مرتب سازی کوکتلی(و۱) بشکن پایان
            ۱۰: مرتب سازی.مرتب سازی حلزونی(و۱) بشکن پایان
            ۱۱: مرتب سازی.مرتب سازی زوج فرد(و۱) بشکن پایان
            ۱۲: مرتب سازی.مرتب سازی پنکیکی(و۱) بشکن پایان
        پایان
        چاپ مرتب سازی.مرتب است(و۱)، ""
        و۱.آزادکن()
    پایان
    سرچاپ ""
    ناپایا د := وکتور {} برگردان وکتور<صحیح>
    دیرکن د.آزادکن()
    هر ع در داده:
        د.بیفزا(ع)
    پایان
    مرتب سازی.مرتب سازی درون نگر(د)
    سرچاپ د
پایان
خروجیtrue true true true true true true true true true true true true [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

مرتب سازی شمارشی CountingSort

روال مرتب سازی شمارشی(v: وکتور<صحیح>)
مرتب‌سازی شمارشی برای عددهای صحیح؛ وقتی بازه‌ی عددها کوچک است، بسیار سریع است.
sort-IntSorts.salam
واردسازی مرتب سازی

روال ریشه:
    تکرار ۳ در ر:
        ناپایا و۱ := وکتور {} برگردان وکتور<صحیح>
        دیرکن و۱.آزادکن()
        هر ع در [۱۷۰، ۴۵، ۷۵، ۹۰، ۸۰۲، ۲۴، ۲، ۶۶]:
            و۱.بیفزا(ع)
        پایان
        اگر ر == ۰:
            مرتب سازی.مرتب سازی مبنایی(و۱)
        وگرنه ر == ۱:
            مرتب سازی.مرتب سازی شمارشی(و۱)
        وگرنه:
            مرتب سازی.مرتب سازی سطلی(و۱)
        پایان
        سرچاپ و۱
    پایان
پایان
خروجی[2, 24, 45, 66, 75, 90, 170, 802] [2, 24, 45, 66, 75, 90, 170, 802] [2, 24, 45, 66, 75, 90, 170, 802]

جستجوی دودویی BinarySearch

روال جستجوی دودویی<T>(v: وکتور<T>، x: T): صحیح
جای x را در وکتور مرتب با جستجوی دودویی پیدا می‌کند؛ اگر نباشد، منفی یک.
sort-BinarySearch.salam
واردسازی مرتب سازی

روال ریشه:
    ناپایا عددها := وکتور {} برگردان وکتور<صحیح>
    دیرکن عددها.آزادکن()
    هر ع در [۱، ۳، ۳، ۳، ۷، ۹]:
        عددها.بیفزا(ع)
    پایان
    سرچاپ مرتب سازی.جستجوی دودویی(عددها، ۷)، مرتب سازی.جستجوی دودویی(عددها، ۴)
    سرچاپ مرتب سازی.کران پایین(عددها، ۳)، مرتب سازی.کران بالا(عددها، ۳)
پایان
خروجی4 -1 1 4

کران پایین LowerBound

روال کران پایین<T>(v: وکتور<T>، x: T): صحیح
نخستین جایی که عضوش کمتر از x نیست؛ جایی که x باید درج شود تا وکتور مرتب بماند.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: sort-BinarySearch.salam

کران بالا UpperBound

روال کران بالا<T>(v: وکتور<T>، x: T): صحیح
نخستین جایی که عضوش بزرگ‌تر از x است. فاصله‌ی کران بالا و پایین، تعداد تکرارهای x است.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: sort-BinarySearch.salam

مرتب سازی شل ShellSort

روال مرتب سازی شل<T>(v: وکتور<T>)
مرتب‌سازی شل؛ نسخه‌ی سریع‌تر درجی.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: sort-Algorithms.salam

مرتب سازی با SortBy

روال مرتب سازی با<T>(v: وکتور<T>، less: روال(T، T): منطقی)
وکتور را با تابع مقایسه‌ی less مرتب می‌کند؛ less(a، b) باید درست برگرداند اگر a باید پیش از b بیاید.
sort-SortBy.salam
واردسازی مرتب سازی

ساختار دانشجو:
    همگانی نام: رشته = ""
    همگانی نمره: صحیح = ۰
پایان

روال ریشه:
    ناپایا کلاس := وکتور {} برگردان وکتور<دانشجو>
    دیرکن کلاس.آزادکن()
    کلاس.بیفزا(دانشجو { نام = "سارا"، نمره = ۱۸ })
    کلاس.بیفزا(دانشجو { نام = "علی"، نمره = ۱۵ })
    کلاس.بیفزا(دانشجو { نام = "رضا"، نمره = ۱۸ })
    کلاس.بیفزا(دانشجو { نام = "مریم"، نمره = ۲۰ })
    بیشتر := (الف: دانشجو، ب: دانشجو) => الف.نمره > ب.نمره
    مرتب سازی.مرتب سازی ترتیب‌نگه‌دار با(کلاس، بیشتر)
    هر د در کلاس:
        چاپ د.نام، ""
    پایان
    سرچاپ ""
    سرچاپ مرتب سازی.مرتب است با(کلاس، بیشتر)
    کمتر := (الف: دانشجو، ب: دانشجو) => الف.نمره < ب.نمره
    صعودی := مرتب سازی.مرتب شده با(کلاس، کمتر)
    سرچاپ صعودی.بگیر(۰).نام
    مرتب سازی.مرتب سازی با(کلاس، کمتر)
    سرچاپ کلاس.بگیر(۰).نام
پایان
خروجیمریم سارا رضا علی true علی علی

مرتب سازی ترتیب‌نگه‌دار با StableSortBy

روال مرتب سازی ترتیب‌نگه‌دار با<T>(v: وکتور<T>، less: روال(T، T): منطقی)
مثل مرتب سازی با، ولی عضوهای برابر ترتیب اولیه‌شان را حفظ می‌کنند؛ در نمونه، سارا پیش از رضا می‌ماند چون زودتر آمده بود.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: sort-SortBy.salam

مرتب شده با SortedBy

روال مرتب شده با<T>(v: وکتور<T>، less: روال(T، T): منطقی): وکتور<T>
رونوشت مرتب‌شده با تابع مقایسه‌ی دلخواه.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: sort-SortBy.salam

مرتب است با IsSortedBy

روال مرتب است با<T>(v: وکتور<T>، less: روال(T، T): منطقی): منطقی
اگر وکتور بر اساس تابع مقایسه مرتب باشد، درست برمی‌گرداند.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: sort-SortBy.salam

مرتب سازی سریع QuickSort

روال مرتب سازی سریع<T>(v: وکتور<T>)
مرتب‌سازی سریع؛ در عمل سریع‌ترین برای بیشتر داده‌ها.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: sort-Algorithms.salam

مرتب است IsSorted

روال مرتب است<T>(v: وکتور<T>): منطقی
اگر وکتور صعودی مرتب باشد، درست برمی‌گرداند.
sort-Sort.salam
واردسازی مرتب سازی

روال ریشه:
    ناپایا عددها := وکتور {} برگردان وکتور<صحیح>
    دیرکن عددها.آزادکن()
    هر ع در [۵، ۳، ۹، ۱، ۷]:
        عددها.بیفزا(ع)
    پایان
    سرچاپ مرتب سازی.مرتب است(عددها)
    مرتب‌شده := مرتب سازی.مرتب شده(عددها)
    سرچاپ مرتب‌شده، عددها
    مرتب سازی.مرتب(عددها)
    سرچاپ عددها، مرتب سازی.مرتب است(عددها)
    مرتب سازی.مرتب نزولی(عددها)
    سرچاپ عددها
    مرتب سازی.برعکس(عددها)
    سرچاپ عددها، مرتب سازی.کمینه(عددها)، مرتب سازی.بیشینه(عددها)
    مرتب سازی.جابجایی(عددها، ۰، ۴)
    سرچاپ عددها
پایان
خروجیfalse [1, 3, 5, 7, 9] [5, 3, 9, 1, 7] [1, 3, 5, 7, 9] true [9, 7, 5, 3, 1] [1, 3, 5, 7, 9] 1 9 [9, 3, 5, 7, 1]

برعکس Reverse

روال برعکس<T>(v: وکتور<T>)
ترتیب عضوهای وکتور را برعکس می‌کند.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: sort-Sort.salam

کمینه Min

روال کمینه<T>(v: وکتور<T>): T
کوچک‌ترین عضو وکتور.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: sort-Sort.salam

بیشینه Max

روال بیشینه<T>(v: وکتور<T>): T
بزرگ‌ترین عضو وکتور.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: sort-Sort.salam

مرتب سازی مبنایی RadixSort

روال مرتب سازی مبنایی(v: وکتور<صحیح>)
مرتب‌سازی مبنایی برای عددهای صحیح؛ رقم به رقم مرتب می‌کند و مقایسه ندارد.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: sort-IntSorts.salam

مرتب سازی پنکیکی PancakeSort

روال مرتب سازی پنکیکی<T>(v: وکتور<T>)
مرتب‌سازی پنکیکی؛ فقط با برعکس کردن ابتدای وکتور مرتب می‌کند. برای آموزش.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: sort-Algorithms.salam

مرتب سازی کوکتلی CocktailSort

روال مرتب سازی کوکتلی<T>(v: وکتور<T>)
مرتب‌سازی کوکتلی؛ حبابی که در هر دور، هم از چپ به راست و هم برعکس می‌رود.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: sort-Algorithms.salam

مرتب سازی شانه ای CombSort

روال مرتب سازی شانه ای<T>(v: وکتور<T>)
مرتب‌سازی شانه‌ای؛ نسخه‌ی بهبودیافته‌ی حبابی.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: sort-Algorithms.salam

مرتب سازی انتخابی SelectionSort

روال مرتب سازی انتخابی<T>(v: وکتور<T>)
مرتب‌سازی انتخابی؛ هر بار کوچک‌ترین عضو باقیمانده را جلو می‌آورد.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: sort-Algorithms.salam

مرتب سازی سطلی BucketSort

روال مرتب سازی سطلی(v: وکتور<صحیح>)
مرتب‌سازی سطلی برای عددهای صحیح؛ وقتی عددها در بازه‌ای یکنواخت پخش‌اند سریع است.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: sort-IntSorts.salam

مرتب‌سازی نمایه SortIndex

روال مرتب‌سازی نمایه(idx &: وکتور<صحیح>، keys &: وکتور<اعشار۶۴>)
به‌جای مرتب کردن داده‌ها، شماره‌های idx را بر اساس keys صعودی مرتب می‌کند؛ وقتی چند وکتور هم‌ترتیب دارید و می‌خواهید همه را با هم مرتب ببینید.
sort-SortIndex.salam
واردسازی مرتب سازی

روال ریشه:
    نام‌ها := ["تهران"، "شیراز"، "تبریز"]
    ناپایا جمعیت := وکتور {} برگردان وکتور<اعشار۶۴>
    ناپایا ترتیب := وکتور {} برگردان وکتور<صحیح>
    دیرکن جمعیت.آزادکن()
    دیرکن ترتیب.آزادکن()
    جمعیت.بیفزا(۸.۷)
    جمعیت.بیفزا(۱.۶)
    جمعیت.بیفزا(۱.۶۵)
    تکرار ۳ در ای:
        ترتیب.بیفزا(ای)
    پایان
    مرتب سازی.مرتب‌سازی نمایه(ترتیب، جمعیت)
    هر ش در ترتیب:
        چاپ نام‌ها[ش]، ""
    پایان
    سرچاپ ""
    مرتب سازی.مرتب‌سازی نمایه نزولی(ترتیب، جمعیت)
    هر ش در ترتیب:
        چاپ نام‌ها[ش]، ""
    پایان
    سرچاپ ""
پایان
خروجیشیراز تبریز تهران تهران تبریز شیراز

مرتب‌سازی نمایه نزولی SortIndexDesc

روال مرتب‌سازی نمایه نزولی(idx &: وکتور<صحیح>، keys &: وکتور<اعشار۶۴>)
مثل مرتب‌سازی نمایه، نزولی.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: sort-SortIndex.salam

مرتب سازی حلزونی GnomeSort

روال مرتب سازی حلزونی<T>(v: وکتور<T>)
مرتب‌سازی حلزونی؛ مثل درجی، ساده و کند.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: sort-Algorithms.salam

جابجایی Swap

روال جابجایی<T>(v: وکتور<T>، i: صحیح، j: صحیح)
جای دو عضو وکتور را عوض می‌کند.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: sort-Sort.salam

مرتب سازی درجی InsertionSort

روال مرتب سازی درجی<T>(v: وکتور<T>)
مرتب‌سازی درجی؛ برای وکتورهای کوچک یا تقریباً مرتب خیلی خوب است.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: sort-Algorithms.salam

مرتب سازی درجی دودویی BinaryInsertionSort

روال مرتب سازی درجی دودویی<T>(v: وکتور<T>)
مرتب‌سازی درجی که جای درج را با جستجوی دودویی پیدا می‌کند.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: sort-Algorithms.salam

مرتب Sort

روال مرتب<T>(v: وکتور<T>)
وکتور را صعودی مرتب می‌کند. انتخاب پیش‌فرض برای مرتب کردن.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: sort-Sort.salam

مرتب نزولی SortDesc

روال مرتب نزولی<T>(v: وکتور<T>)
وکتور را نزولی مرتب می‌کند.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: sort-Sort.salam

مرتب شده Sorted

روال مرتب شده<T>(v: وکتور<T>): وکتور<T>
رونوشت صعودی مرتب‌شده‌ی وکتور؛ اصلی تغییر نمی‌کند.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: sort-Sort.salam

مرتب سازی زوج فرد OddEvenSort

روال مرتب سازی زوج فرد<T>(v: وکتور<T>)
مرتب‌سازی زوج و فرد؛ برای پردازش موازی طراحی شده است.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: sort-Algorithms.salam

مرتب سازی حبابی BubbleSort

روال مرتب سازی حبابی<T>(v: وکتور<T>)
مرتب‌سازی حبابی؛ ساده و کند، برای آموزش.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: sort-Algorithms.salam

مرتب سازی ادغامی MergeSort

روال مرتب سازی ادغامی<T>(v: وکتور<T>)
مرتب‌سازی ادغامی؛ همیشه سریع و پایدار، ولی حافظه‌ی اضافه می‌گیرد.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: sort-Algorithms.salam

مرتب سازی درون نگر IntroSort

روال مرتب سازی درون نگر<T>(v: وکتور<T>)
مرتب‌سازی درون‌نگر؛ با سریع شروع می‌کند و اگر لازم شد به هرمی تغییر می‌دهد تا هیچ‌وقت کند نشود.

نمونه‌ی این مورد همراه با موارد بالاتر آمده است: sort-Algorithms.salam