Bubble Sort Algorithm in Python.

Sorting algorithms play an important role in organizing data efficiently. One such algorithm is the Bubble Sort Algorithm. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. In this article, we will understand the algorithm in detail with implementation in Python code.

Bubble Sort Algorithm for Python.

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. It proceeds until no more swaps are needed, indicating that the list is sorted.

Algorithm Steps:

• Start from the beginning of the list.
• Compare adjacent elements.
• Swap them if they are in the wrong order.
• Repeat steps 2 and 3 until the entire list is sorted.

Python Code Implementation of Bubble Sort.

Here is an example of Bubble Sort in Python:

# Python code for Bubble Sort Algorithm
def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):

        # Flag to optimize when the list is already sorted
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True

        # If no two elements were swapped, the list is sorted
        if not swapped:
            break

# Example usage:
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("Sorted array:", arr)

Output:

Sorted array: [11, 12, 22, 25, 34, 64, 90]

Time and Space Complexity.

• Time Complexity: O(n^2) in the worst-case scenario, as it involves nested loops iterating through the array. Best-case scenario (when the list is already sorted) can be O(n).

• Space Complexity: O(1) as Bubble Sort operates in place, requiring only a constant amount of extra space for variables. 

Explanation of Bubble Sort With Example.

Let's consider the example [64, 34, 25, 12, 22, 11, 90] and step through the Bubble Sort process:

Step 1: Comparing adjacent elements and swapping them if necessary.

• [34, 25, 12, 22, 11, 64, 90]
• [25, 12, 22, 11, 34, 64, 90]
• [12, 22, 11, 25, 34, 64, 90]
• [12, 11, 22, 25, 34, 64, 90]
• [11, 12, 22, 25, 34, 64, 90]

Step 2: Continuing comparisons and swaps.

• [11, 12, 22, 25, 34, 64, 90]

Step 3: The array is sorted in ascending order.

Bubble Sort is generally inefficient for larger datasets due to its quadratic time complexity. However, it can be suitable for small datasets or nearly sorted arrays. Other sorting algorithms like Merge Sort or Quick Sort offer better performance for larger datasets.

Insertion Sort Algorithm in Python.

Insertion Sort is a simple sorting algorithm that is used to sort the array/list elements in ascending or descending order. In this article, we will discuss the algorithm in detail with an example and Python code implementation.

Insertion Sort Algorithm.

Insertion Sort is a simple sorting algorithm that builds the final sorted array gradually by iterating through the elements. It divides the array into two parts: the sorted part and the unsorted part. It repeatedly takes an element from the unsorted part and places it in its correct position within the sorted part by shifting larger elements to the right. This process continues until all elements are in their correct positions, resulting in a fully sorted array. 

The insertion sort algorithm starts with the assumption that the first element is already sorted and then compares subsequent elements, inserting them into the correct position in the sorted part while shifting larger elements as needed. 

Algorithm steps:

• Step 1: Assume the first element is already sorted and consider the second element.

• Step 2: For each element in the unsorted part, compare it with elements in the sorted part.

• Step 3: If the element is smaller, shift larger elements in the sorted part to the right and insert the element at the correct position.

• Step 4: Continue the process until all elements are sorted.

Example:

Let's consider an array [5, 2, 4, 6, 1, 3] and apply Insertion Sort step by step:

1. Below is the condition of the Initial Array.

2. Iteration 1: The first element (5) is already sorted. Consider the second element (2) and compare it with the first. Since 2 < 5, swap them.

3. Iteration 2: Consider the third element (4). Compare it with elements in the sorted part (2, 5). Shift larger elements (5) to the right and insert 4 at the correct position.

4. Iteration 3: Consider the fourth element (6). It is larger than the sorted elements, so leave it as it is.

5. Iteration 4: Consider the fifth element (1). Compare it with elements in the sorted part. Shift larger elements (2, 4, 5, 6) to the right and insert 1 at the correct position.

6. Iteration 5: Consider the sixth element (3). Compare it with elements in the sorted part. Shift larger elements (4, 5, 6) to the right and insert 3 at the correct position.

7. Our Final Sorted Array is [1, 2, 3, 4, 5, 6].

Python Program for Insertion Sort Algorithm.

# Python code Implementation of Insertion Sort
def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1

        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        
        arr[j + 1] = key

# Example
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print("Sorted array:", arr)

Output:

Sorted array: [5, 6, 11, 12, 13]

• Time Complexity: O(n^2) where n is the size of the given array. 

• Space Complexity: O(1) because it uses a constant amount of extra space.

Python Program to Count Subarray with given Sum.

