**Grab The Best Job for you**

March 18, 2024

Advanced Array

,Programming codes

**Grab The Best Job for you**

**Share now **

The problem you’re describing is known as the “Dutch National Flag Problem,” where you need to sort an array containing only 0s, 1s, and 2s without using a sorting algorithm like quicksort or mergesort. This can be achieved efficiently using a technique called the “Dutch National Flag Algorithm,” which was designed by Edsger W. Dijkstra.

Here’s an explanation followed by implementations in C++, Java, and C:

The idea of the Dutch National Flag Algorithm is to partition the array into three sections:

- The first section consists of all 0s.
- The second section consists of all 1s.
- The third section consists of all 2s.

We maintain three pointers:

`low`

: Points to the beginning of the array.`mid`

: Points to the current element being processed.`high`

: Points to the end of the array.

We iterate through the array, moving the elements to their appropriate sections. Specifically:

- If the current element is 0, we swap it with the element at
`low`

and increment both`low`

and`mid`

. - If the current element is 1, we simply increment
`mid`

. - If the current element is 2, we swap it with the element at
`high`

and decrement`high`

.

This way, after traversing the array once, all 0s will be to the left of `mid`

, all 2s will be to the right of `high`

, and all 1s will be between `mid`

and `high`

.

**More Description**

Program Logic

- Initialize three variables
`low`

,`mid`

, and`high`

, where:`low`

points to the beginning of the array (initially 0).`mid`

is the current element being processed (initially 0).`high`

points to the end of the array (initially`n - 1`

, where`n`

is the size of the array).

- Iterate through the array while
`mid`

is less than or equal to`high`

. - At each step:
- If the element at
`mid`

is 0, swap it with the element at`low`

, increment`low`

, and increment`mid`

. This action moves all 0s to the left side of the array. - If the element at
`mid`

is 1, just increment`mid`

. This action maintains all 1s in the middle. - If the element at
`mid`

is 2, swap it with the element at`high`

, decrement`high`

, but don’t increment`mid`

. This action moves all 2s to the right side of the array.

- If the element at
- Repeat this process until
`mid`

crosses`high`

. Once this happens, the array will be sorted with 0s, 1s, and 2s grouped together. - The sorted array is now ready.

C

```
#include <stdio.h>
void sort012(int arr[], int n) {
int low = 0, mid = 0, high = n - 1;
while (mid <= high) {
if (arr[mid] == 0) {
int temp = arr[mid];
arr[mid] = arr[low];
arr[low] = temp;
low++;
mid++;
} else if (arr[mid] == 1) {
mid++;
} else {
int temp = arr[mid];
arr[mid] = arr[high];
arr[high] = temp;
high--;
}
}
}
int main() {
int arr[] = {0, 1, 2, 0, 1, 2};
int n = sizeof(arr) / sizeof(arr[0]);
sort012(arr, n);
printf("Sorted array: ");
for (int i = 0; i < n; ++i) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
```

C++

```
#include <iostream>
using namespace std;
void sort012(int arr[], int n) {
int low = 0, mid = 0, high = n - 1;
while (mid <= high) {
if (arr[mid] == 0) {
swap(arr[mid], arr[low]);
low++;
mid++;
} else if (arr[mid] == 1) {
mid++;
} else {
swap(arr[mid], arr[high]);
high--;
}
}
}
int main() {
int arr[] = {0, 1, 2, 0, 1, 2};
int n = sizeof(arr) / sizeof(arr[0]);
sort012(arr, n);
cout << "Sorted array: ";
for (int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
```

JAVA

```
public class Sort012 {
static void sort012(int arr[], int n) {
int low = 0, mid = 0, high = n - 1;
while (mid <= high) {
if (arr[mid] == 0) {
int temp = arr[mid];
arr[mid] = arr[low];
arr[low] = temp;
low++;
mid++;
} else if (arr[mid] == 1) {
mid++;
} else {
int temp = arr[mid];
arr[mid] = arr[high];
arr[high] = temp;
high--;
}
}
}
public static void main(String[] args) {
int arr[] = {0, 1, 2, 0, 1, 2};
int n = arr.length;
sort012(arr, n);
System.out.print("Sorted array: ");
for (int i = 0; i < n; ++i) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
```

Python

```
def sort(arr):
# Note: We cannot use sort function
# we will find the count of 0,1,2 in the given array with help of count function
count_0 = arr.count(0)
count_1 = arr.count(1)
count_2 = arr.count(2)
# declare new array
new_arr = []
# append 0 to new array
for i in range(count_0):
new_arr.append(0)
for i in range(count_1):
new_arr.append(1)
for i in range(count_2):
new_arr.append(2)
print(" After sorting:", new_arr)
array = [1, 2, 0, 2, 1, 0, 2, 1, 0, 2, 0, 1]
print("Before Sorting:", array)
# call function
sort(array)
```

```
Before Sorting: [1, 2, 0, 2, 1, 0, 2, 1, 0, 2, 0, 1]
After sorting: [0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2]
```

**DataTpoint, your ultimate destination for navigating the dynamic landscape of career opportunities in the data and technology realm.Whether you’re an experienced data scientist, a tech enthusiast, or a recent graduate eager to dive into the world of data-driven innovation, DataTpoint has curated an extensive collection of high-paying job listings and premium opportunities.Explore a diverse range of full-time, part-time, remote, and contract positions in fields such as data analytics, artificial intelligence, software development, and more.Our intuitive platform empowers you to effortlessly discover roles tailored to your skills and preferences. Leverage our advanced search and filtering tools to pinpoint the perfect career path for you. DataTpoint goes beyond conventional job searches; we are dedicated to facilitating your career growth.Utilize our resume-building tools, personalized job alerts, and insightful resources to enhance your job-seeking experience. Connect with top-tier companies that align with your professional goals.Your journey to a rewarding career in the data and technology space, coupled with lucrative opportunities, starts here at DataTpoint. Begin your exploration!**