Merge sort algorithm with an example

by |

The Merge sort algorithm is known as a divide and conquer algorithm. This means that the input array will be divided into two halves, it then calls itself for the two halves and then merges the two sorted halves together. The algorithm is chosen when an application requires stability such as sorting linked lists and when random access is much more costly than sequential access.

How does The Merge sort algorithm work visual diagram

Sorting the array {38, 27, 43, 3, 9, 82, 10}

Implementation of the algorithm in C++

(Note: This code is from geeksforgeeks.org)

/* C program for Merge Sort */
#include <iostream>

using namespace std;

// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;

/* create temp arrays */
int L[n1], R[n2];

/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];

/* Merge the temp arrays back into arr[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}

/* Copy the remaining elements of L[], if there
are any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}

/* Copy the remaining elements of R[], if there
are any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}

/* l is for left index and r is right index of the
sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l+(r-l)/2;

// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);

merge(arr, l, m, r);
}
}

/* UTILITY FUNCTIONS */
/* Function to print an array */
void printArray(int A[], int size)
{
int i;
for (i=0; i < size; i++)
{
cout << A[i];
cout << "\n";
}
}

/* Driver program to test above functions */
int main()
{
int arr[] = {12, 11, 13, 5, 6, 7};
int arr_size = sizeof(arr)/sizeof(arr[0]);

cout << "Given array is \n";
printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

cout << "\nSorted array is \n";
printArray(arr, arr_size);
return 0;
}

letter frequency counter C++ – 6th C++ Practice Assignment

by |

We are going to create a letter frequency counter c++ in this C++ practice assignment. Therefore, the task is to write a program that the user will enter in a word and then prompt the user to enter in a letter. It will then count the number of times the letter appears in the word that was previously entered and display the result.

Algorithm of the letter frequency counter c++

1. Prompt user for a word
2. The word will be displayed
3. Prompt the user for a letter
4. Count the number of times a letter appears in the word
5. Display the result

This letter counting assignment would be applying the concepts of functions and control structures. Basically, the functions would allow us to write user-defined functions for different parts of the program. The control structure as a for loop would be able to count through and match the total counted value found in the word quickly.

//-------------------------------------------------
// Letter Counter program
// Programmed in Visual Studio 2012
//-------------------------------------------------

#include <iostream>
#include <string>
#include <sstream>
#include <cstdlib>

using namespace std;

string word_input;
char c;

void word_input_func()
{
// Prompt the user for a word
cout << "Enter in a word less than 20 character long\n";
getline(cin, word_input);

cout << word_input;
cout << "\n";
}

int word_count_func()
{
char c;

int count = 0;
cout << "Enter in a letter to find in the word\n";
cin >> c;

cout << "\n";

for(int i = 0; i < word_input.length(); i++)
{
if(word_input[i] == c)
{
count++;
}
}

// Display total counted value
cout << "Total count in the word " << count << "\n";

return count;

}

int main()
{
word_input_func();
word_count_func();
}

The Insertion sort algorithm

by |

We are going to talk about the idea behind the Insertion sort algorithm. Basically, It’s a simple sorting algorithm that sorts the array by shifting the elements one at a time. The essential advantage of the insertion sort is that it’s stable. Therefore the algorithm is more effective than the bubble sort and selection sort algorithms.

Visual diagram of the Insertion sort algorithm 

Implementation of the algorithm in C++

// Insertion sort algorithm implementation in C++

#include <iostream>

using namespace std;

int main()
{
// Sorting Elements of an array in ascending order using insertion sort algorithm
int data[100];
int n,temp;
int i,j;

cout << ("Enter number of terms(should be less than 100): ");
cin >> n;

cout << "Enter elements: ";

for(i=0;i<n;i++)
{
cin >> data[i];
}

for(i=1;i<n;i++)
{
temp = data[i];
j=i-1;
while(temp<data[j] && j>=0)
{
data[j+1] = data[j];
--j;
}
data[j+1]=temp;
}

cout << "In ascending order: \n";
for(i=0; i<n; i++)
cout << data[i] << "\n";
return 0;
}

What is stack and heap?

by |

Stack and Heap, both are stored in a computer’s RAM. The figure below shows the basic concept of stack and heap memory.

