Quadratic sorts


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.

 

Training problem

bubble sort

Insert sort

Insertion sort (Insertion sort) —  ;sorting algorithm in which the elements of the input sequence are looked up one at a time, and each new incoming element is placed in the appropriate place among the previously sorted elements.


Insert sort – it is a very simple but inefficient algorithm that nevertheless has several specific advantages that make it relevant even after many other generally more efficient algorithms have been developed.

With insertion sort, you don't have to have the entire array up front before sorting. The algorithm can receive one element at a time during sorting. This is very handy if we need to add more elements during sorting. The algorithm will insert the new element at the right place without "re-executing" sorting the entire array.

Insertion sort can be used in practice due to its efficiency on small (~10 elements) datasets.

The problem is this: there is a part of the array that is already sorted, and you want to insert the remaining elements of the array into the sorted part, while maintaining order. To do this, at each step of the algorithm, we select one of the input data elements and insert it at the desired position in the already sorted part of the array, until the entire input data set is sorted. The method of selecting the next element from the input array is arbitrary, but usually (and in order to obtain a stable sorting algorithm), elements are inserted in the order of their appearance in the input array.

Algorithmic implementation of this algorithm
// The null element is considered to be an already sorted sequence.
// Therefore, the loop starts from 1
LOOP FOR I=1 TO N-1 STEP 1
   X=A[I]
   J=I
   WHEN J>0 AND A[J-1]>X //looking for a place to insert
     EXCHANGE A[J],A[J-1]
     J=J-1
   END BYE
   A[J]=X
 NEXT I
Computational complexity: \(\displaystyle O(n^{2})\).

Training problem

Insertion sort