Given an array of integers, write a Python program to determine the number of subarrays that sum up to a given target sum. 

Example:

Input: arr = [1, 2, 3, 2, 1] sum = 3
Output: Number of Subarrays: 3

Explanation:
There are 3 subarrays sum up to the target sum of 3:
[1, 2]
[3]
[2, 1]

There are multiple approaches to solving the problem of counting subarrays with a given sum, and here we going to discuss a few of them starting from a brute force approach to more optimized solutions.

Approach 1: Brute Force.

In this brute-force method, we explore all possible subarrays within the given array and calculate the sum of each subarray to identify the count of subarrays that match the desired sum.

Algorithm:

• Use two nested loops to generate all possible subarrays.
• Calculate the sum of each subarray.
• Count the number of subarrays with the given sum.

Python Code:

# Python code to count subarrays for given sum (Brute Force)
def count_subarrays(arr, target_sum):
    count = 0
    n = len(arr)
    
    for start in range(n):
        current_sum = 0
        for end in range(start, n):
            current_sum += arr[end]
            if current_sum == target_sum:
                count += 1
    
    return count

arr = [1, 2, 3, 2, 1]
sum = 3
print("Number of Subarrays:", count_subarrays(arr, sum))

Output:

Number of Subarrays: 3

• Time Complexity: As we are checking for all possible subarrays using a nested loop the time complexity of this approach is O(n^2) where n is the length of the array.

• Space Complexity: We are not using any extra space in this approach so the space complexity is O(1).

Approach 2: Prefix Sum.

The prefix sum approach optimizes the solution by leveraging cumulative sums and a hash map to efficiently count subarrays with the given sum. It reduces the time complexity significantly compared to the brute-force method.

Algorithm:

• Calculate the cumulative sum of the array elements.
• Maintain a hash map to store the cumulative sums and their frequencies.
• Determine the count of subarrays with the given sum using the hash map.

Python Code:

# Python code to count subarray for given sum using prefix sum
def count_subarrays(arr, target_sum):
    count = 0
    prefix_sum = {0: 1}
    current_sum = 0
    
    for num in arr:
        current_sum += num
        if current_sum - target_sum in prefix_sum:
            count += prefix_sum[current_sum - target_sum]
        
        prefix_sum[current_sum] = prefix_sum.get(current_sum, 0) + 1
    
    return count

arr = [1, 4, 20, 3, 10, 5]
sum = 33
print("Number of Subarrays:", count_subarrays(arr, sum))

Output:

Number of Subarrays: 1

• Time Complexity: We are traversing the array once so the time complexity is O(n).

• Space Complexity: We are using the hash map to store cumulative sums so the space complexity is O(n).

Approach 3: Sliding Window Technique.

This is the most optimized approach to count the subarray with a given sum. The sliding window technique optimizes the solution further by using two pointers to maintain a window within the array. It dynamically adjusts the window based on the current sum, minimizing unnecessary calculations and achieving a linear time complexity.

Algorithm:

• Use two pointers, typically named left and right, to represent the window boundaries.
• Initialize left and right to the start of the array.
• Expand the window by moving the right pointer to the right.
• Adjust the window based on the current sum.
• If the current sum exceeds the desired sum or target sum, shrink the window by moving the left pointer to the right.
• Continue this process until the sum becomes less than or equal to the target sum.
• Whenever the current sum matches the desired sum, increment the count to track the subarrays that satisfy the condition.
• Continue sliding the window until the right pointer reaches the end of the array.

Python Code:

# Python code count subarrays using sliding window algorithm
def count_subarrays(arr, target_sum):
    count = 0
    current_sum = 0
    left = 0

    for right in range(len(arr)):
        current_sum += arr[right]

        while current_sum > target_sum and left <= right:
            current_sum -= arr[left]
            left += 1

        if current_sum == target_sum:
            count += 1

    return count

arr = [1, 4, 20, 3, 10, 5, 15]
sum = 33
print("Number of Subarrays:", count_subarrays(arr, sum))

Output:

Number of Subarrays: 2

• Time Complexity: In this case where the array elements are non-negative or non-zero, this technique achieves a linear time complexity, typically O(n), making it highly efficient for larger datasets.

• Space Complexity: We are not using any extra space in this sliding window approach so space complexity is O(1).

You can learn the Sliding Window Algorithm in more detail from one of our article: Sliding Window Algorithm with Example.

Python Program to Find Missing Integer in an Array.

Problem Statement.

Given an integer array of size n-1 and the array containing distinct numbers in a range of [1, n]. The task is to write a Python program to find the missing number from the array.

Example:

