Honlap címe

Előző - #41 ROT 13 Titkosítás | Tartalomjegyzék

42. GYAKORLAT: BUBORÉKOS RENDEZÉS

bubbleSort([2, 0, 4, 1, 3]) → [0, 1, 2, 3, 4]

A buborékos rendezés gyakran az első rendezési algoritmus, amelyet informatikus hallgatóknak tanítanak. Bár túlságosan nem hatékony a valós világban való használathoz, az algoritmus könnyen érthető. A könyv utolsó gyakorlatában ezt az alapvető rendezési algoritmust fogjuk megvalósítani.

Gyakorlat leírása

Írjon bubbleSort()függvényt egy listaparaméterrel numbers. A függvény a helyén átrendezi a listában szereplő értékeket. A függvény a most rendezett listát is visszaadja. Számos rendezési algoritmus létezik, de ez a gyakorlat a buborékos rendezési algoritmus megvalósítását kéri.

Ennek a gyakorlatnak az a célja, hogy egy rendezési algoritmust írjon, ezért kerülje a Python sort()metódusának vagy a sorted() függvénynek a használatát, mert az megsértené a gyakorlat célját.

Ezek a Python- assertutasítások leállítják a programot, ha feltételük False. Másolja őket a megoldási program aljára. Az Ön megoldása akkor helyes, ha a következő assertállítások feltételei mind igazak :

assert bubbleSort([2, 0, 4, 1, 3]) == [0, 1, 2, 3, 4]

assert bubbleSort([2, 2, 2, 2]) == [2, 2, 2, 2]

Próbáljon megoldást írni a leírásban szereplő információk alapján. Ha továbbra is problémái vannak ennek a gyakorlatnak a megoldásával, további tippekért olvassa el a Megoldástervezés és a Különleges esetek és Gotchák című részt.

Előfeltétel fogalmak: listák, for ciklusok, range()két argumentummal, beágyazott ciklusok, értékek felcserélése

Megoldás tervezése

A buborékos rendezési algoritmus minden indexpárt összehasonlít, és felcseréli az értékeiket, hogy a nagyobb érték később kerüljön a listába. Ahogy az algoritmus fut, a nagyobb számok a vége felé „buborékolnak”, innen ered az algoritmus neve. iA és j nevű változókkal követjük nyomon azt a két indexet, amelyek értékeit össze kell hasonlítani egymással. A i és a mozgások mögötti minta jvizuálisan könnyebben látható, mint a 42-1. ábra, amely egy 5 elemből álló numberslistát használ példaként:

Figyelje meg a hasonlóságot az i mozgása és ja beágyazott for ciklusok között a 26-os „Kézfogás” projektben. Ahogy az algoritmus fut, jutána indul i és jobbra mozog, majd amikor eléri a végét, i egyszer jobbra mozog, és újra az ij után indul .

If you look at the overall range of i and j, you’ll see that i starts at index 0 and ends at the second to last index. Meanwhile, j starts at the index after i and ends at the last index. This means our nested for loops over the numbers list parameter would look like this:

for i in range(len(numbers) - 1):

for j in range(i, len(numbers)):

Inside the inner loop, the numbers at indexes i and j are compared, and if the number at index i is larger than the number at index j, they are swapped. Figure 42-2 shows the state of a list [8, 2, 9, 6, 3] as the bubble sort algorithm swaps the two numbers after being compared at each step.

At the end of these two nested for loops, the numbers in the list will have been swapped into sorted order.

Special Cases and Gotchas

Sorting algorithms are an excellent introduction to the computer science topic of data structures and algorithms. And bubble sort is a good introduction to sorting algorithms. But the chief weakness of bubble sort is that it’s incredibly inefficient. While it can quickly sort lists of a few dozen or few hundred values, it becomes infeasible for sorting lists of thousands or millions of values. For this reason, real-world applications never use bubble sort.

Now try to write a solution based on the information in the previous sections. If you still have trouble solving this exercise, read the Solution Template section for additional hints.

Solution Template

Try to first write a solution from scratch. But if you have difficulty, you can use the following partial program as a starting place. Copy the following code from https://invpy.com/bubblesort-template.py and paste it into your code editor. Replace the underscores with code to make a working program:

def bubbleSort(numbers):

# The outer loop loops i over all but the last number:

for i in range(len(____) - ____):

# The inner loop loops j starting at i to the last number:

for j in range(____, len(____)):

# If the number at i is greater than the number at j, swap them:

if numbers[i] ____ numbers[j]:

numbers[i], numbers[j] = numbers[____], numbers[____]

# Return the now-sorted list:

return numbers

The complete solution for this exercise is given in Appendix A and https://invpy.com/bubblesort.py. You can view each step of this program as it runs under a debugger at https://invpy.com/bubblesort-debug/.