Sorting:
What will you do if you were asked to search for a particular telephone number in a directory.
You will ask for the surname of the particular person and as the directory is sorted in an ascending order of alphabets, it will not be difficult to find the telephone number.
But if the case is reverse , you know the phone number and you wish to find the name of the person using the telephone directory , will it be easy like the first case.
One would have to search the entire directory sequentially for this purpose.
This example illustrates how difficult it is to search , if the contents or objects cannot be accessed in sorted order .
Data cannot be retrieved efficiently if it is not placed in a particular format.
To convert an unsorted list of data items into an ordered list is known as sorting.
There are searching methods , like the binary search, which require the data to be sorted .
We can define sorting as arrangement of elements in a list according to the increasing or decreasing (ascending/descending) value of each element.
There are many programs and processes in the computer , which require sorted data .
Every time there is new entry , sorting is done and it is put in its proper position.
A computer on an average spends 25 to 40% of its time in sorting .
The only way to search any element in an unordered list is to perform sequential search.
If we have a list having thousands of records then this sequential search will take a very large amount of time to search a given element.
The worst part comes when you search the whole list for a particular record, only to find that it does exist.
Sorting is one of the most important operations to be performed on the list.
The elements in the list may contain single values or records.
Sorting process should be done using minimum amount of time .
There has been much work done to find optimal algorithms to perform sorting under various environments.
Most of the algorithms are sophisticated and lack clarity , but the time factor is so critical that clarity can be sacrificed for it.
Sorting is classified into two categories depending on the environment.
Internal Sorting::
This type of sorting is used when the list does nto contain a large number of elements.
When sorting is done by this method , all the records to be sorted are present in the main memory.
External Sorting::
In this type of sorting , it is not possible to store all the records in the main memory of the computer .
They are stored on devices such as tapes and disks.
Then they are brought into the memory part by part and sorted .
The final list is in sorted order.
There are separate algorithms designed for this purpose .
We will study the internal sorting algorithms.
Sorting again can be classified into two parts depending on whether the records are moved physically to their proper place or their proper position is indicated through some other means.
The following list is sorted using the swap technique:
Before sorting :
Location : 1 2 3 4 5
Number : 21 12 9 2 40
After Sorting :
Location : 1 2 3 4 5
Number : 2 9 12 21 40
If the records are moved physically then time is required to swap the records .
This time will be very large if the individual records are huge in size.
Under such circumstances another method called as sort by address , is used .
In this method , there is an array of pointers points to its corresponding object in the list.
Unsorted list using the sort by address method
When sorting is performed the pointers,
which point to the respective elements, are
moved instead of the elements.The first pointer
will point to the record that should be the first
record after sorting.The physical position of
the records will not change.If we want to access
pointed to by the first pointer will look as shown
'5' and so on. The sorted list will look as shown'
in the figure. There are some basic operations,
which aarre performed , in all the sorting algorithm, viz ,comparison ,assignment and swap-
ping. Usually the execution of the sorting algorithm.
Space is another important factor in the list and on the length of the itself.
1) Use of storage space.
2) Use of computer time.
3) Programming effort.
4) Statistical deviation.
Sorted array by the sort by address method
Let us study each of the factors and see how
they affect the efficiency.
1) Use of storage space.
A program requires very small amount of
space for itself in the mercury. In fact it is negligible as compared to the list to be sorted. The
given list of elements is stored in an array. There
list. The number of lists depends on the type of
array while some use the original list only. The
the original list.Once the sorting is completed,
Some algorithms use only the original list.The number of recursive calls made to the produce.
2)Use of computer time.
The major time is consumed by the various
operations like swapping , comparison and assignment. The time required also depends on
the number of objects present in the list. The
looping structure depends on the number of every critical factor in sorting.
3) Programming effort.
There are various methods used for sorting
A lot of programming effect is put in to find
new algorithms ,which require less time and
space. This require a lot of resesch and still
does not guarantee success. If space and time
are not restricted and the improvement in the
time and space factor is not very significant then
it is adives to us the advisable to take efforts
and find out a new alorithm.
Insertion Sort.
Let us consider an example and try to find
out how insertion sort works. After that,we will
code the algorithm.We have a list'A' of five
elements as follows:
List A: 4,3,2,0,1.
We will sort it in ascending order using insertion sort. We start from the first element 4,it
is the only element we have selected so far hence
it remains as it is. The next element is 3.
List A : 3,4,2,0,1.
Analysis.
The performance of insertion sort depends
on the initial ordering of the elements. There
are two for loops in the algorithm of insertion
sort.The first for loop is always executed for n
times, but execution of the elements. We
will the three cases viz. best, worse and
average case for insertion sort.
F(n)=1+1+.....+1=n=o(n)
While the worst case will be when the element are in the reverse order.The second for
loop will be executed in the following pattern.
F(n)=1+2+3+4...............+n=n(n-1) /2=
O (n2)
The average case will be as shown below:
F(n)=1/2 +2/2 +3/2+..........+n/2=n (n-1) 4=
O (n2)
We find that in insertion sort the proper position of the elements is found out first and
then to place it there all the elements below it are moved one place below.
This cause swapping of elements .If there are a large number of elements in the array then this process will consume a lot of time .
As the complexity is n 2, if there are 10 elements then the complexity will be 100 and if this number increases to 100
then the complexity will be 10000.
Hence , we conclude that this method is suitable for lists containing 20 to 30 elements .
This technique is inefficient in moving elements their proper place.
A lot of time is consumed in swapping elements.
Selection sort:
Example :
List A: 4,3,2,0,1.
We want to sort in ascending order.
We will have to find out the smallest element in the whole list and place it in its proper position by swapping .
In the above list, we find that 0 is the smallest element and it should be placed in the first place .
However , the first place is occupied by 4 , hence the 4 and 0 are swapped . Now the list will look as follows:
List A: 0,3,2,4,1.
Now our list will be from the second element onwards i.e. 3,2,4,1.
We find the smallest element among them 1 is the smallest and it should be placed at the start of the list i.e. at the second position .
So 3 and 1 are swapped and the list will be as follow :
List A: 0,1,2,4,3
The next list to be checked will be from the third position until the end i.e. 2,4,3.
The smallest element is found out to be 2 and it is placed at its proper position.
Here we find that although 2 was in its proper position the process did not change.
Selection sort does consider the order in which the elements are placed initially.
Even if the element is in its proper position , it will be swapped with itself .
Now with the next iteration the list will be completely sorted 4 and 3 will be swapped with each other .
The final list will be as follow:
List A:0,1,2,3,4
We can define selection sort as an algorithm in which the successive elements are selected in order and placed into their
proper sorted position.
What will you do if you were asked to search for a particular telephone number in a directory.
You will ask for the surname of the particular person and as the directory is sorted in an ascending order of alphabets, it will not be difficult to find the telephone number.
But if the case is reverse , you know the phone number and you wish to find the name of the person using the telephone directory , will it be easy like the first case.
One would have to search the entire directory sequentially for this purpose.
This example illustrates how difficult it is to search , if the contents or objects cannot be accessed in sorted order .
Data cannot be retrieved efficiently if it is not placed in a particular format.
To convert an unsorted list of data items into an ordered list is known as sorting.
There are searching methods , like the binary search, which require the data to be sorted .
We can define sorting as arrangement of elements in a list according to the increasing or decreasing (ascending/descending) value of each element.
There are many programs and processes in the computer , which require sorted data .
Every time there is new entry , sorting is done and it is put in its proper position.
A computer on an average spends 25 to 40% of its time in sorting .
The only way to search any element in an unordered list is to perform sequential search.
If we have a list having thousands of records then this sequential search will take a very large amount of time to search a given element.
The worst part comes when you search the whole list for a particular record, only to find that it does exist.
Sorting is one of the most important operations to be performed on the list.
The elements in the list may contain single values or records.
Sorting process should be done using minimum amount of time .
There has been much work done to find optimal algorithms to perform sorting under various environments.
Most of the algorithms are sophisticated and lack clarity , but the time factor is so critical that clarity can be sacrificed for it.
Sorting is classified into two categories depending on the environment.
Internal Sorting::
This type of sorting is used when the list does nto contain a large number of elements.
When sorting is done by this method , all the records to be sorted are present in the main memory.
External Sorting::
In this type of sorting , it is not possible to store all the records in the main memory of the computer .
They are stored on devices such as tapes and disks.
Then they are brought into the memory part by part and sorted .
The final list is in sorted order.
There are separate algorithms designed for this purpose .
We will study the internal sorting algorithms.
Sorting again can be classified into two parts depending on whether the records are moved physically to their proper place or their proper position is indicated through some other means.
The following list is sorted using the swap technique:
Before sorting :
Location : 1 2 3 4 5
Number : 21 12 9 2 40
After Sorting :
Location : 1 2 3 4 5
Number : 2 9 12 21 40
If the records are moved physically then time is required to swap the records .
This time will be very large if the individual records are huge in size.
Under such circumstances another method called as sort by address , is used .
In this method , there is an array of pointers points to its corresponding object in the list.
Unsorted list using the sort by address method
When sorting is performed the pointers,
which point to the respective elements, are
moved instead of the elements.The first pointer
will point to the record that should be the first
record after sorting.The physical position of
the records will not change.If we want to access
pointed to by the first pointer will look as shown
'5' and so on. The sorted list will look as shown'
in the figure. There are some basic operations,
which aarre performed , in all the sorting algorithm, viz ,comparison ,assignment and swap-
ping. Usually the execution of the sorting algorithm.
Space is another important factor in the list and on the length of the itself.
1) Use of storage space.
2) Use of computer time.
3) Programming effort.
4) Statistical deviation.
Sorted array by the sort by address method
Let us study each of the factors and see how
they affect the efficiency.
1) Use of storage space.
A program requires very small amount of
space for itself in the mercury. In fact it is negligible as compared to the list to be sorted. The
given list of elements is stored in an array. There
list. The number of lists depends on the type of
array while some use the original list only. The
the original list.Once the sorting is completed,
Some algorithms use only the original list.The number of recursive calls made to the produce.
2)Use of computer time.
The major time is consumed by the various
operations like swapping , comparison and assignment. The time required also depends on
the number of objects present in the list. The
looping structure depends on the number of every critical factor in sorting.
3) Programming effort.
There are various methods used for sorting
A lot of programming effect is put in to find
new algorithms ,which require less time and
space. This require a lot of resesch and still
does not guarantee success. If space and time
are not restricted and the improvement in the
time and space factor is not very significant then
it is adives to us the advisable to take efforts
and find out a new alorithm.
Insertion Sort.
Let us consider an example and try to find
out how insertion sort works. After that,we will
code the algorithm.We have a list'A' of five
elements as follows:
List A: 4,3,2,0,1.
We will sort it in ascending order using insertion sort. We start from the first element 4,it
is the only element we have selected so far hence
it remains as it is. The next element is 3.
List A : 3,4,2,0,1.
Analysis.
The performance of insertion sort depends
on the initial ordering of the elements. There
are two for loops in the algorithm of insertion
sort.The first for loop is always executed for n
times, but execution of the elements. We
will the three cases viz. best, worse and
average case for insertion sort.
F(n)=1+1+.....+1=n=o(n)
While the worst case will be when the element are in the reverse order.The second for
loop will be executed in the following pattern.
F(n)=1+2+3+4...............+n=n(n-1) /2=
O (n2)
The average case will be as shown below:
F(n)=1/2 +2/2 +3/2+..........+n/2=n (n-1) 4=
O (n2)
We find that in insertion sort the proper position of the elements is found out first and
then to place it there all the elements below it are moved one place below.
This cause swapping of elements .If there are a large number of elements in the array then this process will consume a lot of time .
As the complexity is n 2, if there are 10 elements then the complexity will be 100 and if this number increases to 100
then the complexity will be 10000.
Hence , we conclude that this method is suitable for lists containing 20 to 30 elements .
This technique is inefficient in moving elements their proper place.
A lot of time is consumed in swapping elements.
Selection sort:
Example :
List A: 4,3,2,0,1.
We want to sort in ascending order.
We will have to find out the smallest element in the whole list and place it in its proper position by swapping .
In the above list, we find that 0 is the smallest element and it should be placed in the first place .
However , the first place is occupied by 4 , hence the 4 and 0 are swapped . Now the list will look as follows:
List A: 0,3,2,4,1.
Now our list will be from the second element onwards i.e. 3,2,4,1.
We find the smallest element among them 1 is the smallest and it should be placed at the start of the list i.e. at the second position .
So 3 and 1 are swapped and the list will be as follow :
List A: 0,1,2,4,3
The next list to be checked will be from the third position until the end i.e. 2,4,3.
The smallest element is found out to be 2 and it is placed at its proper position.
Here we find that although 2 was in its proper position the process did not change.
Selection sort does consider the order in which the elements are placed initially.
Even if the element is in its proper position , it will be swapped with itself .
Now with the next iteration the list will be completely sorted 4 and 3 will be swapped with each other .
The final list will be as follow:
List A:0,1,2,3,4
We can define selection sort as an algorithm in which the successive elements are selected in order and placed into their
proper sorted position.
