Can someone please explain the exact purpose of the second for loop in the following bubble sort? I understand the first loop is looking at the 'i'th integer of the array, but what exactly is the second for loop looking at?
Please excuse my ignorance on the topic. I've been coding for less than a week now and am somewhat confused on the subject.
void sort(int array[], int size) {
for(int i = 0, x = size - 1; i < x; i++) {
for(int j = 0; j < x - 1; j++) {
if(array[j] > array[j + 1]) {
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
}
}
}
}
I guess your first loop is wrong too, considering you want to implement Bubble Sort, since the first loop tells the number of passes required to sort a list. In case of Bubble Sort it's equal to Total Number of elements - 1 number of passes are required to sort a list of n elements (n - 1) passes are required, hence the value of i in my humble opinion must start from 1, if I am not mistaken. Moreover, the snippet provided by you doesn't resembles a C Language coding style, in terms of you declaring variables as an when required.
The second loop is basically there to decrease the comparison (Number of elements - pass - 1), after each iteration, since with each pass, we place the largest element to the right side (of the logically unsorted list). Hence since that element is in it's rightful position, so we don't have to compare that with other elements.
4 3 2 1 Original List
3 2 1 4 Pass 1
-
Now since this above 4 is in it's rightful place
we don't need to compare it with other elements.
Hence we will start from the zeroth element and
compare two adjacent values, till 1 (for Pass 2)
Here comparison will take place between 3 and 2,
and since 3 is greater than 2, hence swapping
between 3 and 2, takes place. Now 3 is comapred
with 1, again since greater value is on left
side, so swapping will occur. Now 3 is not compared
with 4, since both these values are in their
rightful place.
2 1 3 4 Pass 2
-
Now since this above 3 is in it's rightful place
we don't need to compare it with other elements.
Hence we will start from the zeroth element and
compare two adjacent values, till 1 (for Pass 3)
Here only one comparison will occur, between
2 and 1. After swapping 2 will come to it's rightful
position. So no further comparison is needed.
1 2 3 4 Pass 3
Here the list is sorted, so no more comparisons, after Pass 3.
void bubbleSort(int *ptr, int size)
{
int pass = 1, i = 0, temp = 0;
for (pass = 1; pass < size - 1; pass++)
{
for (i = 0; i <= size - pass - 1; i++)
{
if (*(ptr + i) > *(ptr + i + 1))
{
temp = *(ptr + i);
*(ptr + i) = *(ptr + i + 1);
*(ptr + i + 1) = temp;
}
}
printf("Pass : %d\n", pass);
for (temp = 0; temp < size; temp++)
printf("%d\t", *(ptr + temp));
puts("");
}
}