What is a stack?

A stack is a data structure used commonly in several programming languages. Similarly, the reason why it is named a stack is that its structure is a collection of elements stacked on top of each other. In other words, the stack is similar to a picture of several books stacked on top of a pile. In real life, the only way we can remove a book from a pile without affecting the others stacked in the pile is to remove the top book. Just like the analogy, the stack only allows the data operations at one end only, which is the top element of the stack.

What is a heap?

The heap is used to dynamically allocate memory to variables at the run time. In other words, the memory needs to be manually released after use during run time. Similarly, the size of the heap depends on the amount of physical and virtual memory available and can grow/shrink at runtime. The heap memory is accessed via pointers (dynamic memory). Above all, heap memory has the disadvantage of being slower than the stack.

Summary of the differences between stack and heap

C++ Multithreading

by |

The concept of c++ multithreading is to be able to run two or more programs at the same time. A thread of execution is the smallest sequence of programming instructions, which can be managed independently by a scheduler. These threads can parallel and it can increase the efficiency of programs. Processors with multiple cores mean that the different threads are executed at the same time on different cores of the processor.

Multithreading diagram containing a process with two threads of execution, running on a single processor

In order to run the multithreading code examples below, you will need the C POSIX library installed as we are using the POSIX library for multithreading support.

Creating threads in c++ multithreading:

//−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
// Joining and detaching threads
//−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
#define NUM_THREADS 5
 
void *wait(void *t)
{
int i;
long tid;
 
tid = (long)t;
 
sleep(1);
cout << "Sleeping in thread\n";
cout << "Thread with id : " << tid;
pthread_exit(NULL);
}
 
int main ()
{
int rc;
int i;
pthread_t threads[NUM_THREADS];
pthread_attr_t attr;
void *status;
 
// Initialize and set thread to be joinable
pthread_attr_init(&attr);
pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);
 
for( i=0; i < NUM_THREADS; i++ )
{
cout << "main() : creating thread, " << i << endl;
rc = pthread_create(&threads[i], NULL, wait, (void *)i );
if (rc)
{
cout << "Error:unable to create thread\n" << rc
exit(−1);
}
}
 
// free attribute and wait for the other threads
pthread_attr_destroy(&attr);
for( i=0; i < NUM_THREADS; i++ )
{
rc = pthread_join(threads[i], &status);
if (rc)
{
cout << "Error:unable to join\n" << rc <<
exit(−1);
}
cout << "Main: completed thread id :" << i ;
cout << " exiting with status\n" << status;
}
 
cout << "Main: program exiting\n";
pthread_exit(NULL);
}

Passing Arguments to threads in c++ multithreading:

//−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
// Passing arguments to threads
//−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
#define NUM_THREADS 5
 
struct thread_data
{
int thread_id;
char *message;
};
 
void *PrintMessage(void *threadarg)
{
struct thread_data *my_data;
 
my_data = (struct thread_data *) threadarg;
 
cout << "Thread ID : " << my_data−>thread_id ;
cout << " Message : " << my_data−>message << endl;
 
pthread_exit(NULL);
}
 
int main ()
{
pthread_t threads[NUM_THREADS];
struct thread_data td[NUM_THREADS];
int rc;
int i;
 
for( i=0; i < NUM_THREADS; i++ )
{
cout <<"main() : creating thread, " << i << endl;
td[i].thread_id = i;
td[i].message = "This is message";
rc = pthread_create(&threads[i], NULL, PrintMessage, (void *)&td[i]);
if (rc)
{
cout << "Error:unable to create thread\n" << rc;
exit(−1);
}
}
pthread_exit(NULL);
}

How to make tic tac toe c++ game – 5th C++ Practice Assignment

by |

This one is on how to write a tic tac toe c++ game that plays against the computer. When the blackjack assignment was shared on StumbleUpon, it generated a large amount of traffic towards the C++ Better Explained site with over 2500 new visitors to the site. Due to popular demand, here is another article on game development with C++. 

Tic Tac Toe Code using Classes

Just like the previous example of implementing blackjack in C++, there are several elements of the Tic Tac toe game that we need to break down. The following code example shows just how that is being done by creating a class of the game and creating a separate function for the needed piece of the game that is required.

