`1) Stage J (Journey)
Introduction
Bubble Sort
Bubble sort is a simple and well-known sorting algorithm. It is used in practice once in a blue
moon and its main application is to make an introduction to the sorting algorithms. Bubble
sort belongs to O(n2) sorting algorithms, which makes it quite inefficient for sorting large
data volumes. Bubble sort is stable and adaptive.
Algorithm
1. Compare each pair of adjacent elements from the beginning of an array and, if they
are in reversed order, swap them.
2. If at least one swap has been done, repeat step 1.
Insertion Sort
Insertion sort belongs to the O(n2) sorting algorithms. Unlike many sorting algorithms with
quadratic complexity, it is actually applied in practice for sorting small arrays of data. For
instance, it is used to improve quicksort routine. Some sources notice, that people use same
algorithm ordering items, for example, hand of cards.
Algorithm
Insertion sort algorithm somewhat resembles selection sort. Array is imaginary divided into
two parts - sorted one and unsorted one. At the beginning, sorted part contains first element
of the array and unsorted one contains the rest. At every step, algorithm takes first element in
the unsorted part and inserts it to the right place of the sorted one. When unsorted part
becomes empty, algorithm stops.
Selection Sort
Selection sort is one of the O(n2) sorting algorithms, which makes it quite inefficient for
sorting large data volumes. Selection sort is notable for its programming simplicity and it can
over perform other sorts in certain situations (see complexity analysis for more details).
Algorithm
The idea of algorithm is quite simple. Array is imaginary divided into two parts - sorted one
and unsorted one. At the beginning, sorted part is empty, while unsorted one contains whole
array. At every step, algorithm finds minimal element in the unsorted part and adds it to the
end of the sorted one. When unsorted part becomes empty, algorithm stops.
When algorithm sorts an array, it swaps first element of unsorted part with minimal element
and then it is included to the sorted part. This implementation of selection sort in not stable.
50
Introduction
Bubble Sort
Bubble sort is a simple and well-known sorting algorithm. It is used in practice once in a blue
moon and its main application is to make an introduction to the sorting algorithms. Bubble
sort belongs to O(n2) sorting algorithms, which makes it quite inefficient for sorting large
data volumes. Bubble sort is stable and adaptive.
Algorithm
1. Compare each pair of adjacent elements from the beginning of an array and, if they
are in reversed order, swap them.
2. If at least one swap has been done, repeat step 1.
Insertion Sort
Insertion sort belongs to the O(n2) sorting algorithms. Unlike many sorting algorithms with
quadratic complexity, it is actually applied in practice for sorting small arrays of data. For
instance, it is used to improve quicksort routine. Some sources notice, that people use same
algorithm ordering items, for example, hand of cards.
Algorithm
Insertion sort algorithm somewhat resembles selection sort. Array is imaginary divided into
two parts - sorted one and unsorted one. At the beginning, sorted part contains first element
of the array and unsorted one contains the rest. At every step, algorithm takes first element in
the unsorted part and inserts it to the right place of the sorted one. When unsorted part
becomes empty, algorithm stops.
Selection Sort
Selection sort is one of the O(n2) sorting algorithms, which makes it quite inefficient for
sorting large data volumes. Selection sort is notable for its programming simplicity and it can
over perform other sorts in certain situations (see complexity analysis for more details).
Algorithm
The idea of algorithm is quite simple. Array is imaginary divided into two parts - sorted one
and unsorted one. At the beginning, sorted part is empty, while unsorted one contains whole
array. At every step, algorithm finds minimal element in the unsorted part and adds it to the
end of the sorted one. When unsorted part becomes empty, algorithm stops.
When algorithm sorts an array, it swaps first element of unsorted part with minimal element
and then it is included to the sorted part. This implementation of selection sort in not stable.
50
