Problem Solving: Introduction to Sets

Learn to read sets from a file and to sort and display them.

We'll cover the following

In this lesson, we’ll work on sets. Sets are a well-defined collection of non-repetitive objects. In our case, we’ll only be looking at the sets of integers.

In this lesson, we’ll learn to:

  • Read integer sets from a file
  • Sort the integer sets
  • Display the sets

So let’s start!

Reading sets from a file

Task: Load the two sets A and B from the file.

The file has the following format:

The two sizes (size of A and size of B) followed by set A and set B entries.

Here is a sample file:

sets.txt
________

5 6
10 2 3 4 5
2 3 4 7 8 10

As we know, a set cannot contain duplicate elements. Therefore, if a number is added twice, that duplicate should not be allowed to enter the set.

So we will have two sets, say A and B, both containing numbers without repetitions. The numbers can be either positive or negative.

The code below reads one of the sets (A) from the file, sets.txt. Please read the comments to understand the code better. Then, add the code in the following playground to load set B.

Press + to interact
main.cpp
sets.txt
#include <iostream>
#include<fstream>
using namespace std;
int main()
{
	// setting maximum capacity of data to 500
    const int capacity = 500;  
	// allocating array A of capacity 500 and 
			// variable sizeA will store the memory we'll use for set A
	int A[capacity] = { 0 }, sizeA; 
	// allocating B of capacity 500 and 
			// variable sizeB will store the memory we'll use for set B
	int	B[capacity] = { 0 }, sizeB;
	int input, repeatedElement = false;
	// open sets.txt to read the content of the file
	ifstream rdr("sets.txt");
	cout << "Size of set A = ";
	// reading from file the size of the set A
	rdr >> sizeA;             
	// displaying the size of set A
	cout << sizeA<<"\n";      
	cout << "Size of set B = ";
	// reading from file the size of the set B
	rdr >> sizeB;            
	// displaying the size of set B 
	cout << sizeB<<"\n";     
	cout << "\n========\n";
	cout << "Tast 1 - Loading the two sets" << endl;
	//Loading the set A through rdr written in "sets.txt"
	for (int i = 0; i <= sizeA-1; i++)
	{
		rdr >> input;         // reading the ith element of set A
		for (int ei = 0; ei < i; ei++)  //for i-1 previously added element 
		{
			if (input == A[ei]) // checking whether a number is already present in the set
			{
				repeatedElement = true; // remember "input" can not be added
				cout << "\n"<<input<<" was repeated!";
				cout << "\nMust have unique elements in the set!\n";
				i--;        // this iteration should be repeated again
				break;  // no need to check any further in the already filled set
			}
		}
		if (repeatedElement == false)  // if repeatedElement is false it means
			A[i] = input;       // the "input" number should be placed on A[i]
		
		// reset flag so that the next element should be checked again
		repeatedElement =false; 
	}
	cout << "A is loaded...!"<<endl;
	
	/* __________________________________________
	Exercise 1: Write the code to load set B.
	 ––––––––––––––––––––––––––––––––––––––––––*/     
	// Write your code here.
	cout << "\n========\n";
	cout << "Tast 2 - Sorting the two sets" << endl;
	//Sorting A
	for (int t = 1; t <= sizeA - 1; t++)
	{
		for (int ai = 0; ai + 1 < sizeA; ai++)
		{
			if(A[ai]>A[ai+1])
				swap(A[ai], A[ai + 1]);
		}
	}
	/* ––––––––––––––––––––––––––––––––––––––––––
	Exercise 2: Write the code to sort the set B.
    ––––––––––––––––––––––––––––––––––––––––––*/ 
	// Write your code here.
 
	cout << "\n========\n";
	cout << "Task 3 - Displaying the sorted sets" << endl;
	//Displaying set A
	cout << "A = {";
	for (int ai = 0; ai <= sizeA - 1; ai++)
	{
		cout << A[ai];
		if (ai != sizeA - 1)
			cout << ", ";
	}
	cout << "}" << endl;
	/* ––––––––––––––––––––––––––––––––––––––––––
	Exercise 3: Write the code to display set B.
	 ––––––––––––––––––––––––––––––––––––––––––*/     
	// Write your code here.
return 0;
}

  • In lines 20 and 25, we read the sizes of sets A and B.

  • In lines 30–49, we have a nested loop. The outer loop starts from 0 till the last element of the A array i.e., sizeA-1. The inner loop checks whether the input number is already in the loaded part of the set i.e., iterating through the index 0 to i-1. If the input number is already present, the repeatElement variable is set to true, and the break instruction stops the inner loop. Outside the inner loop, if the repeatElement is false, then that means this is a new element hence it should be placed at A[i]. The last instruction of the loop, repeatedElement = false, resets repeatedElement so that for the next iteration the next number in input should be checked again. If we won’t do that, then if once repeatedElement is set to true then the coming values will not be added to the array even if they are unique values.

