Jackson Singleton Jackson Singleton - 11 months ago 40
C++ Question

Comprehending the Bubble Sort

Stack Overflow
I was looking into algorithms so I could break them down piece by piece to understand what is going on. Anyways, I was looking at this tutorial to look into the bubble sort. I was confused by a very small part of the demonstration algorithm in C++, the integer j.

void bubbleSort(int arr[], int n) {
bool swapped = true;
int j = 0;
int tmp;
while (swapped) {
swapped = false;
for (int i = 0; i < n - j; i++) {
if (arr[i] > arr[i + 1]) {
tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
swapped = true;

Is it a required part of the algorithm? I don't really understand what it's doing, as when I swapped j inside the for loop for 1, I got the same results.

for (int i = 0; i < n - 1; i++)

Why is the int j in the algorithm?

Answer Source

In the first outer iteration, we would bubble down the largest integer into a[n-1]. The second iteration only needs to traverse array the remaining unsorted part of the array i.e. from index 0 to n-2 and bubble down the second largest integer into a[n-2]. The third iteration only needs to traverse array from index 0 to n-3, and so on.

Variable j achieves this by limiting the range of array to traverse in subsequent outer iterations. We can very well traverse the entire array in every iteration (as you would do after changing n-j with n-1) and obtain the same result. But that would be inefficient, since we would unnecessarily be comparing elements in sorted part of array in every iteration. Let me know if you have any questions.