Heap Sort Algorithm in Python.

Heap Sort is a comparison-based sorting algorithm that uses a Binary Heap data structure to sort elements in an array. In this article, we will discuss the algorithm in detail with Python code implementation.

Heap Sort Algorithm Explanation.

Heap Sort is a sorting algorithm that utilizes the principles of a Binary Heap data structure to sort elements within an array. The process begins by constructing a Max Heap or Min Heap from the unsorted array, ensuring that the root node holds the maximum (or minimum) value compared to its children in the Max Heap (or vice versa in a Min Heap). 

In the next step, the algorithm performs heapify operations, involving reorganization of the heap after each element removal to maintain heap property. During the sorting phase, elements are sequentially removed from the heap, starting from the root node. After each removal, the remaining elements undergo heapify operations to preserve the heap structure. The removed elements are stored in the array, ultimately resulting in a sorted arrangement.

Heap Sort Algorithm Steps:

• Convert the unsorted array into a Max Heap or Min Heap.
• Perform heapify operations to maintain the heap property after each element removal.
• Sequentially remove elements from the heap, starting from the root node. After each removal, reorganize the heap to maintain the heap property.
• Store the removed elements in an array to obtain the sorted order. 

Python Program for Heap Sort Algorithm.

Below is the code implementation of the Heap Sort Algorithm using Python language.

Python Code:

# Python Code implementatin for Heap Sort Algorithm
def heapify(arr, n, i):
    largest = i  # Initialize largest as root
    left = 2 * i + 1  # Left child
    right = 2 * i + 2  # Right child

    # Check if left child exists and is greater than root
    if left < n and arr[left] > arr[largest]:
        largest = left

    # Check if right child exists and is greater than root
    if right < n and arr[right] > arr[largest]:
        largest = right

    # Change root if needed
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # Swap
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)

    # Build a max heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # Extract elements one by one
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # Swap root with last element
        heapify(arr, i, 0)  # Heapify root element

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

Output:

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

Time Complexity: The time complexity of Heap Sort in all cases is O(n log n). Building the heap takes O(n) time, and for each element, heapify takes O(log n) time. As there are n elements, the total time complexity is O(n log n).

Space Complexity: Heap Sort has a space complexity of O(1) as it performs sorting in place, utilizing the input array without requiring additional space.

Heap Sort Using Python Built-in Function.

In Python, the heapq module provides a heap sort functionality through the heapify() and heappop() functions. These functions enable Heap Sort by creating a min-heap and extracting elements one by one, resulting in a sorted list.

Main functions of heapq module:

• heapify(iterable): Converts a given iterable (such as a list) into a heap in place. The function rearranges the elements so that they satisfy the heap property.

• heappush(heap, item): Adds an element item to the heap while maintaining the heap property.

• heappop(heap): Removes and returns the smallest element (root) from the heap while maintaining the heap property.

Python Code:

# Heap Sort Algorithm using heapq module
import heapq

def heap_sort(arr):
    # Convert the input list into a min-heap
    heapq.heapify(arr)  

    sorted_list = []
    while arr:
    # Extract elements one by one 
       sorted_list.append(heapq.heappop(arr))  
    return sorted_list

# Example usage:
arr = [12, 11, 13, 5, 6, 7]
sorted_array = heap_sort(arr)
print("Sorted array:", sorted_array)

Output:

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

Time Complexity: O(n log n)

Space Complexity: O(1)

Merge Sort Algorithm in Python.

MergeSort is a popular sorting algorithm known for its efficiency and stability. It operates by dividing the unsorted list into smaller sub-lists and then merging them back together to produce a sorted list. It is very similar to the Quick Sort Algorithm. In this article, we are going to understand the Merge Sort algorithm in detail with Python code implementation.

Merge Sort Algorithm Explanation.

The merge sort algorithm is based on the divide and conquer approach in which we continuously divide the given list into smaller units to create sorted sub-lists and then merge them back to create a final sorted list.  

 

Algorithm Steps:

• Start with an unsorted list/array.
• Divide the list into smaller sub-lists recursively until each sub-list contains only one element. This process is achieved recursively.
• Combine the smaller sorted sub-lists back together by comparing and merging adjacent pairs of sub-lists.
• Merge these pairs in a sorted manner to create larger sorted sub-lists. 

