Bubble Sort, Insertion Sort and How Fast Sorting Isڕیزکردنی بڵقی، ڕیزکردن بە تێخستن و خێرایی ڕیزکردن

Sorting means putting items in an order: numbers from the smallest to the largest or the other way round, names in alphabetical order. Sorted data is much easier to search. A dictionary lists its words alphabetically, so you open it near the right page at once. An exam hall seats students by their exam number, so everyone finds a seat quickly. The Kurdistan football league table is sorted by points, so the leader is always on top.

ڕیزکردن واتە دانانی شتەکان بە ڕیزبەندییەک: ژمارەکان لە بچووکترینەوە بۆ گەورەترین یان بە پێچەوانەوە، ناوەکان بە ڕیزی ئەلفوبێ. گەڕان لە دراوەی ڕیزکراودا زۆر ئاسانترە. فەرهەنگی وشە، وشەکانی بە ڕیزی ئەلفوبێ دادەنێت، بۆیە یەکسەر نزیک لاپەڕە دروستەکە دەیکەیتەوە. لە هۆڵی تاقیکردنەوەدا قوتابیان بە ژمارەی تاقیکردنەوەکەیان دادەنیشن، بۆیە هەموو کەس بە خێرایی کورسییەکەی دەدۆزێتەوە. خشتەی لیگی تۆپی پێی کوردستان بە خاڵ ڕیزکراوە، بۆیە یەکەمی لیگ هەمیشە لە سەرەوەیە.

Sorting costs time, so why bother? Because you sort once and then search many times. A shop that keeps its 5000 product codes sorted spends a little time sorting them in the evening, and then every code is found quickly all day. Many sorting algorithms exist. They all give the same sorted list, but some need far more work, so programmers compare them.

ڕیزکردن کاتی دەوێت، کەواتە بۆچی ئەم ماندووبوونە؟ چونکە یەک جار ڕیز دەکەیت و پاشان زۆر جار دەگەڕێیت. دوکانێک کە ⁦5000⁩ کۆدی کاڵاکانی بە ڕیزکراوی هەڵدەگرێت، ئێواران کەمێک کات بۆ ڕیزکردن سەرف دەکات و پاشان بە درێژایی ڕۆژ هەر کۆدێک بە خێرایی دەدۆزرێتەوە. زۆر ئەلگۆریزمی (Algorithm) ڕیزکردن هەن. هەموویان هەمان لیستێکی (List) ڕیزکراو دەدەن، بەڵام هەندێکیان کاری زۆر زیاتریان دەوێت، بۆیە بەرنامەسازان (Software developer) بەراوردیان دەکەن.

Think before you read on: where else does a computer sort for you?

پێش ئەوەی بەردەوام بیت بیر بکەرەوە: کۆمپیوتەر (Computer) لە کوێی تر شتەکانت بۆ ڕیز دەکات؟

You have already sorted in this course. In real programs you call sorted(values), which returns a new sorted list, or values.sort(), which sorts the list itself; reverse=True puts the largest first and key= sorts by a rule. See sort() and sorted(), largest first and sorting by a rule. You also traced one algorithm by hand: selection sort finds the smallest value of the unsorted part and swaps it to the front (selection sort). Tables are sorted row by row in Sorting the rows of a table.

پێشتر لەم کۆرسەدا ڕیزت کردووە. لە بەرنامەی ڕاستەقینەدا sorted(values) بەکار دەهێنیت کە لیستێکی ڕیزکراوی نوێ دەگەڕێنێتەوە، یان values.sort() کە خودی لیستەکە ڕیز دەکات؛ reverse=True گەورەترین دەخاتە سەرەتا و key= بەپێی یاسایەک ڕیز دەکات. بڕوانە ⁦sort()⁩ و ⁦sorted()⁩، گەورەترین لە سەرەتادا و ڕیزکردن بەپێی یاسایەک. هەروەها بەدواداچوونت بۆ ئەلگۆریزمێک بە دەست کردووە: ڕیزکردن بە هەڵبژاردن (Selection sort) بچووکترین نرخی (Value) بەشی ڕیزنەکراو دەدۆزێتەوە و دەیگوازێتەوە بۆ سەرەتا (ڕیزکردن بە هەڵبژاردن). ڕیزەکانی خشتە لە ڕیزکردنی ڕیزەکانی خشتەیەک ڕیز دەکرێن.

