Exchange or bubble sorting

Bubble sorting method is based on two consecutive elements successive comparisons and make an exchange between the elements until that are ordered.

Suppose the vector shown in the following table, to perform the management have follow these paso:

• Compares the first two elements, if the second is higher than the first, they are not as they are, but if the first is the largest, are exchanged elements.
• Is then compared to the second element with the third by applying the same criteria as the step previous.
• In this way is repeated the operation in comparison with all the elements that form the vector. When it reaches the last element has been the element which has the highest value and this has been located at the end of the vector.
• To find the second element is repeated the operation management of all the elements of the array except the last.
• Reiterating the process described, the vector be ordered when only comparing the first two elements.

First management.

Example of management by bubble to find the first element.

	vector	comparison 1st	2nd comparison	3rd comparison	4th comparison	5th comparison
V [1]	3	3	3	3	3	3
V [2]	34	34	1	1	1	1
V [3]	1	1	34	34	34	34
v [4]	53	53	53	53	15	15
V [5]	15	15	15	15	53	6
V [6]	6	6	6	6	6	53

management process expressed in pseudocóI say structured e:

 from j. ← 1 to n-1 do If element [j] > element [j+1] then intercambiar(elemento[j],_elemento[j+1]) fin_si fin_desde

for the process of exchanging elements has to use an auxiliary variable of the following forma:

 aux ← V [j] V [j] ← V [j+1] V [j+1] ← aux

Second management.

	vector	1st Management	1st comparison	2nd comparison	3rd comparison	4th comparison
V [1]	3	3	1	1	1	1
V [2]	34	1	3	3	3	3
V [3]	1	34	34	34	15	15
V [4]	53	15	15	15	34	6
V [5]	15	6	6	6	6	34
V [6]	6	53	53	53	53	53

After the second ordination the two largest vector elements have been found and they have placed themselves at the end of the same.

Algorithm of bubble.

Generalizing the management process is obtains the following pseudocode structured for the algorithm of bubble

i - Variable ordinations < br / > j - Variable comparisons < br / > n - number of elements in the vector (c represents the largest index)

 algorithm bubble home / / ordinations since i ← 1 to n-1 do / / comparisons from j ← 1 up NI do If element [j] > element [j+1] then / / Exchange elements aux ← V [j] V [j] ← V [j+1] V [j+1] ← aux fin_si fin_desde fin_desde end

example in C:

 v [] int = {3, 34, 1, 53, 15, 6}; int j, i, aux;

/ / Management for(i=0;_i<5;_i++) {/ / comparisons for(j=0;_j<5-i;_j++) {/ / Exchange element if(v[j]_>_v[j+1]) {aux = v [j];}}}
		v [j] = v [j+1];
		v [j+1] = aux;
		{}}

reiterating in sorting get sorted vector as shown in the following tabla:

	Vector	1st Management	Management 2nd	3rd management	Management 4th	5th management
V [1]	3	3	1	1	1 < br / >	1
V [2]	34	1	3	3	3	3
V [3]	1	34	15	6	6	6
V [4]	53	15	6	15	15	15
V [5]	15	6	34	34	34	34
V [6]	6	53	53	53	53	53

Method of management of bubble improved.

If you look at the table of sorts we note that the vector has been ordered in the third management, being unnecessary making the fourth and fifth management, however analyzed bubble algorithm performs all comparisons of sorting up to (n-1). You can detect that the vector is orderly and interrupt the ordinations, thus improving the performance of the algorithm. When is a management If all comparisons there has been an exchange of elements it is because the vector is ordered. An indicator, flag or Boolean variable can be used to detect the end of the management

The following algorithm shows one of the versions optimized method of sorting bubble.

i - Variable ordinations < br / > j - Variable comparisons < br / > n - number of elements in the vector (c represents the largest index) < br / > ord - indicator Variable of sorted vector

 algorithm Burbuja2 home / / ordinations i ← 1 / / start ordinations ord ← 0 / / start indicator of vector ordered while ord = 0 do ord ← 1 / / comparisons from j ← 1 to n-I make If element [j] > element [j+1] then / / Exchange elements aux ← V [j] V [j] ← V [j+1] V [j+1] ← aux ord ← 0 fin_si fin_desde i ← k fin_mientras end

example in C:

 int v [] = {3, 34, 1, 53, 15, 6}; int j, aux; int i = 0; bool ord = false;

/ / Ordinations while(!ord) {/ / comparisons ord = true;}
	for(j=0;j<5-i;j++) {if(v[j]>v[j+1]) {/ / Exchange elements aux = v [j];}}
			v [j] = v [j+1];
			v [j+1] = aux;
			Ord = false;	{{/ / Indicator of sorted vector}} i ++;
}

Example in C++ Builder:

 / /-# include < vcl.h > # include < iostream.h > # include < conio.h > # pragma hdrstop / /-# pragma argsused int main(int_argc,_char*_argv[]) {/ / variable int v [] = {3, 34, 1, 53, 15, 6}; int j, aux; int i = 0; bool ord = false;}

/ / Display the vector for(int_n=0;_n<6;_n++) {cout < < v [n] < < "";}

/ / Ordinations while(!ord) {/ / comparisons ord = true;}
	for(j=0;j<5-i;j++) {if(v[j]>v[j+1]) {/ / Exchange elements aux = v [j];}}
			v [j] = v [j+1];
			v [j+1] = aux;
			Ord = false;	{{/ / Indicator of sorted vector}} i ++;
} / / Display the array ordered cout < < endl;
for(int_n=0;_n<6;_n++) {cout < < v [n] < < "";}

getch();
return 0;
} / /-

Many authors criticize the ordering method for bubble due to its low yield and its desmerecida significance, although I share these views, is a very simple system that adapts perfectly to his studio in centres of formation.

Other methods of management as selection or insertion provides better results, management systems Quick (quicksort), Shell and Merge are the most effective, providing some spectacular returns when it comes to ordering vectors of large dimensions.