#### Quadratic sorts

**Sorting** - **is rearranging the elements of an array (list) in a given order.**

Bubble method (bubble sort), or sort by simple exchanges).

An immortal classic of the genre. The principle of action is simple: we go around the array from beginning to end, simultaneously swapping unsorted neighboring elements. As a result of the first pass to the last place, "pops up" maximum element. Now we again bypass the unsorted part of the array (from the first element to the penultimate one) and change the unsorted neighbors along the way. The second largest element will be in the penultimate place. Continuing in the same spirit, we will bypass the ever-decreasing unsorted part of the array, pushing the found maximums to the end.

Source

Algorithmic implementation of this algorithm

LOOP FOR J=1 TO N-1 STEP 1
F=0
LOOP FOR I=1 TO N-J-1 STEP 1
IF A[I] > A[I+1] THEN
EXCHANGE A[I],A[I+1]
F=1
NEXT I
IF F=0 THEN EXIT THE LOOP // if there were no exchanges during the pass,
// that means all elements
// arranged in order
NEXT J

Complexity of this algorithm:

\(\displaystyle O(n^{2})\).

Additional useful information:

Wikipedia article.