The K-Nearest Neighbors (KNN) algorithm is one of the simplest and most intuitive supervised machine learning algorithms. It classifies a new data point based on the majority class among its K closest neighbors in the training dataset. There is no explicit training phase — the algorithm memorizes the entire dataset and makes decisions at prediction time, which is why it is also called a lazy learner.
In this post, we will walk through a C++ implementation of the KNN algorithm that classifies a person’s height as short, medium, or tall using a small training set of 12 records. We cover the algorithm step by step and explain the output in detail.
What is the KNN Algorithm?
KNN works on a very simple principle: similar things exist in close proximity. Given an unlabeled data point, the algorithm:
- Calculates the distance between the new point and every point in the training dataset.
- Sorts all training points by distance (ascending).
- Picks the K nearest points (the threshold).
- Assigns the class that appears most frequently among those K neighbors.
This program uses a single feature — height — and the distance metric is the simple absolute difference (Manhattan distance in 1D). Gender is stored in the dataset but is not used as a feature for classification in this implementation.
C++ Program: KNN Algorithm
#include <iostream>
#include <cstring> // for strcmp()
using namespace std;
int main() {
int sampleIdx, bubblePass, compareIdx;
// Total number of training samples
int totalSamples = 12;
// Gender of each training sample
char gender[12] = {'F','M','F','F','F','M','F','M','M','F','M','F'};
// Height (in meters) of each training sample
float height[12] = {1.6f, 2.0f, 1.9f, 1.88f, 1.7f, 1.85f,
1.6f, 1.7f, 2.2f, 1.8f, 1.95f, 1.9f};
// Class label (short / medium / tall) for each training sample
char label[12][10] = {"short", "tall", "medium", "medium",
"short", "medium", "short", "short",
"tall", "medium", "medium", "medium"};
// ----------------------------------------------------------------
// Print the initial training set
// ----------------------------------------------------------------
cout << "\nInitial Training Set:";
cout << "\nGender\tHeight\tOutput";
for (sampleIdx = 0; sampleIdx < 12; sampleIdx++) {
cout << "\n" << gender[sampleIdx] << "\t" << height[sampleIdx] << "\t" << label[sampleIdx];
}
// ----------------------------------------------------------------
// Read the new (unseen) tuple from user
// ----------------------------------------------------------------
float newHeight; // new height to classify
char newGender; // new gender (stored but not used for classification)
cout << "\n\nEnter tuple to classify (Height Gender, e.g. 1.7 M): ";
cin >> newHeight >> newGender;
// ----------------------------------------------------------------
// Read K (number of nearest neighbours to consider)
// ----------------------------------------------------------------
int kNeighbours;
cout << "\nEnter K (threshold): ";
cin >> kNeighbours;
// dist[i][0] = original index of sample i
// dist[i][1] = distance from the new tuple to sample i
float dist[12][2];
float tempDiff;
// ----------------------------------------------------------------
// Step 1: Calculate distance from new tuple to every training sample
// Distance = |height_i - newHeight| (absolute difference)
// ----------------------------------------------------------------
for (sampleIdx = 0; sampleIdx < 12; sampleIdx++) {
dist[sampleIdx][0] = (float)sampleIdx; // store original index
tempDiff = height[sampleIdx] - newHeight; // signed difference
dist[sampleIdx][1] = (tempDiff < 0) ? -tempDiff : tempDiff; // absolute value
}
// ----------------------------------------------------------------
// Step 2: Sort distances using Bubble Sort (ascending order)
// ----------------------------------------------------------------
int neighbourIdx;
float tempDist;
for (bubblePass = 0; bubblePass < 11; bubblePass++) {
for (compareIdx = 0; compareIdx < 11; compareIdx++) {
if (dist[compareIdx][1] > dist[compareIdx+1][1]) {
// Swap distances
tempDist = dist[compareIdx][1];
dist[compareIdx][1] = dist[compareIdx+1][1];
dist[compareIdx+1][1] = tempDist;
// Swap corresponding indices so they stay in sync
neighbourIdx = (int)dist[compareIdx][0];
dist[compareIdx][0] = dist[compareIdx+1][0];
dist[compareIdx+1][0] = (float)neighbourIdx;
}
}
}
// ----------------------------------------------------------------
// Step 3: Display the K nearest neighbours
// ----------------------------------------------------------------
int countShort = 0; // votes for "short"
int countMedium = 0; // votes for "medium"
int countTall = 0; // votes for "tall"
cout << "\n\nTop " << kNeighbours << " Nearest Neighbours:";
cout << "\nGender\tHeight\tOutput";
for (sampleIdx = 0; sampleIdx < kNeighbours; sampleIdx++) {
neighbourIdx = (int)dist[sampleIdx][0]; // original index of this neighbour
cout << "\n" << gender[neighbourIdx] << "\t" << height[neighbourIdx] << "\t" << label[neighbourIdx];
// Count votes for each class
if (strcmp(label[neighbourIdx], "short") == 0) countShort++;
if (strcmp(label[neighbourIdx], "medium") == 0) countMedium++;
if (strcmp(label[neighbourIdx], "tall") == 0) countTall++;
}
// ----------------------------------------------------------------
// Step 4: Print vote counts
// ----------------------------------------------------------------
cout << "\n\nVote Summary:";
cout << "\n Short : " << countShort;
cout << "\n Medium : " << countMedium;
cout << "\n Tall : " << countTall;
// ----------------------------------------------------------------
// Step 5: Classify based on majority vote
// ----------------------------------------------------------------
if (countShort > countMedium && countShort > countTall) {
cout << "\n\nResult: New tuple is classified as --> SHORT";
} else if (countMedium > countShort && countMedium > countTall) {
cout << "\n\nResult: New tuple is classified as --> MEDIUM";
} else if (countTall > countMedium && countTall > countShort) {
cout << "\n\nResult: New tuple is classified as --> TALL";
} else {
cout << "\n\nResult: TIE — increase K or add more training data.";
}
return 0;
}
How the Code Works — Step by Step
Step 1 — Define the Training Dataset
The training set has 12 records, each with three attributes: gender (char), height in metres (float), and a class label — either short, medium, or tall (char array). The label is the ground truth we want KNN to reproduce for unseen inputs.
Step 2 — Accept Input and K
The user provides the height and gender of the new tuple, plus the value of K. K is the number of nearest neighbours that will vote on the classification. A smaller K is more sensitive to noise; a larger K is more robust but can blur class boundaries.
Step 3 — Calculate Distance to Each Training Sample
The program uses the absolute difference in height as the distance metric. For a training sample with height height[i] and a new tuple with height newHeight, the distance is:
distance = |height[i] - newHeight|
Both the distance and the original array index are stored together in a 2D array dist[12][2], so the original index is not lost when we sort by distance.
Step 4 — Sort by Distance (Bubble Sort)
The 2D array is sorted in ascending order by distance using Bubble Sort. The outer loop (bubblePass) controls the number of passes and the inner loop (compareIdx) performs adjacent comparisons. Crucially, when two distance entries are swapped using tempDist, their paired index entries are also swapped so the association between a distance and its original training record is preserved.
Step 5 — Select K Nearest Neighbours and Vote
The first K entries in the sorted array are the nearest neighbours. For each of these, the class label (short, medium, or tall) is read using the stored neighbourIdx (the original training record index). A vote counter for each class is incremented accordingly using strcmp().
Step 6 — Majority Vote and Classification
Whichever class received the most votes from the K nearest neighbours wins. The new tuple is assigned that class as its predicted label.
Program Output
Initial Training Set:
Gender Height Output
F 1.6 short
M 2 tall
F 1.9 medium
F 1.88 medium
F 1.7 short
M 1.85 medium
F 1.6 short
M 1.7 short
M 2.2 tall
F 1.8 medium
M 1.95 medium
F 1.9 medium
Enter tuple to classify (Height Gender, e.g. 1.7 M): 1.7 M
Enter K (threshold): 5
Top 5 Nearest Neighbours:
Gender Height Output
F 1.7 short
M 1.7 short
F 1.8 medium
F 1.6 short
F 1.6 short
Vote Summary:
Short : 4
Medium : 1
Tall : 0
Result: New tuple is classified as --> SHORT
Output Explanation
The new tuple has a height of 1.7 m. After computing distances from all 12 training records and sorting, the 5 nearest neighbours are:
- Two records at height 1.7 m (distance = 0.0) — both labelled short
- One record at height 1.8 m (distance = 0.1) — labelled medium
- Two records at height 1.6 m (distance = 0.1) — both labelled short
The vote tally is: short = 4, medium = 1, tall = 0. Since short has the highest count, the algorithm classifies the input as SHORT. This is the correct and expected result — a person of 1.7 m in this dataset is closest to the cluster of individuals labelled as short.
Key Concepts Recap
| Concept | Details in This Program |
|---|---|
| Algorithm type | Supervised, instance-based (lazy learner) |
| Feature used | Height (single numeric feature) |
| Distance metric | Absolute difference (1D Manhattan distance) |
| Sorting method | Bubble Sort |
| Decision rule | Majority vote among K neighbours |
| Classes | short, medium, tall |
Conclusion
The KNN algorithm is elegantly simple yet surprisingly effective for small datasets. This C++ implementation demonstrates all the core steps: storing a labelled training set, computing distances, sorting by distance, picking the K nearest neighbours, and classifying by majority vote. While this example uses only one feature and a simple distance measure, the same pattern scales to multiple features using Euclidean or other distance metrics.
If you found this helpful, also check out the related DWM programs:
hi, may i know does it include with euclidean formula too?
this program is showing the error
” fatal error: iostream.h: No such file or directory
compilation terminated.
“what should i do?
remove (.h) from (#include (iostream.h)) .let it just be (#include (iostream).
#include
if(strcmp(op[l],”short”)==0)
error on strcmp();
function prototype missing
You did not consider gender as feature while classifying right?