This lesson adds two algorithms and then asks the real question: how much work does each one do, and what happens when the list gets big?

ئەم وانەیە دوو ئەلگۆریزم زیاد دەکات و پاشان پرسیارە ڕاستەقینەکە دەکات: هەر یەکەیان چەند کار دەکات و کاتێک لیستەکە گەورە دەبێت چی ڕوو دەدات؟

Bubble sort walks along the list and looks at neighbours: positions 0 and 1, then 1 and 2, and so on. Whenever the left value is bigger than the right one, it swaps them. One walk from the start to the end is called a pass. During a pass the largest value is carried along to the end, like a bubble rising in a glass of water, which gives the algorithm its name.

ڕیزکردنی بڵقی بە لیستەکەدا دەڕوات و سەیری دراوسێکان دەکات: شوێنی 0 و 1، پاشان 1 و 2 و بەم شێوەیە. هەر کاتێک نرخی چەپ لە ڕاست گەورەتر بوو، ئاڵوگۆڕیان پێ دەکات. یەک ڕۆیشتن لە سەرەتاوە بۆ کۆتایی پێی دەوترێت جار (pass). لە هەر جارێکدا گەورەترین نرخ بەرەو کۆتایی دەبرێت، وەک بڵقێک کە لە پەرداخێک ئاودا بەرز دەبێتەوە، هەر بۆیە ناوی لێ نراوە.

After pass 1 the largest value is in its final place, so pass 2 can stop one pair earlier. After pass 2 the two largest values are in place, and so on. A list of $n$ values needs at most $n-1$ passes, and each pass makes one comparison fewer than the one before: $n-1$, then $n-2$, down to 1.

دوای جاری یەکەم گەورەترین نرخ لە شوێنی کۆتایی خۆیدایە، بۆیە جاری دووەم دەتوانێت یەک جووت زووتر بوەستێت. دوای جاری دووەم دوو گەورەترینەکە لە شوێنی خۆیانن و بەم شێوەیە. لیستێک بە $n$ نرخ لانیزۆر پێویستی بە $n-1$ جار هەیە و هەر جارێک یەک بەراورد کەمتر لە جاری پێشوو دەکات: $n-1$، پاشان $n-2$، تا دەگاتە 1.

Six January mornings in Penjwen gave these temperatures in °C: [4, -2, 9, -6, 1, 7]. The table follows bubble sort on them. Each pass compares the pairs in the second column from left to right.

شەش بەیانیی مانگی کانوونی دووەم لە پێنجوێن ئەم پلە گەرمییانەیان ⁦(°C)⁩ دا: [4, -2, 9, -6, 1, 7]. خشتەکە هەنگاوەکانی ڕیزکردنی بڵقی لەسەر ئەم پلە گەرمییانە پیشان دەدات. هەر جارێک جووتەکانی ستوونی دووەم لە چەپەوە بۆ ڕاست بەراورد دەکات.

Look at the passes: 5, 4, 3, 2 and 1 comparisons. The list is already sorted after pass 3, but this plain version of bubble sort cannot know that, so it still makes passes 4 and 5. The program below prints every comparison, so you can check the table.

سەیری جارەکان بکە: 5، 4، 3، 2 و 1 بەراورد. لیستەکە دوای جاری سێیەم ڕیزکراوە، بەڵام ئەم وەشانە سادەیەی ڕیزکردنی بڵقی ناتوانێت ئەوە بزانێت، بۆیە هێشتا جاری چوارەم و پێنجەم دەکات. بەرنامەی خوارەوە هەموو بەراوردێک چاپ دەکات، بۆیە دەتوانیت خشتەکە بپشکنیت.

The steps become two loops, one inside the other (nested loops): the outer loop counts the passes, the inner loop walks along the pairs.

هەنگاوەکان دەبنە دوو خول، یەکێکیان لە ناو ئەوی تردا (خولە ناوەکییەکان): خولی دەرەوە جارەکان دەژمێرێت و خولی ناوەوە بە جووتەکاندا دەڕوات.

To put the largest first, change one character: swap when the left value is smaller than the right one.