//−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
//Tic Tac Toe Class
//−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
#ifndef TIC_TAC_TOE
#define TIC_TAC_TOE
 
#include <time.h>
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using std::cout;
 
class TicTacToe
{
private:
int pos[9]; // board position
int player; // current player
int totalTurns; // how many turns so far?
int numberPlayers; // 1 to 20
bool playerType[20]; // player #, 0 = comp, 1 = human
 
public:
TicTacToe();
void printTurn();
bool playerHuman();
void humanMove();
void computerMove();
void drawBoard();
bool Winner();
bool fullBoard();
void nextTurn();
 
};
 
#endif

Tic_Tac_Toe.cpp file – drawBoard() and other main functions

//−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
// Tic Tac Toe constructor
//−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
TicTacToe::TicTacToe()
{
 srand (time(0));
 
 player = 1; // who starts first?
 totalTurns = 0;
 
 // new player setup
 numberPlayers = 2;
 playerType[1] = 1; // playerType[player] is human (1)
 playerType[2] = 0; // playerType[player] is computer (0)
 
 for (int i = 0; i < 9; i++)
 {
 pos[i] = 0;
 }
 
}
 
 
//−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
// Draw the Tic Tac Toe Board and seperate the board
// with the help of |
//−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
void TicTacToe::drawBoard()
{
std::cout << std::endl<< pos[0] << " | " << pos[1] << " | " << pos[2]<< "\n?\n"<< pos[3] << " | " << pos[4] << " | " << pos[5]<< "\n?\n"<< pos[6] << " | " << pos[7] << " | " << pos[8]<< std::endl;}

void TicTacToe::printTurn()
{
 std::cout << "\nPlayer " << player << "'s turn.\n";
}
 
void TicTacToe::nextTurn()
{
 totalTurns++;
 
 if (++player > numberPlayers)
 player = 1;
}
 
bool TicTacToe::playerHuman()
{
 return playerType[player];
}
 
void TicTacToe::humanMove()
{
 
 std::cout << "\nEnter your move: ";
 int move;
 
 do
 {
 std::cin >> move;
 move−−; // so user can enter 1−9 instead of 0−8
 }
 while (move < 0 || move > 8 || pos[move] != 0);
 
 pos[move] = player;
}
 
void TicTacToe::computerMove()
{
 int move;
 
 do
 {
 // Pick a random number from 1 − 9
 move = rand() % 9; // just pick a random number
 }
 while (move < 0 || move > 8 || pos[move] != 0);
 
 pos[move] = player;
 
}
 
bool TicTacToe::Winner()
{
 int board[8][3] = {{0,1,2},
 
 // winning possibilities
 {3,4,5},
 {6,7,8},
 {0,3,6},
 {1,4,7},
 {2,5,8},
 {0,4,8},
 {2,4,6}}; 
 
 // Go through the list of possibilities
 for (int i = 0; i < 8; i++)
 {
 if ((pos[board[i][0]] == pos[board[i][1]]) && (pos[board[i][1]] == pos[board[i][2]]) && pos[board[i][0]] != 0)
 {
 cout << "\nPlayer " << pos[board[i][0]] << " wins!\n\n";
 
 return 1; // return winner true
 }
 }
 
 return 0; // winner false
}
 
bool TicTacToe::fullBoard()
{
 if (totalTurns == 9)
 {
 cout << "\nTie game!\n\n";
 return 1;
 }
 else
 return 0;
}

Main.cpp file

#include "Tic_Tac_Toe.h"
 
//−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
// Main function of the game
//−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
int main()
{
TicTacToe Game;
Game.drawBoard();
 
do
{
Game.printTurn();
 
if (Game.playerHuman()) // human turn?
Game.humanMove();
else
Game.computerMove();
 
Game.drawBoard();
Game.nextTurn();
 
}
 
// Keep running the game until there is a winner and the game board is full
while (!Game.Winner() && !Game.fullBoard());
 
return 0;
}

More on cppbetterexplained:

• Lottery ticket generator in C++
• Salary program in C++
• Virtual vs Pure Virtual Function