Python Program for Merge Sort Algorithm.

Below is the code implementation of Merge Sort Algorithm in Python:

# Python code implementation of Merge Sort
def merge_sort(arr):
    if len(arr) > 1:
        # Find the middle of the list
        mid = len(arr) // 2 
 
        # Divide the list into two halves
        left_half = arr[:mid]  
        right_half = arr[mid:]

        # Recursive call to sort the left half
        merge_sort(left_half)  
        
        # Recursive call to sort the right half
        merge_sort(right_half)  

        # Merge the sorted halves
        i = j = k = 0  # Initialize indices for merging
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        # Check for remaining elements in left and right halves

        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

# Example usage:
arr = [64, 34, 25, 12, 20, 10, 90]
merge_sort(arr)
print("Sorted array:", arr)

Output:

Sorted array: [10, 12, 20, 25, 34, 64, 90]

Time Complexity: Merge Sort demonstrates a time complexity of O(n log n) across all cases. This efficiency makes Marge Sort highly desirable for sorting larger datasets. 

Space Complexity: O(n). Merge Sort's space complexity primarily involves auxiliary space for temporary arrays during the merging phase.

Quick Sort Algorithm in Python.

Quick Sort is a highly efficient sorting algorithm that arranges elements in ascending or descending order. It operates based on the divide and conquer strategy, dividing the array into smaller segments, and then sorting those segments recursively to achieve the final sorted array. It is very much similar to the Merge Sort Algorithm.

Quick Sort Algorithm Explanation.

In Quick Sort, we have to choose a pivot element, a chosen value from the array around which partitioning occurs. This pivotal choice significantly influences the algorithm's efficiency. Our goal is to select a pivot that helps create balanced partitions, ensuring the array gets divided into approximately equal halves during each recursive call.

Select the First and Last Element as Pivot:

• Selecting the first and last element as the pivot is simple and efficient in implementation. However, this approach might lead to unbalanced partitions if the array is already sorted or nearly sorted.

Select the Last Element as Pivot:

• Choosing the middle element of the array as the pivot. This method often provides a better pivot choice, especially for larger datasets.

Quick Sort Algorithm Steps:

• Step 1: Select an element from the array as the pivot (commonly the last element).

• Step 2: Rearrange the elements in the array so that elements smaller than the pivot are placed before it, while elements larger than the pivot are placed after it. 

• Step 3: After Step 2,  the pivot assumes its correct position in the sorted array.

• Step 4: Apply Quick Sort recursively to the subarrays formed by partitioning until the entire array is sorted.

Python Program for Quick Sort Algorithm.

Below is the code implementation of the Quick Sort Algorithm using Python programming.

# Python code implementation of Quick Sort Algorithm
def partition(arr, low, high):
    # Choose the last element as the pivot    
    pivot = arr[high]  
    i = low - 1  # Index of smaller element
    
    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 quick_sort(arr, low, high):
    if low < high:
        # Partitioning index
        pi = partition(arr, low, high)

        # Recursively sort elements before and after partition
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)

# Example usage:
arr = [64, 34, 25, 12, 22, 11, 90]
quick_sort(arr, 0, len(arr) - 1)
print("Sorted array:", arr)

Output:

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

Time Complexity: In the best and average cases, where the pivot consistently divides the array into roughly equal halves, Quick Sort achieves a time complexity of O(n log n). However, in the worst-case scenario, where the pivot selection leads to highly unbalanced partitions, Quick Sort's time complexity degrades to O(n^2).

Space Complexity: In the average case, the maximum space required for the recursive call stack is O(log n), as the array gets divided into smaller segments. 

Selection Sort Algorithm in Python.

Sorting algorithms offer a unique approach to arranging data efficiently in ascending or descending order. Among these techniques stands Selection Sort, a straightforward yet essential algorithm that systematically organizes elements by repeatedly selecting the minimum value and placing it at the beginning. In this article, we will explore the Selection Sort Algorithm in detail with Python implementation, and understand its strengths and limitations in sorting data.

Python Program for Selection Sort Algorithm.