بۆ ئەوەی گەورەترین لە سەرەتا بێت، تەنها یەک نووسە (Character) بگۆڕە: کاتێک نرخی چەپ لە ڕاست بچووکتر بوو ئاڵوگۆڕیان پێ بکە.

In the trace the list was sorted after pass 3, yet passes 4 and 5 still ran. A pass that makes no swap at all proves that the list is sorted: every pair of neighbours is already in order. So keep a flag. Set swapped = False at the start of each pass, set it to True whenever you swap, and leave the outer loop with break if it is still False at the end of the pass (break).

لە بەدواداچوونەکەدا لیستەکە دوای جاری سێیەم ڕیزکرابوو، بەڵام هێشتا جاری چوارەم و پێنجەم کران. جارێک کە هیچ ئاڵوگۆڕێک نەکات دەیسەلمێنێت کە لیستەکە ڕیزکراوە: هەموو جووتە دراوسێیەک پێشتر بە ڕیزن. کەواتە ئاڵایەک هەڵبگرە. لە سەرەتای هەر جارێکدا swapped = False دابنێ، هەر کاتێک ئاڵوگۆڕت کرد بیکە بە True و ئەگەر لە کۆتایی جارەکەدا هێشتا False بوو، بە break خولی دەرەوە جێبهێڵە (break).

On the temperatures the flag saves only pass 5: 14 comparisons instead of 15. Pass 4 is still needed, because it is the pass that finds no swap. On a list that is already sorted the saving is large: one pass of 5 comparisons instead of 15 comparisons in 5 passes.

لەسەر پلە گەرمییەکان ئاڵاکە تەنها جاری پێنجەم پاشەکەوت دەکات: ⁦14⁩ بەراورد لەبری ⁦15⁩. جاری چوارەم هێشتا پێویستە، چونکە ئەو جارەیە کە هیچ ئاڵوگۆڕێک نادۆزێتەوە. لەسەر لیستێک کە پێشتر ڕیزکراوە پاشەکەوتەکە گەورەیە: یەک جار بە 5 بەراورد لەبری ⁦15⁩ بەراورد لە 5 جاردا.

Think of how you sort playing cards. You pick up one card at a time. The cards already in your hand are in order, and each new card slides left past the bigger ones until it drops into its place. Insertion sort does exactly this. The left part of the list is the sorted hand. Each pass takes the next value, the current value, shifts every bigger value of the sorted part one place to the right, and drops the current value into the gap.

بیر لەوە بکەرەوە چۆن کارتی یاری ڕیز دەکەیت. هەر جارە یەک کارت هەڵدەگریت. ئەو کارتانەی پێشتر لە دەستتدان بە ڕیزن و هەر کارتێکی نوێ بەرەو چەپ بە تەنیشت کارتە گەورەترەکاندا دەخزێت تا لە شوێنی خۆیدا دادەنرێت. ڕیزکردن بە تێخستن ڕێک ئەمە دەکات. بەشی چەپی لیستەکە دەستە ڕیزکراوەکەیە. هەر جارێک نرخی داهاتوو هەڵدەگرێت، واتە نرخی ئێستا، هەموو نرخێکی گەورەتری بەشە ڕیزکراوەکە یەک شوێن بەرەو ڕاست دەجووڵێنێت و نرخی ئێستا دەخاتە ناو بۆشاییەکە.

The same temperatures, [4, -2, 9, -6, 1, 7], sorted by insertion sort. Pass 1 starts with the second value, because one value on its own is already a sorted hand.

هەمان پلە گەرمییەکان، [4, -2, 9, -6, 1, 7]، بە ڕیزکردن بە تێخستن ڕیز دەکرێن. جاری یەکەم بە نرخی دووەم دەست پێ دەکات، چونکە یەک نرخ بە تەنها خۆی دەستێکی ڕیزکراوە.

Pass 2 is cheap: 9 is bigger than the last card of the sorted part, so one comparison shows that it is already in place. Pass 4 stops at $-2$, because $-2$ is not bigger than 1: everything further left is even smaller.

