My profesor added this line of code to a bubble sort saying that it made it more efficient by tracking the last swap. I don't understand how this would work
void bubble_sort(int a[], int n){
while (0<n-1) {
int last =0;
for (int i=0; i<n-1; i++) {
if (a[i]>a[i+1]) {
swap(a[i],a[i+1])
last=i;//this line tracks the last swap, but how would it stop the program once it is sorted?
}
}
}
}My profesor added this line of code to a bubble sort saying that it made it more efficient by tracking the last swap. I don't understand how this would work
void bubble_sort(int a[], int n){ while (0<n-1) { int last =0; for (int i=0; i<n-1; i++) { if (a[i]>a[i+1]) { swap(a[i],a[i+1]) last=i;//this line tracks the last swap, but how would it stop the program once it is sorted? } } } }
Hello, i can see nothing in your code that can be affected by variable last. Variable last just counts how many times the swap occurs between elements a, a[i+1]. Maybe you mean something like this:
void BubbleSort(apvector <int> &num)
{
int i, j, flag = 1; // set flag to 1 to start first pass
int numLength = num.length( );
for(i = 1; (i <= numLength) && flag; i++) //if flag becomes 0 then sorting stops
{
flag = 0;
for (j=0; j < (numLength -1); j++)
{
if (num[j+1] > num[j]) // ascending order simply changes to <
{
swap(num[j], num[j + 1]; // swap elements
flag = 1; // indicates that a swap occurred.
}
}
}
}
Bubble Sort is dependent on performing multiple swaps to move values to their sorted locations. The idea is that if no swaps are performed, then logically everything must be in the proper location. If everything is in its proper location, the sort is finished whether all passes have been completed or not.
I believe that is your instructor's intended purpose for "last", but it's not a proper implementation for that intent.
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.