Good programming practice: Some programmers for maintaining a flag, just like repeatedElement in the above example, declare and initialize it just before the nested inner loop. In this way, at the end of the outer loop, they don’t need to reinitialize it.

Exercise 1: Loading set B

Write the code in the above playground for loading B from the file using rdr.

Reminder: It should restrict the repetition of elements in the set.

Sorting the sets

Task: Given A and B as two sets, sort them.

How to sort a set/array?

Here is the general idea:

Step 1: First, we start comparing two neighboring numbers, A[ai] with A[ai+1], from the start position till the last two numbers.

  • If the first number is greater than the second number, we exchange their positions (by using the swap() function defined in our standard libraries).

    Observation 1: With swap(), the larger of the two values will be pushed to the right; hence, for the next iteration, the next two numbers will be compared, and the larger will move forward, and so on. Hence, in the end, the largest will reach the last position.

    Observation 2: If we repeat the above procedure one more time, the second maximum number will reach the second last position. How many times can we repeat this procedure?

Step 2: We repeat Step 1 sizeA-1 times.

Let’s implement the code for sorting both the sets,

Implementation of sorting set A

Here is the code for sorting set A. Try to understand it, and extend the above playground with this sorting of A.

Advice: After writing this code in the playground, step by step execute your extended program and see what is the state of the array after each iteration of the loop—both during the inner loop execution, after each iteration completion, and after the completion of the entire code.

Press + to interact
for (int t = 1; t <= sizeA - 1; t++)
{
	for (int ai = 0; ai + 1 < sizeA; ai++)
	{
		if(A[ai]>A[ai+1])
			swap(A[ai], A[ai + 1]);
	}
}

Instruction: Write the code in the above playground to extend the program for sorting A.

Exercise 2: Sorting set B

Task: Sort set B, using the similar code as for set A.

Write the code similar to the one we used to sort A as described above. Try to write the code without looking at the hint.

Instruction: Write the sorting code in the above playground to extend the program for sorting B.

Displaying the sets

Task: Display the two sorted sets, A and B.

We want to print A and B on the screen in the standard way of writing sets. For example, if A contains 2, 3, 4, 5, and 10, and B contains 2, 3, 4, 7, 8, and 10, the program should display the following:

Press + to interact
A = {2, 3, 4, 5, 10}
B = {2, 3, 4, 7, 8, 10}
For an empty set, print { }

The code below prints set A as described in the task:

Instruction: Write the following code in the above playground and check the output in the console.

Press + to interact
cout << "A = {";
for (int ai = 0; ai <= sizeA - 1; ai++)
{
	cout << A[ai];
	if (ai != sizeA - 1) // We don't want to print a comma after last element
		cout << ", ";
}
cout << "}" << endl;

  • In Lines 2–8, we have to iterate the loop that starts from 0 to size-1 of set A. After printing every value, we need to display a comma but not for the last iteration. Hence, we avoid printing commas using the if statement. Lines 5–6 capture this printing.

Exercise 3: Printing set B

Add the code in the code editor above to display set B.