Bubble Sort – Source Code

Below is a C++ implementation of Bubble Sort. We do not follow Object Oriented Concepts in the below program but do use a few C++ libraries.

This program has been tested on a x86_64 (64 bit) Linux machine for validity.


Key points to remember:

  • The source code below expects an text file named ‘input.txt’ in the same folder where the binary generated by compiling the below code is placed.
  • The input file should contain space separated integer values that would be read by the program and considered as input.
  • The maximum number of input values that can be processed at once is restricted to 100.


Source Code:

/*
* bubblesort.cpp
*
*  Created on: 26-Jul-2011
*      Author: Santhosh
*
*  Description:
*      This program sorts integer data in an input file using the bubble sort
*  algorithm.
*      The input data is stored in a file named 'input.txt'. Each integer is
*  separated by space.
*  Example:
*      14 15 4 9 7 18 3 5 16 4 20 17 9 14 5
*/

#include <iostream>
#include     // Required for the 'ifstream' object
#include <cstdlib>    // Required for the 'exit()' method.

/* Function Prototypes */
int readInputFromFile(int input[]);
void displayArray(int input[], int size);
void bubbleSort(int input[], int n);

// Const variable pointing to the name of the input file.
const char* inputFileName = "input.txt";

// Const variable - max size of the input array.
const short arraySize = 100;

/* == FUNCTION =================================================================
*  NAME       : main
*
*  PARAMETERS : none
*
*  DESCRIPTION:
*      The main method that reads the input from a file and then invokes
*  the bubble sort algorithm to sort the data. The input data is displayed on
*  terminal before and after sorting the data.
* =============================================================================
*/

int main() {
int input[arraySize] = { 0 }; // Set the contents of input array to 0.
int count = 0; // Variable to save the actual length of array.

// Read the input from the input file.
count = readInputFromFile(input);

// Display unsorted or raw input data.
std::cout << "Raw input (" << count << " elements): " << std::endl;
displayArray(input, count);

// Sort the input array using in-place bubble sort algorithm.
bubbleSort(input, count);

// Display the sorted output.
std::cout << "Sorted output (" << count << " elements): " << std::endl;
displayArray(input, count);

return 0;
}

/* == FUNCTION =================================================================
*  NAME       : bubbleSort
*
*  PARAMETERS :
*      input  : an integer array to be sorted.
*          n  : size of the array.
*
*  DESCRIPTION:
*      This method sorts the contents of the array pointed by the 'input'
*  variable in ascending order utilzing the bubble sort algorithm.
* =============================================================================
*/

void bubbleSort(int input[], int n) {
bool swapped = true;
for (int i = 0; i < n - 1 && swapped == true; i++) {
swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (input[j] > input[j + 1]) {
// Swap the elements.
int temp = input[j];
input[j] = input[j + 1];
input[j + 1] = temp;
swapped = true;
}
}
}
}

/* == FUNCTION =================================================================
*  NAME       : readInputFromFile
*
*  PARAMETERS :
*      input  : an integer array which should be filled with elements that are
*               read from the input file.
*
*  RETURN       :
*      count  : an integer whose value signifies the actual lenght of the
*               array.
*
*  DESCRIPTION:
*      This method reads the input file for space separated integer values and
*  updates the 'input' array (passed as a parameter).
* =============================================================================
*/

int readInputFromFile(int input[]) {
std::ifstream in(inputFileName);
if (in.is_open() == false) {
std::cerr << "Failed to open the input file!" << std::endl;
exit(1);
} else {
int count = 0;
while (!in.eof()) {
in >> input[count];
if (++count >= 100)
break;
}
in.close();

if (count >= 100) {
std::cerr << "The input exceeds size limitations." << std::endl;
std::cerr << "At max " << arraySize << " elements are allowed! ";
std::cerr << "But found " << count + 1 << " elements!" << std::endl;
std::cerr << std::endl;
exit(2);
}
return count;;
}
}

/* == FUNCTION =================================================================
*  NAME       : displayArray
*
*  PARAMETERS :
*      input  : an integer array whose elements are to be displayed.
*      size   : size of the array.
*
*  DESCRIPTION:
*      This method displays the contents of the array received as parameter.
* =============================================================================
*/

void displayArray(int input[], int size) {
for (int i = 0; i < size; i++)
std::cout << "\t" << *(input + i);
std::cout << std::endl;
}

 


Sample Output:

Use Case: With valid data

Raw input (15 elements):
14    15    4    9    7    18    3    5    16    4    20    17    9    14    5
Sorted output (15 elements):
3    4    4    5    5    7    9    9    14    14    15    16    17    18    20

Use Case: With input data that exceeds 100 elements

The input exceeds size limitations.
At max 100 elements are allowed! But found 101 elements!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s