Input: arr = [1, 2, 3, 4, 6]
Output: Missing Number is 5

Input: arr = [3, 1, 2, 5, 7, 6]
Output: Missing Number is 4

There are multiple approaches to finding the missing number in an array and here we are going to discuss three of them.

• Using Set.
• Using XOR.
• Using Summation.

Python Program to Find Missing Number Using Set.

In this approach, we are using a set data structure to efficiently identify the missing number in a given sequence or array.

Algorithm:

• Step 1: Convert the given sequence or array into a set for efficient lookup operations.

• Step 2: Create a set containing all the numbers in the expected range or sequence.

• Step 3: Subtract the set of given numbers from the set of expected numbers. 

• Step 4: The remaining elements in the expected set would be the missing number.

Python Code:

def find_missing_integer(arr):
    n = len(arr) + 1  # Including the missing integer

    full_set = set(range(1, n + 1))
    arr_set = set(arr)

    missing_integer = full_set - arr_set

    return missing_integer.pop()

arr = [1, 2, 3, 4, 6]
print("Missing Number is",find_missing_integer(arr))

Output:

Missing Number is 5

• Time Complexity: The time complexity of the above approach is O(n) because the construction of the set takes O(n) time and the subtraction of one set with another also takes O(n) time.

• Space Complexity: The space complexity is O(n) as it requires additional space to store the sets of expected and given numbers.

Python Program to Find Missing Number of Array Using XOR.

The XOR approach utilizes the properties of the XOR operation to find the missing number in an array. XORing any number with itself results in 0 so all identical elements cancel out each other.

Algorithm:

• Step 1: Iterate through the given array and XOR all the elements with each other.

• Step 2: XOR all the numbers from 1 to n to obtain a cumulative XOR value.

• Step 3: XOR the cumulative XOR value from Step 1 with the XOR value from Step 2.

• Step 4: The result will be the missing number in the array.

Python Code:

# Python code implementation to find missing number
def find_missing_integer(arr):
    n = len(arr) + 1  
    xor_full = 0
    xor_arr = 0

    # XOR of all numbers from 1 to n
    for i in range(1, n + 1):
        xor_full ^= i

    # XOR of all numbers in the array
    for num in arr:
        xor_arr ^= num

    missing_integer = xor_full ^ xor_arr
    return missing_integer

arr = [3, 1, 2, 5, 7, 6]
print("Missing Number is",find_missing_integer(arr))

Output:

Missing Number is 4

• Time Complexity: O(n) because we have to iterate through the array to perform XOR operations.

• Space Complexity: O(1) because we have used a constant amount of extra space for variables.

Python Program to Find Missing Number of Array Using Summation.

In this approach, we are using math formulas to find the sum of the first n natural numbers. Then we subtract the sum of the array with the sum of the natural number and it will return us the missing number.

Algorithm:

• Step 1: Iterate through the given array and calculate the sum of all the elements.

• Step 2: Determine the expected sum of all the numbers in the sequence from 1 to n. This can be calculated using the formula: (n * (n+1))/2.

• Step 3: Subtract the sum of the given numbers from the expected sum. The result will be the missing number.

Python Code:

# Python code to find missing number using math
def find_missing_integer(arr):
    n = len(arr) + 1  

    expected_sum = n * (n + 1) // 2

    actual_sum = sum(arr)
    missing_integer = expected_sum - actual_sum

    return missing_integer

arr = [3, 1, 2, 5, 7, 6]
print("Missing Number is",find_missing_integer(arr))

Output:

Missing Number is 4

• Time Complexity: O(n) because we have to iterate through the array to calculate the sum of array elements.

• Space Complexity: O(1) as no extra space is required in this approach to find the missing number.

Python Programg to Find Kth Largest Number in an Array.

Given an array arr[] of size n and a number k, the task is to write a Python program to find the kth largest element from the array. Note that the value of k is always less than the size of the array and the array contain all distinct element.

Example:

Input: arr = [2, 5, 1, 6, 3, 9]  k = 2
Output: 6
Explanation: The second largest element in the array in 6

Input: arr = [12, 5, 1, 6, 3, 9, 10]  k = 3
Output: 9
Explanation: The third largest element in the array in 9

Kth Largest Element in an Array Using Sorting.

In this approach, we first sort the entire array and then retrieve the kth largest element from the sorted array.

Algorithm:

• Sort the entire array in descending order using an efficient sorting algorithm like Quicksort.

• Return the kth element from the sorted array, which represents the kth largest number.

Python Code:

def kth_largest(arr, k):
    arr.sort(reverse=True)
    return arr[k - 1]

