CSC 112 – LECTURE SEVEN
Sorting algorithms
An algorithm is a step-by-step solution of a problem or task. It is
a way of providing the detailed procedure on how to solve a
particular task. It shows the details of the steps involved in the
solution process, the possible conditions and constraints to be
encountered along the line and how such will be handled.
A sorting algorithm is an algorithm that puts the data elements
of a list in a specific order, usually in numerical order or
lexicographical (alphabetical) order. Sorting often times needs to
be carried out on a list before some other operations can be
carried out. Sorting is therefore a very important part of data
processing.
The output of a sort must:
1. Be in the particular order specified. That is, if the data is to be
arranged in ascending order, no element should be smaller than
its preceding element and if in descending order, no element
should be bigger than its preceding element.
2. The output is a permutation (reordering) of the input.
So much of research has gone into the process of sorting data
items in a data structure and this has brought about several
methods of sorting.
Types of sorting algorithms
1. Bubble sort – It is a simple sorting algorithm that
continuously iterates through a list, swapping items until
they appear in the correct order. The algorithm starts at the
beginning of the data set, compares the first two elements,
and if the first is greater than the second, it swaps them so
that the first (which is the greater) can take the current sort
position.
This continues for each pair of adjacent elements till the
end of the data set is reached. It then starts again with the
first two elements, repeating the process until no swaps
have occurred which is on the last pass.
For instance, if we have a data set containing the following
numbers which are to be arranged in ascending order:
7, 5, 2, 3, 5, 0, 1, 5, 9, 6, 4
Upon the first sort, the list becomes
1st operation -5, 7, 2, 3, 5, 0, 1, 5, 9, 6, 4
2nd operation -5, 2, 7, 3, 5, 0, 1, 5, 9, 6, 4
3rd operation -5, 2, 3, 7, 5, 0, 1, 5, 9, 6, 4
4th operation -5, 2, 3, 5, 7, 0, 1, 5, 9, 6, 4
5th operation -5, 2, 3, 5, 0, 7, 1, 5, 9, 6, 4
6th operation -5, 2, 3, 5, 0, 1, 7, 5, 9, 6, 4
7th operation -5, 2, 3, 5, 0, 1, 5, 7, 9, 6, 4
8th operation -5, 2, 3, 5, 0, 1, 5, 7, 9, 6, 4
9th operation -5, 2, 3, 5, 0, 1, 5, 7, 6, 9, 4
10th operation-5, 2, 3, 5, 0, 1, 5, 7, 6, 4, 9
After the 10th operation, the process is started all over again
from the beginning of the list, comparing adjacent values
and swapping them. This process is continued until no more
swapping can occur in the list an then, the list is finally
sorted.
2. Selection sort - is an in-place comparison sort. It is
inefficient on large
lists. The algorithm finds the minimum value, swaps it with
the value in the first position, and repeats these steps for
the remainder of the list.
Selection sort is simple and also has performance
advantages over more complicated algorithms in certain
situations.
Using the same example as in the bubble sort algorithm,
consider
7, 5, 2, 3, 5, 0, 1, 5, 9, 6, 4
With selection sort, it is done in the following way:
1st operation-Since 0 is the least, and is at position 6, it is
swapped with 7 on position 1.
0, 5, 2, 3, 5, 7, 1, 5, 9, 6, 4
2nd operation-The next smallest is 1 on position 7 to be
swapped with 5 on position 2.
0, 1, 2, 3, 5, 7, 5, 5, 9, 6, 4
3rd operation-2 on position 3 need not be swapped
4th operation-3 on position 4 need not be swapped
5th operation-0, 1, 2, 3, 4, 7, 5, 5, 9, 6, 5
6th operation-0, 1, 2, 3, 4, 5, 7, 5, 9, 6, 5
7th operation-0, 1, 2, 3, 4, 5, 5, 7, 9, 6, 5
8th operation-0, 1, 2, 3, 4, 5, 5, 5, 9, 6, 7
9th operation-0, 1, 2, 3, 4, 5, 5, 5, 6, 9, 7
10th operation-0, 1, 2, 3, 4, 5, 5, 5, 6, 7, 9
With this, the list is already sorted.
3. Insertion sort - It is a simple sorting algorithm that is
relatively efficient for small lists and is often used as part of
more sophisticated algorithms. It works by taking elements
from the list one after the other and inserting them in their
correct position into a new sorted list. That is, there is a list
which is unsorted. To sort this list, another new list is
created which is originally without elements. This newly
created list will be gradually filled with the elements of the
unsorted list in order. When an element is to be inserted
into the new list, the elements in the new list are checked to
see the rightful position of the element to be inserted. It is
then inserted where it ought to be, following the desired
sequence. This may cause some of the already placed
elements to be shifted in order to create its own position.
Insertion can be quite expensive because it often requires
shifting all following elements over by one.
Using the same example as in the bubble sort algorithm,
consider
7, 5, 2, 3, 5, 0, 1, 5, 9, 6, 4
For the insertion sort, a new list is created and the
following take place:
1st operation-7
2nd operation-5, 7 (7 is shifted from position 1 to 2)
3rd operation-2, 5, 7 (5 is shifted from 1 to 2 and 7 from 2 to
3)
4th operation-2, 3, 5, 7 (2 is unchanged while others
change)
5th operation-2, 3, 5, 5, 7
6th operation-0, 2, 3, 5, 5, 7 (all shift by 1 position for 0 to be
on position 1)
7th operation-0, 1, 2, 3, 5, 5, 7 (0 remains unchanged while
others shift)
8th operation-0, 1, 2, 3, 5, 5, 5, 7 (only 7 shifts to allow 5
before it)
9th operation-0, 1, 2, 3, 5, 5, 5, 7, 9 (no position shift, 9 is
only added)
10th operation-0, 1, 2, 3, 5, 5, 5, 6, 7, 9 (7 and 9 shift)
11th operation-0, 1, 2, 3, 4, 5, 5, 5, 6, 7, 9 (0, 1, 2, 3 remain
unchanged while others shift)
With this, the list is already sorted.
4. Merge sort – is a type of sorting method that takes
advantage of the ease of merging already sorted lists into a
new sorted list. It is a variant of the bubble sort and it is a
divide-and-conquer algorithm which makes use of the
concept of dividing a complex task into smaller tasks which
are easier to handle. After these smaller tasks are solved,
their results are combined together to form the overall
solution.
It starts by comparing every two elements (i.e., 1 with 2,
then 3 with 4...) and swapping them if the first should come
after the second. It then merges each of the resulting lists
of two into lists of four, and then merges the lists of four,
and so on; until at last two lists are merged into the final
sorted list. It is well-suited for sorting large lists. It is
gaining wide acceptance and use.
Consider the following list:
7, 1, 2, 3, 8, 0, 1, 5, 9, 6
From the above list, two smaller lists are derived which are:
7, 1, 2, 3, 8 0, 1, 5, 9, 6
These two lists are then further individually divided into
smaller lists.
7, 1, 2, 3, 8 0, 1, 5,
9, 6
7, 1, 2 3, 8 0, 1, 5 9,
6
0,1 5 9
6
7, 1 2 3 8 0
1
7 1 2 3 8 0 1
5 9 6
The initially complex list is divided into several small lists
containing just one element, each list is then sorted and
merged together.
1, 7 2 3, 8 0, 1 5 6, 9
1, 2, 7 3,8 0, 1, 5 6, 9
1, 2, 3, 7, 8 0, 1, 5, 6, 9
0, 1, 1, 2, 3, 5, 6, 7, 8, 9 (final sorted list)
Other sorting algorithms include bucket sort, quicksort,
heapsort, radix sort, counting sort, shell sort, comb sort,
distribution sort and timsort algorithms. Other algorithms
can be developed for better processing of tasks.
Searching algorithms
Searching is a process of looking through a set of data to
pick or fish out the desired data for use. There are
situations when not all the data contained in a data set are
required for processing. In such cases, the desired data to
be used is searched for using a searching algorithm.
There are basically two (2) approaches to searching through
a data set:
a) Sequential search and
b) Binary search.
Sequential Search - Sequential search involves looking at
each value in turn. That is, the whole data set is traversed
in the search of the required data. Each data element is
looked at and inspected to see if it matches the desired data
to be searched for. If the current element matches the
desired element, the data element is returned and if not the
required element, the next element is looked at. This
continues till the end of the list is reached. The algorithm
quits and returns true if the current value is the desired
value and it quits and returns false if it has looked at all of
the values in the data set without finding the desired value.
If the values are in sorted order, then the algorithm can
sometimes quit and return false without having to look at all
of the values in the data set. The desired value is not in the
array if the current value is greater than the desired value.
Binary search – This algorithm can be used and is
preferred when the values are in sorted order. The
algorithm for binary search starts by looking at the middle
item x, of the data set. If x is equal to the desired element,
v, it quits and returns true. Otherwise, it uses the relative
ordering of x and v to eliminate half of the array. If the
desired element, v is less than x, then it can't be stored to
the right of x in the array and so, all the elements on the
right can be eliminated; similarly, if it is greater than x, it
can't be stored to the left of x and so, all elements to the left
are eliminated. Once half of the array has been eliminated,
the algorithm starts again by looking at the middle item in
the remaining half. It quits when it finds v or when the
entire array has been eliminated.
Question
1. Explain the different types of sorting algorithms.
2. Explain the different searching algorithms.
