Consider an input string S of digits 0, 1, and 2. This string, which is given by
ID: 3792008 • Letter: C
Question
Consider an input string S of digits 0, 1, and 2. This string, which is given by the user, ends with '#'. It should be stored in a table (or array), called Digits. The number of each of these digits is unknown. We have a function, called SWAP (S, i, j, ) which places the i^th digit in the j^th entry of S and the j^th digit in the i^th entry of S. Note that SWAP (S, i, j) is defined for all integers i and j between 0 and length (S)-1, where length(S) is the number of digits of a string S Write an algorithm, called Sort _ 102, which sorts the digits in the array Digits in a way that all 1's appear first, followed by all 0's, and followed by all 2's. The algorithm Sort _ 102 should have one parameter: The array Digits. Also, your solution will be correct only if the following four constraints are satisfied: Each digit (0, 1, or 2) is evaluated only once The function SWAP(S, i, j, ) is used only when it is necessary No extra space can be used by the algorithm Sort _ 102. In other words, only the array Digits can be used to sort the 0, l, or 2. You cannot count the number of each digit 0, 1, or 2. Show that the algorithm Sort _ 102 is correct using an informal proof (i.e., discussion). Give a program corresponding to Sort _ 102 using C + + programming language.Explanation / Answer
Algorithm:
1. Low := 1; Mid := 1; High := N;
2. while Mid <= High do
1. Invariant: a[1..Low-1]=0 and a[Low..Mid-1]=1 and a[High+1..N]=2; a[Mid..High] are unknown.
2. case a[Mid] in
0: swap a[Low] and a[Mid]; Low++; Mid++
1: Mid++
2: swap a[Mid] and a[High]; High–
Program:
#include <iostream>
using namespace std;
//Swap function that accepts an array and the entries i and j
void swap(string &S, int i, int j)
{
char temp = S[i];
S[i] = S[j];
S[j] = temp;
}
//This Function accepts an array and performs operation to sort them
void sort102(string &Digits)
{
int arr_size = Digits.length();
int lo = 0;
int hi = arr_size - 2;
int mid = 0;
while (mid <= hi)
{
switch (Digits[mid])
{
case '1':
swap(Digits, lo++, mid++);
break;
case '0':
mid++;
break;
case '2':
swap(Digits, mid, hi--);
break;
}
}
cout << Digits;
}
int main() {
string Digits;
cout << "Enter a String which contains digits 0,1 and 2 ending with # ";
cin >> Digits;
sort102(Digits);
}