forked from keon/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathcocktail_shaker_sort.py
More file actions
45 lines (36 loc) · 1.12 KB
/
cocktail_shaker_sort.py
File metadata and controls
45 lines (36 loc) · 1.12 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
"""
Cocktail Shaker Sort
Cocktail shaker sort is a variation of bubble sort that traverses the
list alternately from left-to-right and right-to-left.
Reference: https://en.wikipedia.org/wiki/Cocktail_shaker_sort
Complexity:
Time: O(n) best / O(n^2) average / O(n^2) worst
Space: O(1)
"""
from __future__ import annotations
def cocktail_shaker_sort(array: list[int]) -> list[int]:
"""Sort an array in ascending order using cocktail shaker sort.
Args:
array: List of integers to sort.
Returns:
A sorted list.
Examples:
>>> cocktail_shaker_sort([3, 1, 2])
[1, 2, 3]
"""
n = len(array)
swapped = True
while swapped:
swapped = False
for i in range(1, n):
if array[i - 1] > array[i]:
array[i - 1], array[i] = array[i], array[i - 1]
swapped = True
if not swapped:
return array
swapped = False
for i in range(n - 1, 0, -1):
if array[i - 1] > array[i]:
array[i - 1], array[i] = array[i], array[i - 1]
swapped = True
return array