arr = [2, 5, 1, 6, 3, 9]
k = 2
print("Kth largest element is",kth_largest(arr, k))  

Output:

Kth largest element is 6

• Time Complexity: O(n log n) for sorting + O(1) for retrieving kth element = O(n log n).

• Space Complexity: Depends on the sorting algorithm, generally O(log n) for efficient algorithms, up to O(n) in worst-case scenarios.

Kth Largest Element in an Array Using Heap.

In this approach, we are going to use min-heap to efficiently find the kth largest element without sorting the entire array.

Algorithm:

• Create a min-heap of size k and insert the first k elements from the array into the heap.

• The root of the min-heap will always be the smallest element among the k elements.

• For the remaining elements in the array, compare each element with the root of the heap.

• If the element is larger than the root, replace the root with this element and re-heapify the min-heap to maintain its structure.

• After traversing through the entire array, the root of the min-heap will be the kth largest element.

Python Code:

import heapq

def kth_largest_heap(arr, k):
    heap = arr[:k]
    heapq.heapify(heap)
    
    for num in arr[k:]:
        if num > heap[0]:
            heapq.heappop(heap)
            heapq.heappush(heap, num)
    
    return heap[0]

arr =[12, 5, 1, 6, 3, 9, 10]  
k = 3
print("Kth largest element is", kth_largest_heap(arr, k))  

Output:

Kth largest element is 9

Time Complexity:

Building the initial min-heap with the first k elements takes O(k) time. For the remaining (n-k) elements, each insertion and re-heapification operation takes O(log k) time. Therefore, the overall time complexity is O(n log k).

Space Complexity:

The space complexity is O(k) to maintain the min-heap of size k.

Quickselect Algorithm to Find the Kth Largest Number.

Quickselect is an algorithm used to find the kth smallest or largest element in an unsorted array. It's an optimization of the quicksort algorithm.

Algorithm:

• Choose a pivot element from the array. Rearrange the elements in the array such that elements smaller than the pivot are on the left, and elements greater than the pivot are on the right.

• Based on the position of the pivot after partitioning, the pivot's index is compared to k - 1.

• If the pivot index is equal to k - 1, then the pivot is the kth largest element. Return the pivot.

• If the pivot index is less than k - 1, the kth largest element must be in the right subarray. Recur for the right subarray.

• If the pivot index is greater than k - 1, the kth largest element must be in the left subarray. Recur for the left subarray.

• Repeat the process until the pivot's index is equal to k - 1.

Python Code:

# Python code to find kth largest element from array
def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1

    for j in range(low, high):
        if arr[j] >= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def quickselect(arr, low, high, k):
    if low <= high:
        pivot_index = partition(arr, low, high)     

        if pivot_index == k - 1:
            return arr[pivot_index]
        elif pivot_index > k - 1:
            return quickselect(arr, low, pivot_index - 1, k)
        else:
            return quickselect(arr, pivot_index + 1, high, k)

def kth_largest(arr, k):
    return quickselect(arr, 0, len(arr) - 1, k)

arr = [3, 6, 8, 9, 12, 51, 13] 
k = 3
print("Kth largest element is", kth_largest(arr, k))

Output:

Kth largest element is 12

• Time Complexity: The average time complexity is O(n) but in the worst case, Quickselect's time complexity can degrade to O(n^2).

• Space Complexity: Quickselect has a space complexity of O(log n) for the recursive call stack due to its recursive nature.

Python Program to Left Rotate an Array.

Problem Statement: You are given an array of integers and an integer K. Implement a Python program to perform a left rotation on the array K times. Left rotation means that each array element will be shifted K places to the left, and the elements overflowing from the left side will be placed at the end of the array.

Example:

Input: 
Given array: [1, 2, 3, 4, 5, 6]
Number of rotations: 2

Output:
[3, 4, 5, 6, 1, 2]

Explanation:

The array [1, 2, 3, 4, 5, 6] is rotated twice to the left. In each rotation, the elements shift to the left by two positions. After the first rotation, the array becomes [2, 3, 4, 5, 6, 1]. After the second rotation, it becomes [3, 4, 5, 6, 1, 2]. 

Left Rotation of an Array

Python Program to Left Rotation Using Brute Force Approach.

The simplest approach to left-rotate an array is to perform one rotation at a time for the specified number of positions. 

Brute Force Algorithm:

1. This Algorithm involves an outer loop that runs K times to perform the specified number of rotations.
2. Inside each iteration of the loop, the following steps are executed to perform a single left rotation:
   • Store the first element of the array in a temporary variable to prevent its value from being overwritten.
   • Shift all other elements one position to the left. This is done by iterating through the array and assigning each element the value of the element at the next index.
   • Place the temporary variable (the original first element) at the end of the array, effectively completing one left rotation.