Selection Sort is a simple sorting algorithm that works by repeatedly finding the minimum element from the unsorted part of the array and putting it at the beginning. It divides the array into two parts: the sorted part and the unsorted part. The algorithm finds the smallest element from the unsorted part and swaps it with the first unsorted element, incrementing the sorted part’s size by one.

Algorithm Steps:

• Start from the beginning of the list.
• Find the minimum element in the unsorted part.
• Swap it with the first unsorted element.
• Increment the sorted part’s size by one.
• Repeat steps 2-4 until the entire list is sorted.

Python Code Implementation for Selection Sort.

Here is an example of Selection Sort in Python:

# Python code for Selection Sort Algorithm
def selection_sort(arr):
    n = len(arr)
    for i in range(n):

        min_idx = i

        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

# Example usage:
arr = [64, 34, 25, 12, 22, 11, 90]
selection_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) as it involves nested loops iterating through the array, making it inefficient for larger datasets.

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

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.

Prefix Sum Technique Explanation.

The Prefix Sum Technique, also known as Prefix Sum Array or Cumulative Sum Array, is a methodology used to efficiently compute and store cumulative sums of elements in an array. It enables fast retrieval of the sum of elements within a specific range of indices in constant time.

Prefix Sum Technique Explanation.

Below are the steps that we need to follow to create a Prefix Sum Array:

• Given an array arr of size n, the prefix sum at index i, denoted as prefix[i], represents the sum of elements from index 0 to index i-1 in the original array arr.

• The first element of the prefix sum array prefix[0] is initialized as 0 and subsequent elements prefix[i] are computed by adding the current element in the original array arr[i-1] to the previous prefix sum prefix[i-1].

• Use this formula to find the sum of elements within a range [left, right] (inclusive) in the original array: sum_range = prefix[right + 1] - prefix[left].

Example:

Let's understand the working with one example,

Original Array:
[3, 1, 7, 4, 2, 0, 5]

Prefix Sum Array:
[0, 3, 4, 11, 15, 17, 17, 22]

Calculation of Prefix Sum Array:
prefix[0] = 0 (initialized)
prefix[1] = prefix[0] + arr[0] = 0 + 3 = 3.
prefix[2] = prefix[1] + arr[1] = 3 + 1 = 4
prefix[3] = prefix[2] + arr[2] = 4 + 7 = 11.
prefix[4] = prefix[3] + arr[3] = 11 + 4 = 14.
prefix[5] = prefix[4] + arr[4] = 14 + 1 = 15.
prefix[6] = prefix[5] + arr[5] = 15 + 2 = 17.
prefix[7] = prefix[6] + arr[6] = 17 + 5 = 22.

To find the sum of elements between indices 2 and 5 (inclusive):

• sum_range = prefix[6] - prefix[2] = 17 - 4 = 13

Prefix Sum Code Implementation.

Now I hope that you understand the basic workings of the Prefix Sum Array Technique and why it is so popularly used for solving many coding problems. Let's see the code implementation of this in different programming languages.

C Implementation:

// C Code Implementation of Prefix Sum Array
#include <stdio.h>

void prefixSum(int arr[], int prefix[], int n) {
    prefix[0] = 0; // Initialization

    for (int i = 1; i <= n; i++) {
        prefix[i] = prefix[i - 1] + arr[i - 1];
    }
}

