Grab The Best Job for you
The Cigna Group Careers 2024: Software Engineer Associate
Sort arrays Consists of 0,1,2
March 18, 2024
Advanced Array
,Programming codes
Share now
Program to Sort the arrays which consists of 0,1,2 without using Sorting Algorithm
Definition & Explanation
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:
Explanation:
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
lowand increment bothlowandmid. - If the current element is 1, we simply increment
mid. - If the current element is 2, we swap it with the element at
highand decrementhigh.
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, andhigh, where:lowpoints to the beginning of the array (initially 0).midis the current element being processed (initially 0).highpoints to the end of the array (initiallyn - 1, wherenis the size of the array).
- Iterate through the array while
midis less than or equal tohigh. - At each step:
- If the element at
midis 0, swap it with the element atlow, incrementlow, and incrementmid. This action moves all 0s to the left side of the array. - If the element at
midis 1, just incrementmid. This action maintains all 1s in the middle. - If the element at
midis 2, swap it with the element athigh, decrementhigh, but don’t incrementmid. This action moves all 2s to the right side of the array.
- If the element at
- Repeat this process until
midcrosseshigh. Once this happens, the array will be sorted with 0s, 1s, and 2s grouped together. - The sorted array is now ready.
C
Method 1 :
#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;
}
Output :
C++
Method 1 :
#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;
}
Output :
JAVA
Method 1 :
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();
}
}
Output :
Python
Method 1 :
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)
Output :
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!