3. This process of rotating the array K times is repeated for the specified number of rotations.

Example Illustration:

Python Code:

# Python code to left rotate array (Brute Force)
def left_rotate_array(arr, k):
     length = len(arr)
     for i in range(k):
           # store the first element
           temp = arr[0]
           
           # Shift all other elements to the left
           for i in range(length - 1):
                  arr[i] = arr[i + 1]
           
            # Place the first element at the end
            arr[length - 1] = temp

# Example usage:
given_array = [1, 2, 3, 4, 5]
rotations = 2

print("Original array:", given_array)
left_rotate_array(given_array, rotations)
print(f"After {rotations} left rotations:", given_array)

Output:

Original array: [1, 2, 3, 4, 5]
After 2 left rotations: [3, 4, 5, 1, 2]

• Time Complexity: O(n * d) where n is the length of the array and d is the number of positions to rotate. This can be inefficient for large arrays or a high number of rotations.

• Space Complexity: O(1) no extra space is required to rotate the array using this method.

Python Program to Rotate an Array Using Slicing.

The array left rotation algorithm using slicing in Python involves manipulating the original array to create a left-rotated version without individually moving each element.

Algorithm Explanation:

To handle scenarios where the number of rotations ('k') exceeds the array's length, take the modulo of 'k' with the array's length. This step ensures that 'k' remains within the range of the array's length.

• Create a new list called rotated_array by using Python's list slicing.

• Slice the original array (arr) from index 'k' to the end (arr[k:]). This extracts the elements that need to be moved to the beginning after rotation.

• Concatenate (+) this slice with the portion of the array from the start to index 'k' (arr[:k]). This captures the elements that should be moved to the end after rotation.

• This combination represents the left-rotated version of the array.

• Update the original array (arr) with the values from the rotated_array.

• Iterate through the rotated_array and assign each value to the corresponding index in the original array.

• This step replaces the elements in the original array with the left-rotated elements.

Example Illustration:

This slicing approach efficiently handles left rotation without individually moving each element, making it a concise and Pythonic way to achieve the desired rotation.

Python Code:

def left_rotate_array(arr, k):
    length = len(arr)
    k = k % length  # Ensure k is within array length
    
    # Slicing to perform left rotation
    rotated_array = arr[k:] + arr[:k]
    
    # Update original array with rotated values
    for i in range(length):
        arr[i] = rotated_array[i]

# Example usage:
given_array = [1, 2, 3, 4, 5]
rotations = 2

print("Original array:", given_array)
left_rotate_array(given_array, rotations)
print(f"After {rotations} left rotations:", given_array)

Output:

Original array: [1, 2, 3, 4, 5]
After 2 left rotations: [3, 4, 5, 1, 2]

• Time Complexity: Slicing in Python takes (n) time complexity, where n is the number of elements being sliced and concatenated.

• Space Complexity: O(n) because we have created a temporary array for rotation.

Python Program to Rotate an Array Using Reversal Algorithm.

The reversal algorithm involves three steps to perform left rotation on an array.

Reversal Algorithm:

• Reverse the elements from the start of the array up to the k index.

• Reverse the elements from the k index to the end of the array.

• Reverse the entire array to obtain the final left-rotated array.

Example Illustration:

Python Code:

def reverse_array(arr, start, end):
    while start < end:
        arr[start], arr[end] = arr[end], arr[start]
        start += 1
        end -= 1

def left_rotate_array(arr, k):
    length = len(arr)
    k = k % length  # Ensure k is within array length for multiple rotations
    
    # Reverse the first part: from start to k
    reverse_array(arr, 0, k - 1)
    
    # Reverse the second part: from k to end
    reverse_array(arr, k, length - 1)
    
    # Reverse the entire array
    reverse_array(arr, 0, length - 1)

# Example usage:
given_array = [1, 2, 3, 4, 5]
rotations = 2

print("Original array:", given_array)
left_rotate_array(given_array, rotations)
print(f"After {rotations} left rotations:", given_array)

Output:

Original array: [1, 2, 3, 4, 5]
After 2 left rotations: [3, 4, 5, 1, 2]

• Time Complexity: For each reversal operation it will take O(n) time so the overall time complexity will be O(n) where n is the number of elements.

• Space Complexity: The algorithm uses a constant amount of extra space O(1).

So these are a few approaches to left-rotate an array in Python. Each approach has different space and time complexity so you can choose the most optimized one for your solution.