جاری دووەم هەرزانە: 9 لە دوایین کارتی بەشە ڕیزکراوەکە گەورەترە، بۆیە یەک بەراورد پیشانی دەدات کە پێشتر لە شوێنی خۆیدایە. جاری چوارەم لە $-2$دا دەوەستێت، چونکە $-2$ لە 1 گەورەتر نییە: هەموو ئەوانەی زیاتر لە چەپن لەوەش بچووکترن.

For the largest first, again flip one comparison: shift while the value on the left is smaller than current.

بۆ گەورەترین لە سەرەتادا، دیسان یەک بەراورد پێچەوانە بکەرەوە: تا نرخی لای چەپ لە current بچووکتر بێت بیجووڵێنە.

At registration, students' names arrive one at a time, and the list must stay in alphabetical order the whole time. Which technique fits? Insertion sort: each new name is inserted into a list that is already sorted, which is exactly one pass of insertion sort. Insertion sort can sort a list while it is still arriving, something bubble and selection sort cannot do.

لە کاتی ناونووسیندا ناوی قوتابیان یەک یەک دێن و دەبێت لیستەکە هەمیشە بە ڕیزی ئەلفوبێ بمێنێتەوە. کام ڕێگا گونجاوە؟ ڕیزکردن بە تێخستن: هەر ناوێکی نوێ دەخرێتە ناو لیستێک کە پێشتر ڕیزکراوە، کە ڕێک یەک جاری ڕیزکردن بە تێخستنە. ڕیزکردن بە تێخستن دەتوانێت لیستێک ڕیز بکات لە کاتێکدا هێشتا دێت، شتێک کە ڕیزکردنی بڵقی و ڕیزکردن بە هەڵبژاردن ناتوانن.

Which algorithm does the least work? A stopwatch depends on the computer, so we count instead: the number of comparisons, and the number of swaps (in insertion sort, shifts). The program adds counters to all three algorithms and runs them on the same three lists. Each function sorts a copy, so every algorithm gets exactly the same input.

کام ئەلگۆریزم کەمترین کار دەکات؟ پێوانی کات بە کاتژمێر پشت بە کۆمپیوتەرەکە دەبەستێت، بۆیە لەبری ئەوە دەژمێرین: ژمارەی بەراوردەکان و ژمارەی ئاڵوگۆڕەکان (لە ڕیزکردن بە تێخستندا، جووڵاندنەکان). بەرنامەکە ژمێرەرەکان (Counter) بۆ هەر سێ ئەلگۆریزمەکە زیاد دەکات و لەسەر هەمان سێ لیست کاریان پێ دەکات. هەر کردارێک کۆپییەک ڕیز دەکات، بۆیە هەموو ئەلگۆریزمێک ڕێک هەمان نێوخستە (Input) وەردەگرێت.

Bubble sort's 7 swaps and insertion sort's 7 shifts are no accident. Each swap or shift fixes exactly one pair of values that stood in the wrong order, and the temperatures have exactly 7 such pairs. Selection sort always makes 15 comparisons, but at most one swap per pass, which helps when moving data is slow.

7 ئاڵوگۆڕی ڕیزکردنی بڵقی و 7 جووڵاندنی ڕیزکردن بە تێخستن ڕێکەوت نین. هەر ئاڵوگۆڕ یان جووڵاندنێک ڕێک یەک جووت نرخ چاک دەکات کە بە ڕیزبەندیی هەڵە وەستابوون و پلە گەرمییەکان ڕێک 7 جووتی وایان هەیە. ڕیزکردن بە هەڵبژاردن هەمیشە ⁦15⁩ بەراورد دەکات، بەڵام لە هەر جارێکدا لانیزۆر یەک ئاڵوگۆڕ، کە یارمەتیدەرە کاتێک جووڵاندنی دراوە هێواشە.

The same algorithm can be quick or slow, depending on the input. The best case is the input of size $n$ that needs the least work; the worst case is the one that needs the most (worst and average case). For sorting, the best case is a list that is already sorted, and the worst case is a list in reverse order. The counting program above gives, for six values:

