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.
               }
          }
     }
  
}

Edited 6 Years Ago by vanalex: n/a

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.

Edited 6 Years Ago by Fbody: n/a

This question has already been answered. Start a new discussion instead.