Full sort
- Algorithms course
- Beginner
- Lesson 23/80
- 4 min
Sort fully with multiple passes; O(n^2).
Is sorted check
To check if an array is sorted, you iterate over adjacent pairs and verify that each is in the correct order.
If you find even one pair in the wrong order, the array is not sorted. If all pairs are correct, the array is sorted.
Early termination
To optimize bubble sort, if no swap occurs during a pass, the array is sorted and the algorithm can stop. This makes the best case O(n).
This optimization uses a swapped flag: False at the start of a pass, True when a swap occurs. If still False at the end, the loop breaks.
Practice Is sorted
Write is_sorted(arr). Check neighbors, return True if sorted, False otherwise. Print True with print(is_sorted([1, 2, 3])).
Starter code
def is_sorted(arr):
# Check if sortedSample solution
def is_sorted(arr):
# Check if sorted
for i in range(len(arr) - 1):
if arr[i] > arr[i + 1]:
return False
return True
print(is_sorted([1, 2, 3]))Expected output
True
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Full sort: match the terms
| Term | Meaning |
|---|---|
Sorted |
Neighbors correct |
Pass |
Start to end |
No swap |
Stop |
O(n^2) |
Worst |
2 What does no swap in a pass mean?
- Array is broken
- Array is sorted Correct answer
- Array is empty
- Array is too large
Explanation: No swap means the array is sorted.
3 Sorted check
If sorted, ____ is returned.If sorted, True is returned.Explanation: True is right.