هەمان ئەلگۆریزم دەکرێت خێرا یان هێواش بێت، بەپێی نێوخستە. لە باشترین باردا نێوخستەکە (بە قەبارەی $n$) کەمترین کاری دەوێت؛ لە خراپترین باردا زۆرترین کاری دەوێت (خراپترین بار و باری مامناوەند). بۆ ڕیزکردن، باشترین بار لیستێکە کە پێشتر ڕیزکراوە و خراپترین بار لیستێکە بە ڕیزبەندیی پێچەوانە. بەرنامەی ژماردنی سەرەوە بۆ شەش نرخ ئەمە دەدات:

In general, for $n$ values: in the best case bubble sort with the flag and insertion sort make only $n-1$ comparisons. In the worst case every pass compares as much as it can:

بە گشتی، بۆ $n$ نرخ: لە باشترین باردا ڕیزکردنی بڵقی بە ئاڵاوە و ڕیزکردن بە تێخستن تەنها $n-1$ بەراورد دەکەن. لە خراپترین باردا هەر جارێک هەموو ئەو بەراوردانە دەکات کە دەتوانێت:

With six values every algorithm finishes at once. Count again with 1,000 numbers, in random order, already sorted and reversed, and the difference between the best and the worst case becomes huge:

لەگەڵ شەش نرخ هەموو ئەلگۆریزمێک یەکسەر تەواو دەبێت. دووبارە لەگەڵ $1000$ ژمارە بژمێرە، بە ڕیزبەندیی هەڕەمەکی، پێشتر ڕیزکراو و پێچەوانە، ئەوکاتە جیاوازیی نێوان باشترین بار و خراپترین بار زۆر گەورە دەبێت:

Time complexity describes how the work of an algorithm grows when its input grows. With six temperatures every algorithm finishes at once. With a million records, the difference decides whether a program answers in a second or in hours, so programmers think about it before they use an algorithm on real data. Three rules of thumb cover most beginner programs:

ئاڵۆزیی کات (Time complexity) باس لەوە دەکات کە کاری ئەلگۆریزمێک چۆن گەورە دەبێت کاتێک نێوخستەکەی گەورە دەبێت. لەگەڵ شەش پلەی گەرمیدا هەموو ئەلگۆریزمێک یەکسەر تەواو دەبێت. لەگەڵ ملیۆنێک تۆماردا (Record)، جیاوازییەکە بڕیار دەدات کە بەرنامەیەک لە چرکەیەکدا وەڵام دەداتەوە یان لە چەند کاتژمێرێکدا، بۆیە بەرنامەسازان پێش بەکارهێنانی ئەلگۆریزمێک لەسەر دراوەی ڕاستەقینە بیری لێ دەکەنەوە. سێ یاسای سادە زۆربەی بەرنامەی سەرەتایی دەگرنەوە:

All three sorting algorithms of this lesson have a loop inside a loop, so all three are quadratic. Programmers write this as $O(n^2)$, read "order n squared"; the notation is explained in Big-O notation in one screen, and Comparing algorithms compares four algorithms for the same problem in the same way.

هەر سێ ئەلگۆریزمی ڕیزکردنی ئەم وانەیە خولێک لە ناو خولێکدا هەیە، بۆیە هەر سێکیان پلەدوون. بەرنامەسازان ئەمە وەک $O(n^2)$ دەنووسن؛ ئەم نیشانەیە لە نیشانەی O-ی گەورە لە یەک پەڕەدا ڕوون کراوەتەوە و بەراوردکردنی ئەلگۆریزمەکان بە هەمان شێوە چوار ئەلگۆریزم بۆ هەمان کێشە بەراورد دەکات.

Counting is the fair way to compare algorithms, but it is also interesting to time them. The program sorts the same random numbers with bubble sort, insertion sort and Python's list.sort(), and measures the seconds with time.perf_counter(). These times come from the computer this lesson was written on (an Apple M1 laptop with Python 3.12). Your numbers will differ, and even two runs on the same computer differ a little.

ژماردن ڕێگای دادپەروەرانەی بەراوردکردنی ئەلگۆریزمەکانە، بەڵام کاتگرتنیشیان سەرنجڕاکێشە. بەرنامەکە هەمان ژمارە هەڕەمەکییەکان (Random number) بە ڕیزکردنی بڵقی، ڕیزکردن بە تێخستن و list.sort()ـی Python ڕیز دەکات و چرکەکان بە time.perf_counter() دەپێوێت. ئەم کاتانە لەو کۆمپیوتەرەوە هاتوون کە ئەم وانەیەی لەسەر نووسراوە (لاپتۆپێکی ⁦Apple M1⁩ بە ⁦Python 3.12⁩). ژمارەکانی تۆ جیاواز دەبن و تەنانەت دوو جار کارپێکردن لەسەر هەمان کۆمپیوتەر کەمێک جیاوازن.

