C++ Insertion Sort

A simple implementation of insertion sort algorithm in C++

– Fill array with random numbers

template <typename Comparable>
void fillRandom(vector<Comparable> &iArray, Comparable range)
{
	srand((unsigned)time(0));
	for(Comparable i = 0; i < iArray.size(); i++)
	{
		iArray[i] = rand() % range;
	}
}

– Insertion Sort forwards

template <typename Comparable>
void insertionSort(vector<Comparable> &a)
{
	for(int unsorted = 1; unsorted < a.size(); unsorted++)
	{
		int loc;
		Comparable nextItem = a[unsorted];
		for(loc = unsorted; loc > 0 && nextItem < a[loc - 1]; loc--)
		{
			a[loc] = a[loc - 1];
		}

		a[loc] = nextItem;
	}
}

– Insertion Sort backwards

template <typename Comparable>
void insertionSortInverted(vector<Comparable> &a)
{
	for(int unsorted = a.size() - 2; unsorted >= 0; unsorted--)
	{
		int loc;
		Comparable nextItem = a[unsorted];
		for(loc = unsorted; loc < a.size() - 1 && nextItem > a[loc + 1]; loc++)
		{
			a[loc] = a[loc + 1];
		}

		a[loc] = nextItem;
	}
}
Advertisements

C++ Bubble Sort

A simple implementation of Bubble Sort algorithm:

Also on Blogger

– Random Generator:

template <typename Comparable>
void fillRandom(vector<Comparable> &iArray)
{
	srand((unsigned)time(0));
	for(vector<Comparable>::size_type i = 0; i < iArray.size(); i++)
	{
		iArray[i] = rand();
	}
}

– Bubble Sort Algorithm:

template <typename Comparable>
void bubbleSort(vector<Comparable> &a)
{
	bool sorted = false;
	for(int pass = 1; pass < a.size() && !sorted; pass++)
	{
		sorted = true; // Optimize and stop if array is already sorted
		for(int index = 0; index < a.size() - pass; index++)
		{
			if(a[index] > a[index + 1])
			{
				swap(a[index], a[index + 1]);
				sorted = false;
			}
		}
	}
}

– Bubble Sort Algorithm, inverted version:

template <typename Comparable>
void bubbleSortInverted(vector<Comparable> &a)
{
	bool sorted = false;
	for(int pass = a.size() - 1; pass > 0 && !sorted; pass--)
	{
		sorted = true; // Optimize and stop if array is already sorted
		for(int index = a.size() - 1; index > 0; index--)
		{
			if(a[index] < a[index - 1])
			{
				swap(a[index], a[index - 1]);
				sorted = false;
			}
		}
	}
}

C++ Selection Sort

A brief implementation about Selection Sort:

– First we need a random generator:

void fillRandom(vector<int> &iArray)
{
	srand((unsigned)time(0));
	for(int i = 0; i < iArray.size(); i++)
	{
		iArray[i] = rand();
	}
}

– Selection Sort algorithm starting from biggest to smallest:

template <typename Comparable>
void selectionSort(vector<Comparable> &a, int last)
{
	if(last <= 0)
	{
		return;
	}

	vector<Comparable>::size_type largest = a[0];
	int index = 0;
	for(int i = 1; i <= last; i++)
	{
		if(a[i] > largest)
		{
			largest = a[i];
			index = i;
		}
	}

	vector<Comparable>::size_type buffer = a[index];
	a[index] = a[last];
	a[last] = buffer;
	selectionSort(a, last - 1);
}

– Selection Sort algorithm starting from smallest to biggest:

template <typename Comparable>
void selectionSortInvert(vector<Comparable> &a, int first)
{
	if(first >= a.size())
	{
		return;
	}

	Comparable smallest = a[first];
	int index = first;
	for(int i = first + 1; i < a.size(); i++)
	{
		if(a[i] < smallest)
		{
			smallest = a[i];
			index = i;
		}
	}

	vector<Comparable>::size_type buffer = a[index];
	a[index] = a[first];
	a[first] = buffer;
	selectionSortInvert(a, first + 1);
}

– Finally, libraries used:

#include <iostream>
#include <vector>
#include <ctime>

Software Development Process – Requirements Specifications, Design Methods

Terms and Concepts

Analysis – Activity of Software Requirements Engineering where the needs for a new system are defined by stakeholders and by any role with vested interests in the system/project. The analysis seeks to answer how does the system solves a problem (added value) taking in consideration the constraints on a solution as well as its feasibility

Anti-Patterns – A pattern that is commonly used but ineffective and/or counter productive in practice, it has the following characteristics:

  • Some repeated pattern of action, process or structure that initially appears to be beneficial but ultimately produces more bad consequences than beneficial results

Architectural Design – Part of the software design and implementation where the following items are identified:

  • Overall structure of the system
  • Principal components (also called subsystems or modules)
  • Their relationships
  • How are they distributed

Architectural Styles – Also known as Design Styles or Architectural Patterns, they possesses the following characteristics:

  • Define “direction / layout”
    • Threads and execution (control flow)
    • Communication
    • Modularity
  • Allows allocation across infrastructure
  • Defines platform requirements
  • Styles:
    • Flow
    • Layered
    • Data-Centered
    • Virtual Machines
  • It is object oriented
  • Could be a mixture of patterns

Blue Ocean Strategy – Is a strategy known for having competitive advantage by delivering a solution with added value. This is done by the following ways:

  • Reduce existing factors from industry standards
  • Raise factors above industry standards
  • Eliminate factors that industry has taken for granted
  • Create something that hasn’t been created before

Cohesion – Is the relationship between the modules / functions of a system. High / Strong cohesion is best since it leads to good rules. Accessed based on design / understanding of code. Types of cohesion:

  • Functional cohesion – does ONE thing only
  • Informational cohesion – Multiple functions operating on the same data
  • Sequential cohesion – Functions that can be put in sequence where each have no meaning alone. Only together have meaning
  • Temporal cohesion – They happen at the same time together
  • Logical cohesion – One of the parameters is a flag for identifying what to actually do. A common “signature” for functions
  • Coincidental cohesion – No logical relationship or functionality as to why code is together in a module, also called “illogical programming” or “programming on acid”

Constraints – Limitations for a given solution. Key constrains are: Resources, Time, Infrastructure, People, Technology

Conversation – Is a style of use case involving actors and the system and can be defined as an ordered iteration, a request / response or event driven metaphors

Coupling – (“Loose” coupling is best) Is related to the communication between modules. It defines the “opaqueness” of the “black box” for a module. It involves significant implications for maintainability and code evolution

Requirement – High-level, general, business-focused descriptions of what the system should do

Specification – Low-level, detailed, developer-focused descriptions of what the system should do

Hello world!

Welcome to WordPress.com. This is your first post. Edit or delete it and start blogging!