Algorithms
A brief description of
the algorithms that are being animated in this system is presented here.
This algorithm will keep
scanning through the whole data set comparing the adjacent elements. If the
next element in line is smaller than the current one, the elements are swapped.
This way, the largest element will get ‘bubbled’ to the top of the data. A
method to make this algorithm more efficient will be to terminate the execution
of the algorithm as soon as the data is sorted.
Improved Bubble Sort
As opposed to bubble sort, instead of comparing and
sorting adjacent elements, the initial stage of this algorithm will be to first
compare and sort the elements that are (x = n/2) spaced apart where the size
of the data set is n elements. The next stage will be to reduce the
number of the spacing of the elements. The elements that will be compared and
sorted will be the elements that are (x = x/2) spaced apart. The spaces
between elements to be sorted, x, will continue to be reduced until it
reaches 1, whereby, adjacent elements will be compared and sorted.
Shaker Sort
The shaker sort algorithm is also known as the bi-directional
bubble sort algorithm. This algorithm will keep scanning through the data set,
and at the end of each scan, the two elements with the smallest and largest value
will be swapped with the elements in their correct places, at the front and the
back of the data set respectively. At the end of the next scan through the data
set, the elements with the next smallest and largest value will be swapped to
their respective sorted places.
Insert Sort
This algorithm is one whereby the front of the data
set is always maintained as a sorted set. Initially, the first element by
itself, is considered to be sorted. In its second step, the second element is
compared against the first element. If the second element is of value smaller
than the first element, they are swapped. This algorithm works by obtaining an
element and comparing it with all of the elements in front of it, one at a
time. If the element is smaller than the one in front of it, the adjacent
elements are swapped and the element will be compared again with the one in
front of it. This goes on until the element is greater than the one in front of
it or until it reaches the front of the data set.
Shell Sort
Shell sort is named after a computer scientist, Donald
L. Shell, who discovered it in 1959. It is based on the insertion sort, but
with a feature that improves the insertion sort’s performance. Unlike the
insertion sort that compares and sorts elements that are next to each other,
shell sort’s initial scan through the data set will do the insert sort on
elements that are spaced (x = n/2) apart, where the size of the data set
is n elements. This initial space, x, will continue to be repeated
reduced after every pass through the data set until it eventually becomes 1,
whereby, adjacent elements will be compared and sorted.
Select Sort
The idea of selection sort algorithm is to
repeatedly search for the next smallest (or largest) element in the data set
and move it to the first (or last) position in the data set in order to produce
a sorted data set. In this system’s demonstration of the select sort algorithm,
the algorithm will repeatedly search for the next smallest element in the data
set and place it in its correct position. When this algorithm is executed, it
will first set the value of the first element to be the smallest value. After
that, the algorithm will make a pass and scan through the rest of the elements
in the data set looking for any elements smaller than this minimum value. If an
element with a smaller value is found, the element with the smaller value will
be swapped with the element in its position.
Quick Sort
The quick sort algorithm consists of the following
four steps. Firstly, if the total number of elements in the data set is 0 or 1,
the algorithm execution is terminated. Secondly, pick any element in the data
set to be a pivot. In this system’s demonstration of the quick sort algorithm,
the pivot chosen is always the first element in the data set. Thirdly,
partition the data set into to disjoint groups. One group consists of all the
elements of the original data set that are smaller than the pivot, while the
other group consists of all the elements of the original data set that are
larger than the pivot. Lastly, quicksort is called recursively on the two
disjoint groups.
Links:
·
Home