Each time $n$ doubles, bubble sort and insertion sort take about four times as long: that is quadratic growth. list.sort() takes only about twice as long, and it starts out hundreds of times faster. If bubble sort kept growing like $n^2$, a million numbers (250 times 4,000) would take $250^2 = 62\,500$ times as long as 4,000 numbers: about 28,000 seconds, nearly 8 hours. That is an estimate, not a measurement. On the same computer list.sort() really sorts a million numbers in 0.14 seconds:

هەر جارێک $n$ دوو هێندە دەبێت، ڕیزکردنی بڵقی و ڕیزکردن بە تێخستن نزیکەی چوار هێندە کات دەبەن: ئەمە گەشەی پلەدووە. list.sort() تەنها نزیکەی دوو هێندە کات دەبات و لە سەرەتاوە سەدان جار خێراترە. ئەگەر ڕیزکردنی بڵقی بەردەوام وەک $n^2$ گەورە ببوایە، ملیۆنێک ژمارە (⁦250⁩ هێندەی ⁦4000⁩) $250^2 = 62\,500$ هێندەی ⁦4000⁩ ژمارە کاتی دەبرد: نزیکەی ⁦28000⁩ چرکە، نزیکەی 8 کاتژمێر. ئەمە خەمڵاندنە، نەک پێوانە. لەسەر هەمان کۆمپیوتەر list.sort() بە ڕاستی ملیۆنێک ژمارە لە ⁦0.14⁩ چرکەدا ڕیز دەکات:

Python's sort() and sorted() use Timsort, a much cleverer algorithm built from insertion sort and merging. It needs about $n \log n$ comparisons instead of $n \times n$, which is why it sorted a million numbers in a fraction of a second (the logarithm is explained in the next lesson, How many steps?). It is also adaptive: on a list that is already sorted, or sorted backwards, it needs only about $n$ comparisons, which is why sorting the sorted million again took 0.018 s.

sort() و sorted()ـی Python Timsort بەکار دەهێنن، ئەلگۆریزمێکی زۆر زیرەکتر کە لە ڕیزکردن بە تێخستن و تێکەڵکردن دروست کراوە. لەبری $n \times n$ نزیکەی $n \log n$ بەراوردی پێویستە، هەر بۆیە ملیۆنێک ژمارەی لە بەشێکی چرکەیەکدا ڕیز کرد (لۆگاریتم (Logarithm) لە وانەی داهاتوودا ڕوون دەکرێتەوە: چەند هەنگاو؟). هەروەها خۆگونجێنە: لەسەر لیستێک کە پێشتر ڕیزکراوە یان بە پێچەوانە ڕیزکراوە، تەنها نزیکەی $n$ بەراوردی پێویستە، هەر بۆیە دووبارە ڕیزکردنی ملیۆنە ڕیزکراوەکە ⁦0.018⁩ چرکەی برد.

It is also stable: values that compare as equal keep the order they had before the sort. Sort exam results by mark, and two students with the same mark stay in the order of the original list.

هەروەها جێگیرە (ڕیزکردنی جێگیر): ئەو نرخانەی لە بەراورددا یەکسانن هەمان ڕیزبەندیی پێش ڕیزکردن دەپارێزن. ئەنجامی تاقیکردنەوە بە نمرە ڕیز بکە، دوو قوتابی بە هەمان نمرە بە ڕیزبەندیی لیستی سەرەتایی دەمێننەوە.

Next: searching. Linear search, then binary search, which needs a sorted list and adds a fourth speed to the table: logarithmic time.

دواتر: گەڕان. گەڕانی هێڵی (Linear search)، پاشان گەڕانی دووانی، کە لیستێکی ڕیزکراوی پێویستە و خێرایی چوارەم بۆ خشتەکە زیاد دەکات: کاتی لۆگاریتمی (Logarithmic time).