algorithms/algorithms/sorting/gnome_sort.py at main · keon/algorithms · GitHub

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
"""
Gnome Sort

Gnome sort moves an element toward the front of the list until it finds
an element that is smaller or equal, then steps forward again.  It is
similar to insertion sort but uses swaps instead of shifts.

Reference: https://en.wikipedia.org/wiki/Gnome_sort

Complexity:
    Time:  O(n) best / O(n^2) average / O(n^2) worst
    Space: O(1)
"""

from __future__ import annotations


def gnome_sort(array: list[int]) -> list[int]:
    """Sort an array in ascending order using gnome sort.

    Args:
        array: List of integers to sort.

    Returns:
        A sorted list.

    Examples:
        >>> gnome_sort([3, 1, 2])
        [1, 2, 3]
    """
    n = len(array)
    index = 0
    while index < n:
        if index == 0 or array[index] >= array[index - 1]:
            index += 1
        else:
            array[index], array[index - 1] = array[index - 1], array[index]
            index -= 1
    return array