int main() {
    int arr[] = {3, 1, 7, 4, 2, 0, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    int prefix[n + 1];
    prefixSum(arr, prefix, n);

    printf("Prefix Sum Array: ");
    for (int i = 0; i <= n; i++) {
        printf("%d ", prefix[i]);
    }
    printf("\n");

    return 0;
}

Output:

Prefix Sum Array: 0 3 4 11 15 17 17 22

C++ Implementation:

// C++ Code Implementation of Prefix Sum Array Technique
#include <iostream>
#include <vector>
using namespace std;

void prefixSum(vector<int>& arr, vector<int>& prefix) {
    prefix[0] = 0; // Initialization

    for (int i = 1; i <= arr.size(); i++) {
        prefix[i] = prefix[i - 1] + arr[i - 1];
    }
}

int main() {
    vector<int> arr = {3, 1, 7, 4, 2, 0, 5};
    int n = arr.size();

    vector<int> prefix(n + 1);
    prefixSum(arr, prefix);

    cout << "Prefix Sum Array: ";
    for (int i = 0; i <= n; i++) {
        cout << prefix[i] << " ";
    }
    cout << endl;

    return 0;
}

Output:

Prefix Sum Array: 0 3 4 11 15 17 17 22

Java Implementation:

// Java Code Implementation to Print Prefix Sum Array
public class PrefixSum {
    public static void prefixSum(int[] arr, int[] prefix) {
        prefix[0] = 0; // Initialization

        for (int i = 1; i <= arr.length; i++) {
            prefix[i] = prefix[i - 1] + arr[i - 1];
        }
    }

    public static void main(String[] args) {
        int[] arr = {3, 1, 7, 4, 8, 0, 5};
        int n = arr.length;

        int[] prefix = new int[n + 1];
        prefixSum(arr, prefix);

        System.out.print("Prefix Sum Array: ");
        for (int i = 0; i <= n; i++) {
            System.out.print(prefix[i] + " ");
        }
        System.out.println();
    }
}

Output:

Prefix Sum Array: 0 3 4 11 15 23 23 28 

Python Implementation:

# Python Code Implementation for Prefix Sum Array
def prefix_sum(arr):
    n = len(arr)
    prefix = [0] * (n + 1)

    for i in range(1, n + 1):
        prefix[i] = prefix[i - 1] + arr[i - 1]

    return prefix

arr = [3, 11, 7, 4, 2, 0, 5]
prefix = prefix_sum(arr)
print("Prefix Sum Array:", prefix)

Output:

Prefix Sum Array: 0 3 14 21 25 27 27 32 

• Time Complexity: O(n) because we need to traverse the complete array at least once to create the prefix sum array.

• Space Complexity: O(n) because we are creating a new prefix sum array of the same size to store the calculated prefix sum of the given array.

Key Points About Prefix Sum Array.

• Efficiency: Precomputing prefix sums allow quick retrieval of range sums without recomputation.
• Constant Time Complexity: Retrieving a range sum is achieved in constant time O(1) by subtracting prefix sums.
• Preprocessing Overhead: Additional space O(n) is required to store the prefix sum array.

The Prefix Sum Technique is commonly used in scenarios where frequent range sum queries need to be answered efficiently, such as in computational geometry, image processing, and various algorithm problems.

Dutch National Flag Algorithm | Explanation | Code.

The Dutch National Flag algorithm is a Computer Science problem proposed by Edsger W. Dijkstra, a Dutch computer scientist. It is used for sorting an array of 0s, 1s, and 2s (or any other two distinct elements). It partitions the array into three segments - the low segment containing 0s, the middle segment containing 1s, and the high segment containing 2s.

Dutch National Flag Problem.

Given an array containing elements that can take one of three distinct values (e.g., red, white, and blue), the task is to sort the array in place such that elements of the same value are grouped together and the array is partitioned into three sections:

• All elements less than a certain value (e.g., red).
• All elements equal to that value.
• All elements greater than a certain value (e.g., blue).

Example:

Suppose the array represents colors: [1, 0, 2, 1, 0, 2] (0 for red, 1 for white, 2 for blue).

Initial Array:
[1, 0, 2, 1, 0, 2]

Sorted Array:
[0, 0, 1, 1, 2, 2]

Dutch National Flag Algorithm Explain.

This algorithm is used for partitioning elements within an array containing multiple distinct values, grouping similar elements together efficiently in a single pass through the array.

Step 1: Initialize three-pointers low, mid, and high where low and mid-pointers point to the start of the array and high pointer points to the end of the array.

Step 2: Start iterating through the array while mid is less than or equal to high:

• If the element at mid is the lower value (0) then swap the element at low with the element at mid and increment both low and mid.
• If the element at mid is the middle value (1) then increment mid by 1.
• If the element at mid is the higher value (2) then swap the element at mid with the element at high and decrement high.

Step 3: Keep repeating step 2 until mid crosses high, ensuring all elements are appropriately sorted. 

Working Example of Dutch National Flag Algorithm.

This algorithm basically sorts an array containing only three different types of values. Below we are showing the operation it performs in each iteration.

Iteration	Array	Operation/Description
1.	[1, 0, 2, 1, 0, 2]	Initial array
2.	[0, 0, 2, 1, 1, 2]	Swap 1 at index 0 with 0 at index 1
3.	[0, 0, 2, 1, 1, 2]	Increment 'mid'
4.	[0, 0, 2, 1, 1, 2]	Increment 'mid'
5.	[0, 0, 2, 1, 1, 2]	Swap 2 at index 2 with 2 at index 5
6.	[0, 0, 1, 1, 2, 2]	Decrement 'high' and Increment 'mid'

I hope that now you have understood the workings of the Dutch National Flag Algorithm and we are going to implement this algorithm using different programming languages such as C, C++, Python, and Java.

C Code Implementation:

// C Code Implementation of Dutch National Flag Algorithm
#include <stdio.h>

// Function to swap two values
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// function definition
void sortColors(int* nums, int numsSize) {
    int low = 0, mid = 0, high = numsSize - 1;

    while (mid <= high) {
        switch(nums[mid]) {
            case 0:
                swap(&nums[low++], &nums[mid++]);
                break;
            case 1:
                mid++;
                break;
            case 2:
                swap(&nums[mid], &nums[high--]);
                break;
        }
    }
}

int main() {
    int nums[] = {1, 0, 2, 1, 0, 2};
    int numsSize = sizeof(nums) / sizeof(nums[0]);

    sortColors(nums, numsSize);

    printf("Sorted Array: ");
    for (int i = 0; i < numsSize; ++i) {
        printf("%d ", nums[i]);
    }
    printf("\n");

    return 0;
}

Output:

Sorted Array: 0 0 1 1 2 2

C++ Code Implementation:

// C++ code implementation of Dutch National Flag Algorithm
#include <iostream>
#include <vector>
using namespace std;

void sortColors(vector<int>& nums) {
    int low = 0, mid = 0, high = nums.size() - 1;

    while (mid <= high) {
        switch(nums[mid]) {
            case 0:
                swap(nums[low++], nums[mid++]);
                break;
            case 1:
                mid++;
                break;
            case 2:
                swap(nums[mid], nums[high--]);
                break;
        }
    }
}

int main() {
    vector<int> nums = {1, 0, 2, 1, 0, 2};

    sortColors(nums);

    cout << "Sorted Array: ";
    for (int i = 0; i < nums.size(); ++i) {
        cout << nums[i] << " ";
    }
    cout << endl;

    return 0;
}

Output:

Sorted Array: 0 0 1 1 2 2

Java Code Implementation:

// Java Code Implementation for Dutch National Flag Algorithm
public class DutchNationalFlag {
    // Function
    public static void sortColors(int[] nums) {
        int low = 0, mid = 0, high = nums.length - 1;

        while (mid <= high) {
            switch(nums[mid]) {
                case 0:
                    int tempLow = nums[low];
                    nums[low++] = nums[mid];
                    nums[mid++] = tempLow;
                    break;
                case 1:
                    mid++;
                    break;
                case 2:
                    int tempHigh = nums[high];
                    nums[high--] = nums[mid];
                    nums[mid] = tempHigh;
                    break;
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 0, 2, 1, 0, 2};

        sortColors(nums);

        System.out.print("Sorted Array: ");
        for (int num : nums) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

Output:

Sorted Array: 0 0 1 1 2 2

Python Code Implementation:

# Python Code Implementation of Dutch National Flag Algorithm
def sortColors(nums):
    low, mid, high = 0, 0, len(nums) - 1

    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1

nums = [1, 0, 2, 1, 0, 2]

sortColors(nums)

print("Sorted Array:", nums)

Output:

Sorted Array: 0 0 1 1 2 2

Time and Space Complexity.

Time Complexity: The Dutch National Flag Algorithm processes each element in the array exactly once so the time complexity is O(n) where n is the number of elements in the array.

Space Complexity: The algorithm performs sorting in the same array without using additional data structures. It uses only a few variables (pointers) to manipulate the array elements, resulting in contact space usage O(1).