0

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?
			}
		}
	}
}
3
Contributors
2
Replies
7
Views
6 Years
Discussion Span
Last Post by Fbody
Featured Replies
  • [QUOTE=aaronmk2;1377702]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 [CODE] 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]) … Read More

1

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 by vanalex: n/a

0

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 by Fbody: n/a

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.