5 Best Ways to Check if an Array is Almost Sorted in Python

Rate this post

πŸ’‘ Problem Formulation: You may encounter a situation where you need to verify if an array is nearly sorted – that is, can it become entirely sorted by moving any element at most one position from where it currently stands? For example, with a given input array [1, 3, 2, 4], the desired output would be True since the array can be sorted by swapping the elements ‘3’ and ‘2’. This article explores multiple approaches to solving this problem in Python.

Method 1: Brute Force Approach

This method involves checking every element with its immediate neighbors to see if swapping them results in a sorted array. We iterate through the array and swap each element with its adjacent elements to check if the array becomes sorted. This is a straightforward but a potentially less efficient approach when dealing with large arrays.

Here’s an example:

def is_almost_sorted(arr):
    if len(arr) < 3:  # A 2-element or smaller list is always 'almost sorted'
        return True
    for i in range(len(arr) - 1):
        if arr[i] > arr[i + 1]:
            # Try swapping with the next element
            arr[i], arr[i + 1] = arr[i + 1], arr[i]
            if arr == sorted(arr):
                return True
            # If it didn't work, revert the swap and try with previous element
            arr[i], arr[i + 1] = arr[i + 1], arr[i]
            if i > 0 and arr[i] < arr[i - 1]:
                arr[i], arr[i - 1] = arr[i - 1], arr[i]
                if arr == sorted(arr):
                    return True
                arr[i], arr[i - 1] = arr[i - 1], arr[i]
            return False
    return True

print(is_almost_sorted([1, 3, 2, 4]))

Output:

True

This code defines the function is_almost_sorted() that takes an array as input and returns True if the array can be sorted by swapping at most one pair of adjacent elements. It checks each pair and tries to swap them if they’re out of order, then verifies if the resulting array is sorted. If the array is already near-sorted or the swap works, it returns True. If not, it reverts the swap and checks the previous element. The function also handles the edge case for very short arrays.

Method 2: Optimized Swap Check

The optimized swap check is an improved version of the brute force approach. Instead of swapping, we simply check if the potential swap would result in a sorted array. This method reduces the number of operations by avoiding unnecessary swaps and reverts, making it more efficient.

Here’s an example:

def almost_sorted(arr):
    swap = None
    for i in range(len(arr) - 1):
        if arr[i] > arr[i + 1]:
            if swap is not None:
                return False
            swap = (i, i + 1)
    if swap is None:
        return True
    i, j = swap
    arr[i], arr[i + 1] = arr[i + 1], arr[i]  # Perform the potential swap
    return arr == sorted(arr)

print(almost_sorted([1, 3, 2, 4]))

Output:

True

The function almost_sorted() tracks the indices where a swap might need to happen. If more than one swap is needed, it returns False. Otherwise, it simulates the swap and checks if the array becomes sorted. The approach is more efficient as it avoids unnecessary comparisons and swaps that don’t lead to a sorted array.

Method 3: Counting Out-of-Place Elements

In this approach, we count the number of elements that are not in their correct order. If there is at most one such element, the array is considered almost sorted. It’s an efficient way to solve the problem without modifying the array.

Here’s an example:

def is_almost_sorted_count(arr):
    out_of_place = 0
    for i in range(len(arr) - 1):
        if arr[i] > arr[i + 1]:
            out_of_place += 1
            if out_of_place > 1:
                return False
    return True

print(is_almost_sorted_count([1, 3, 2, 4]))

Output:

True

The function is_almost_sorted_count() iterates through the array and increments the count of out-of-place elements whenever a pair of elements is found that is not in the ascending order. It returns False immediately when more than one pair is detected, and True if at most one such pair is found, thereby identifying whether the array is almost sorted with minimal computation.

Method 4: Sorting and Comparing Indices

This method involves sorting a copy of the original array and then comparing it with the original to identify elements that are more than one position away from where they should be. If such elements are found, the array is not almost sorted.

Here’s an example:

def check_almost_sorted(arr):
    sorted_arr = sorted(arr)
    diff_index = [i for i in range(len(arr)) if arr[i] != sorted_arr[i]]
    return len(diff_index) < 3 and all(abs(i - j) < 2 for i, j in zip(diff_index, diff_index[1:]))

print(check_almost_sorted([1, 3, 2, 4]))

Output:

True

The function check_almost_sorted() creates a sorted copy of the input array and determines the indices where the elements differ. If the number of different indices is less than three and each of these indices is no more than one position away from the correct index, the function returns True, thus efficiently determining if the array is almost sorted.

Bonus One-Liner Method 5: Using List Comprehensions

This one-liner method combines the sorting and comparing indices approach into a single list comprehension. The elegance comes from Python’s ability to express complex logic concisely, providing a compact solution.

Here’s an example:

is_almost_sorted_one_liner = lambda arr: len([1 for i in range(len(arr)-1) if arr[i] > arr[i+1]]) < 2

print(is_almost_sorted_one_liner([1, 3, 2, 4]))

Output:

True

The one-liner function is_almost_sorted_one_liner() leverages a lambda function and a list comprehension to count the number of out-of-place elements. It checks whether there are fewer than two such occurrences. If so, the array is considered almost sorted. It’s a concise but less readable solution that gets the job done quickly.

Summary/Discussion

  • Method 1: Brute Force Approach. Direct. Time-consuming for large arrays. Can be inefficient due to multiple array mutations.
  • Method 2: Optimized Swap Check. Reduced operations. More efficient than the brute force. Still, involves a simulated swap to verify sorting.
  • Method 3: Counting Out-of-Place Elements. Highly efficient. No array modification. Instantly identifies if more than one swap is needed.
  • Method 4: Sorting and Comparing Indices. Non-intrusive. Relies on sorting. Offers a clear comprehension of element positions.
  • Method 5: One-Liner. Compact and fast. Less readable and potentially difficult for beginners to understand.