مصیبت مرتب‌سازی

julia> v = [3, 2, 4, 1]
4-element Vector{Int64}:
 3
 2
 4
 1

julia> sort(v)
4-element Vector{Int64}:
 1
 2
 3
 4

# sort descending
julia> sort(v, rev=true)
4-element Vector{Int64}:
 4
 3
 2
 1

julia> v
4-element Vector{Int64}:
 3
 2
 4
 1

julia> issorted(v)
false

# v is as previously

julia> issorted(v)
false

julia> sort!(v)
4-element Vector{Int64}:
 1
 2
 3
 4

julia> v
4-element Vector{Int64}:
 1
 2
 3
 4

julia> issorted(v)
true

julia> langs = ["Julia", "C++", "Python", "Elixir"]
4-element Vector{String}:
 "Julia"
 "C++"
 "Python"
 "Elixir"

julia> inxs = sortperm(langs)  # => Integers
4-element Vector{Int64}:
 2
 4
 1
 3

julia> langs[inxs]  # sort the entire vector
4-element Vector{String}:
 "C++"
 "Elixir"
 "Julia"
 "Python"

julia> langs[inxs[1:2]]  # slice the indices
2-element Vector{String}:
 "C++"
 "Elixir"

دستورالعمل‌ها

شما به عنوان دستیار مهندس تولید در شرکتی استخدام شده‌اید که برای لاک‌پشت‌ها لحاف تولید می‌کند.

سفارش‌ها در طول روز به شکل اسم یا شماره‌ی مشتری و تعداد سفارش ثبت می‌شوند. سپس این سفارش‌ها صبح‌ها، پیش از شروع تولید همان روز، پردازش می‌شوند.

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

1. تعداد را مرتب کنید!

همان‌طور که گفته شد، آرایه‌ی تعدادها باید از بزرگ به کوچک مرتب شود. به دلیل اندازه‌ی بالقوه بزرگ این آرایه‌ها، باید آن‌ها را درجا مرتب کرد. برای اینکه همه‌چیز را درست پیگیری کنید، باید بتوانید آرایه‌ی مشتری‌ها را هم متناسب با تعدادها مرتب کنید؛ بنابراین به یک «جایگشت» مرتب‌سازی از تعدادها نیاز خواهید داشت.

تابعی به اسم sortquantity!(qty) بنویسید که یک Vector از تعدادهای Integer می‌گیرد. این تابع ورودی qty را درجا و به ترتیب نزولی مرتب می‌کند و یک جایگشت مرتب‌سازی از این ترتیب برمی‌گرداند.

julia> qty = [8, 9, 5, 6]
4-element Vector{Int64}:
 8
 9
 5
 6

julia> sortquantity!(qty)
4-element Vector{Int64}:
 2
 1
 4
 3

julia> qty # original vector is sorted in-place
4-element Vector{Int64}:
 9
 8
 6
 5

2. مشتری را مرتب کنید

همان‌طور که در بالا گفته شد، باید مشتری‌ها را در یک ترتیب مشخص پیگیری کنید.

تابعی به اسم sortcustomer(cust, srtperm) بنویسید که یک Vector از مشتری‌ها یعنی cust و یک Vector جایگشت مرتب‌سازی یعنی srtperm می‌گیرد. این تابع آرایه‌ای جدید برمی‌گرداند که مشتری‌ها در آن به همان ترتیبی قرار دارند که جایگشت مرتب‌سازی تعیین کرده است.

julia> cust = ["a", "b", "c"]
3-element Vector{String}:
 "a"
 "b"
 "c"

julia> sortcustomer(cust, [2, 3, 1])
3-element Vector{String}:
 "b"
 "c"
 "a"

julia> cust # original vector remains unsorted
3-element Vector{String}:
 "a"
 "b"
 "c"

3. برنامه‌ی تولید!

حالا می‌توانید همه را کنار هم بگذارید تا به گرم ماندن آن لاک‌پشت‌ها کمک کنید! اکنون می‌توانید تعدادها و مشتری‌ها را درست مرتب کنید، اما باید بتوانید ترتیب اصلی را برای ارسال بازیابی کنید. این کار با یک جایگشت مرتب‌سازی معکوس انجام می‌شود.

تابعی به اسم production_schedule!(cust, qty) بنویسید که یک Vector از مشتری‌ها و یک Vector از تعدادها می‌گیرد. این تابع تعدادها را درجا و به ترتیب نزولی مرتب می‌کند. این تابع یک Vector جدید از مشتری‌ها برمی‌گرداند که به همان ترتیب تعدادها مرتب شده‌اند، و همچنین یک جایگشت مرتب‌سازی معکوس برمی‌گرداند که می‌توان با آن بردارهای مرتب‌شده را به ترتیب اصلی‌شان بازگرداند.

julia> cust, qty = ["a", "b", "c"], [2, 3, 1]
(["a", "b", "c"], [2, 3, 1])

julia> orderedcust, invperm = production_schedule!(cust, qty)
(["b", "a", "c"], [2, 1, 3])

julia> qty # has been sorted in-place
3-element Vector{Int64}:
 3
 2
 1

julia> orderedcust[invperm], qty[invperm] # inverse permutation gives original ordering
(["a", "b", "c"], [2, 3, 1])