2015 12th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD)

Optimized Selection Sort Algorithm for Two

Dimensional Array

Sultan Ullah, Muhammad A. Khan Mudasser A. Khan, H. Akbar, and Syed S. Hassan
Department of Information Technology, Computer and Communication Research Lab
University of Haripur, University of Haripur,
Haripur, Pakistan. Haripur, Pakistan.
Email: (sultan,aamir)@[Link] Email: (mudasser,habib,shabih)@[Link]

Abstract—The main idea of Optimized Selection Sort Algo- factor of four. It is also a matter of great concern that, the
rithm (OSSA) is based on the already existing selection sort algo- nature of the data also has an effect on the efficiency of
rithm, with a difference that old selection sort; sorts one element the algorithm. A sorting algorithm may behave differently
either smallest or largest in a single iteration while optimized if the original data set is almost sorted rather than if it is
selection sort, sorts both the elements at the same time i.e smallest random or it may be in the reverse order. The creation of
and largest in a single iteration. In this study we have developed
spatial data structures that are important in computer graphics
a variation of OSSA for two-dimensional array and called it
Optimized Selection Sort Algorithms for Two-Dimensional arrays and geographic information systems is necessarily a sorting
OSSA2D. The hypothetical and experimental analysis revealed procedure. A well-organized sort routine is also a useful unit
that the implementation of the proposed algorithm is easy. The in implementing algorithms like sparse matrix multiplication
comparison shows that the performance of OSSA2D is better and parallel programming patterns like Map Reduce [3], [4].
than OSSA by four times and when compared with old Selection The idea of optimized selection is based on the old selection
Sort algorithm the performance is improved by eight times (i.e if sort [5]. Unlike the old selection sort which sort data item
OSSA can sort an array in 100 seconds, OSSA2D can sort it in one at a time, the optimized selection sort algorithm (OSSA)
24.55 Seconds, and similarly if Selection Sort takes 100 Seconds sort two data elements (smallest as well largest) in a single
then OSSA2D take only 12.22 Seconds). This performance is iteration. It reduced the execution time of the selection sort
remarkable when the array size is very large. The experiential
by almost fifty percent, although this algorithm also has
results also demonstrate that the proposed algorithm has much
lower computational complexity than the one dimensional sorting a computational time complexity of Big O((n)2 ) [5], [6].
algorithm when the array size is very large. Enormous data in many fields is normally represented by the
use of Matrices. It is felt by the computer professional to have
Keywords—Algorithm analysis, Sorting algorithms, Two Dimen- efficient sorting algorithms for sorting the two-dimensional
sional Arrays, Computational Complexity. arrays. There is plenty of algorithms which mainly focuses on
one-dimensional array sorting, but a few algorithms have been
I. I NTRODUCTION proposed for two-dimensional array sorting [7], [8], [9]. In
[8], the result is extended from one-dimensional array to two-
Sorting and Searching are the tasks that are repeatedly en-
dimensional by the use of interpolation and filtering algorithms
countered in various computer applications. Since they reveal
which results in a complexity of O((mn)2 ). Two-dimensional
basic tasks that must be deal with quite frequently, researchers
array AR(M,N) is treated as one dimensional array by most
have tried in the past to develop algorithms efficient in terms
of the earlier sorting algorithms to sort these mn elements
of least memory requirement and least time requirement.
[10], [11], [12]. Simple selection sorting is the widely sorting
Searching together with sorting is perhaps the most common
algorithm used due to its simplicity and less implementation
operation used in Computing. It was always a matter of
complexity. Although it has a time complexity of O((mn))2
great attraction for the researchers that to reduce the time a
) on sorting one dimensional array with mn elements as (n-
computer takes in sorting and searching data [1], [2]. That’s
1)nm/2 comparison operations are required. The time required
why, the researcher tried to develop speedy, well-organized
for sorting large arrays (e.g. arrays with 1000000*1000000
and economical algorithms for sorting and ordering lists and
elements) is practically much time consuming. In this article,
arrays. This was one of the fundamental fields of research in
we propose an optimized sort algorithm for two dimensional
computing for decades. The development of optimized sorting
arrays, to solve the above mentioned problem of sorting.
algorithms will leads to efficient computing as whole. It is
The hypothetical and experimental results proved that this
observed that, the time to complete the task for most sorting
proposed algorithm has a high efficiency level [10], [13].
algorithms depends on the amount of data. Consequently to
The paper is organized in the following manner. In section
analyze an algorithm, it is required to find a relationship
2 the algorithm for two dimensional arrays is proposed. The
showing how the time needed for the algorithm depends on
proposed algorithm (OpSSA2D) is analyzed in section 3. In
the amount of data. It is observed that, for an algorithm,
Section 4, the approach of sorting single dimensional arrays is
when the amount of data is doubled, the time needed is also
presented for the proposed algorithm. Section 5, Experimental
doubled. Similarly from the analysis of another algorithm
analysis and discussion is presented and Section 6 contain
it was cleared that when the amount of data is increased
conclusion.
the time to complete the task of sorting is increased by a

978-1-4673-7682-2/15/$31.00 ©2015 IEEE 2549

Authorized licensed use limited to: Ingrid Nurtanio. Downloaded on October 01,2020 at [Link] UTC from IEEE Xplore. Restrictions apply.
II. P ROPOSED O PTIMIZED S ELECTION S ORT A LGORITHM
F OR T WO D IMENSIONAL A RRAYS ((mn2 − mn) + 4(nm2 + nm))
f (m, n) =
4
The main idea of Optimized Selection sort is based on
already existing selection sort algorithm, with a difference that The time complexity for the algorithm after ignoring the
selection sort, sorts one element either smallest or largest in constant and lower terms will be: O(mn2 + nm2 )
a single iteration while optimized selection sort, sorts the two
elements at a time i.e smallest and largest in a single iteration. In [6] the efficiency of old selection sort algorithm for
We have developed a variation of the already existing selec- one-dimensional array having the same number of elements
tion sort for two-dimensional array and called it Optimized as that with the two-dimensional array is found as follows.
Selection Sort Algorithms for Two-Dimensional array. For one dimensional array the number of comparison needed
by selection sort;
We have amatrix in the form of AR(M,N)as follows (mn − 1)mn
AR11 AR12 . AR1n (2)
2
 . . . . 
For two-dimensional array with equal number of elements as
AR(M, N ) = 
 
 . . . . 
 that of one-dimensional array the number of comparisons are;
AR1m ARm2 .... ARmn nm(n − 1)
+ mn(m − 1) (3)
Before going to the stepwise details of the algorithm 2
we will create a new array Y(M,N) which will store sorted The efficiency Calculated for efficient two dimensional sorting
elements. The working of our proposed optimized selection algorithms in [10]is;
algorithm for two-dimensional array is depicted in the follow- mn
ing steps: 2 (mn − 1)
mn(n−1)
2 + mn(m − 1)
STEP 1: Each row of the array should be sorted using
the Optimized Selection Sorting Algorithm (Let assume that (mn − 1)
the elements are sorted in descending order in each row). =
(n + 2m − 3)
STEP 2: Initialize the index values of the target array i.e Y mn
such that (row,col)as row = col = 1 ≈ (4)
STEP 3: Find the Largest element from the first column and n+m
placed it into Y(row,col) the successor the largest will now Now calculating the efficiency of optimized selection sort
be the first element of the row. algorithm for two-dimensional array, against the efficiency of
STEP 4: Update the index values for row,col col = col + 1 optimized selection sort for one dimension array;
If col > nthen col = 1, row = row + 1 mn
STEP 5: Goto step (3) if AR is not empty, else goto Exit. 4 (mn − 1)
mn(n−1)
STEP 6: EXIT. 4 + mn(m − 1)
(mn − 1)
=
(n + 4m − 5)
III. A NALYSIS OF O P SSA2D
mn
The Most of the time in sorting process the algorithms ≈ (5)
n + 4m
major cost is on the comparisons of the data items to be sorted.
Again calculating the efficiency of optimized selection sort for
Therefore we analyzed the time complexity of by computing
two-dimensional array against old selection sort for the same
the number of comparison which is performed. As we know
number of data items;
for sorting one dimension array the number of comparison re-
quired by the selection sort is (n(n−1))
2 but we have introduced mn
the OSSA which performs less number of comparisons and 2 (n − 1)
it becomes (n(n−1))
4 [1]. Let assume that there are m rows mn(n−1)
4 + mn(m − 1)
in a two-dimensional array. So (nm(n−1))4 times comparison 2(mn − 1)
will be required to sort all the rows of the array. Now after =
sorting each row of the array in descending order by the (n + 4m − 5)
above mechanism we will now search the maximum element 2mn
in the first column. For this purpose the number of comparison ≈ (6)
n + 4m
needed is (m − 1) and there are m rows and n columns. So
for all the comparison in the array it needs mn(m − 1). After Similarly calculating the efficiency of optimized selection sort
finding the element in the first column it will be transferred of two-dimensional against the efficient selection sort for two-
to the target array. Therefore the total number of comparison dimensional array; from equation and we have:
needed for the two-dimensional array to be sorted using OSSA mn
2 (n − 1) + (m − 1)mn
for two dimensional array will be: mn(n−1)
4 + mn(m − 1)

nm(n − 1) 2(n + 2m − 3)
f (m, n) = + nm(m − 1) (1) (n + 4m − 5)
4

2550
Authorized licensed use limited to: Ingrid Nurtanio. Downloaded on October 01,2020 at [Link] UTC from IEEE Xplore. Restrictions apply.
 2(n + 2m)
p
≈ (7) is 100/4(4( ((4100)) − 5), 1875 times which is much more
n + 4m less than the Optimized Selection Sort Algorithm for one
Now consider if we have the values of n = 10000 and the dimensional array. We can calculate the values of m,and n
value of m = 10000 After putting the values in equation we by the following method.
r
2mn (4K)
m=
n + 4m 4
2(108 )
= m = int(m)
104 + 4(104 )
= 400 n = 4m
The above result shows that our algorithm is 400 times efficient
than the ordinary selection sort for one dimensional array If (m > (int)m)
having same amount of data. if we put the values in the
equation: m = (int)m + 1
2(n + 2m)
n + 4m
If (m > (int)m)
2(104 + 2(104 )
=
104 + 4(104 ) m = (int)m + 1
= 1.2
K
The above result shows that this proposed algorithm is still n=
more efficient than the already existing algorithm for two- m
dimensional array having same amount of data[10].
If (n > (int)n)
IV. C ONVERSION OF S INGLE D IMENSIONAL A RRAY TO
T WO D IMENSIONAL A RRAY n = (int)n + 1
It has been observed in the previous section that the sorting
of two-dimensional array is far more efficient than the one- Some times it might happen that the calculated value of
dimensional array for the same number of elements. In this (mn) > K, so we need to fill the empty cells of the array
section we have tried to convert a one-dimensional array with with imaginary values depending upon the data to be sorted.
constant elements K to a two-dimensional array having (m n) If the data is sorted in the descending then we will fill the
data elements. According to equation: empty cells with infinitesimal values and with infinite values
nm(n − 1) otherwise.
f (m, n) = + nm(m − 1)
4
nm
f (m, n) = (n + 4m − 5) V. R ESULTS AND D ISCUSSION
4
AndK = (n × m) In this section, Optimized Selection Sort Algorithm for
Two Dimensional Arrays is compared with other existing
K algorithm of the same computational complexity. In the Table
f (m, n) =(n + 4m − 5)
4 1, the comparison between Simple Selection Sort, Optimized
Since K is a constant and m, n >= 1 so according to Selection Sort for Single Dimensional Arrays and Optimized
geometric inequality; Selection Sort Algorithm for Two Dimensional Arrays are
presented which are as under:
K p
(4 (n × 4m − 5))
4
√ A. Comparison of Selection, Optimized Selection and Opti-
When n = 4m = 4K then the values of f (m, n)is the mized Selection Sort Algorithm for Two Dimensional Arrays
minimum value.
This section represents the comparison of old selection sort
K p with the optimized variant of the selection sort algorithms as
(4 (4K − 5)) (8) presented in Table 1.
4
From the above equation we can calculate the number of When we plot the graph of Selection Sort Algorithm (SSA)
comparison of two-dimensional arrays and found that it has the and Optimized Selection Sort Algorithm for Two Dimensional
lowest value. As the number of comparison of one-dimensional Array (OpSSA2D), we can see that the performance is im-
array is given by K(K − 1)/4, so if the number is increased proved. The analysis further shows that SSA take 100 seconds
by 100 times so we need 100(100 − 1)/4, almost 2500 times to complete a sorting job, while the same is done in 12.41
more comparisons as that of the two dimensional array which seconds by OpSSA2D. These results are presented in figure 1.

2551
Authorized licensed use limited to: Ingrid Nurtanio. Downloaded on October 01,2020 at [Link] UTC from IEEE Xplore. Restrictions apply.
 TABLE I. R ESULTS OF S ELECTION S ORT, OSSA FOR O NE TABLE II. R ESULTS OF I NSERTION S ORT, AND O PTIMIZED
D IMENIONAL A RRAY AND O P SSA S ELECTION S ORT A LGORITHM FOR 2D A RRAY

K Slection Sort OSSA 1D OpSSA K Insertion Sort OpSSA

1000.0 499500.0 249750 61995.55 1000.0 499400.0 61995.55

5000.0 12497500.0 6248750.0 700856.8 5000.0 12496500.0 700856.8

10000.0 49995000.0 24997500.0 1987500 10000.0 49994000.0 1987500

15000.0 1.12E+08.0 56246250.0 3655485 15000.0 1.10E+08.0 3655485

20000.0 2E+08.0 99995000.0 5631854.0 20000.0 1.9E+08.0 5631854.0

Fig. 2. Results of Insertion Sort, and Optimized Selection Sort Algorithm

Fig. 1. Results of Selection Sort, OSSA for One Dimensional Array and for 2D Array
OpSSA2D

C. Comparison of Efficient Selection Sort and Optimized Se-

lection Sort Algorithm for Two Dimensional Arrays
B. Comparison of Insertion Sort and Optimized Selection Sort
Algorithm for Two Dimensional Arrays The Section describes the comparison of proposed and
already existing algorithm. Table 3 contains the results.

The comparison of Insertion Sort and optimized selection The efficient selection sort is another implementation for
sort algorithm for two dimensional arrays is presented in this selection sort. The graph contains the comparison of efficient
section. These results are shown in Table 2. selection sort (EfSSA) and with OpSSA2D. The results shows
that OpSSA2D is much better that than EfSSA.
The results of insertion sort and OpSSA2D are plotted and Although the computational complexity of both the algo-
presented in figure 2. These results show that the time taken by rithms are O(n2 ), but the performance of OpSSA2d even get
OpSSA2D is much lesser as compared with insertion sort. Both better and better when the data volume is high. Despite the
these algorithms belongs to the same family of comparison computational complexity the results of Optimized Selection
based sorting algorithms. It is cleared from the figure that Sort Algorithm for two Dimensional Array are promising and
the performance of Optimized Selection for Two Dimensional support our claim to be better than other comparison based
array is much better in comparison with insertion sort. sorting algorithms.

2552
Authorized licensed use limited to: Ingrid Nurtanio. Downloaded on October 01,2020 at [Link] UTC from IEEE Xplore. Restrictions apply.
 TABLE III. R ESULTS OF E FFICIENT S ELECTION S ORT, AND
O PTIMIZED S ELECTION S ORT A LGORITHM FOR 2D A RRAY rithms. It is stable and very simple to implement. It is evident
from the above results that optimized selection algorithm for
two-dimensional arrays is more efficient than the other sorting
K Efficient Sort OpSSA
algorithm of the same complexity for the same amount of data.
Hereafter proved our claim to be an efficient algorithm of the
1000.0 123991.1 61995.55 order of O(n2 ). It could be useful algorithm when it needs to
solve the problem of sorting huge volume of data in reasonably
easy manner and efficiently.
5000.0 1401714 700856.8

R EFERENCES
10000.0 3975000 1987500
[1] D. Kitabı, “Th cormen, ce leiserson, rl rivest and c. stein: Introduction
to algorithms,” 2001.
15000.0 7310969 3655485 [2] C. L. Muller and C. Kidd, “Debugging geographers: teaching pro-
gramming to non-computer scientists,” Journal of Geography in Higher
Education, vol. 38, no. 2, pp. 175–192, 2014.
20000.0 11263708 5631854 [3] S. Matsuoka, H. Sato, O. Tatebe, M. Koibuchi, I. Fujiwara, S. Suzuki,
M. Kakuta, T. Ishida, Y. Akiyama, T. Suzumura et al., “Extreme big
data (ebd): Next generation big data infrastructure technologies towards
yottabyte/year,” Supercomputing frontiers and innovations, vol. 1, no. 2,
pp. 89–107, 2014.
[4] F. Kaashoek, R. Morris, and Y. Mao, “Optimizing mapreduce for
multicore architectures,” 2010.
[5] S. Jadoon, S. F. Solehria, S. Rehman, and H. Jan, “Design and analysis
of optimized selection sort algorithm,” International Journal of Electric
& Computer Sciences (IJECS-IJENS), vol. 11, no. 01, pp. 16–22, 2011.
[6] M. Khan, A. Khan, M. Khan, and S. Anwar, “A novel learning
method to classify data streams in the internet of things,” in Software
Engineering Conference (NSEC), 2014 National, Nov 2014, pp. 61–66.
[7] S. Jadoon, S. F. Solehria, and M. Qayum, “Optimized selection sort
algorithm is faster than insertion sort algorithm: a comparative study,”
International Journal of Electrical & Computer Sciences IJECS-IJENS,
vol. 11, no. 02, pp. 19–24, 2011.
[8] S. Sumathi, A. Prasad, and V. Suma, “Optimized heap sort technique
(ohs) to enhance the performance of the heap sort by using two-
swap method,” in Proceedings of the 3rd International Conference on
Frontiers of Intelligent Computing: Theory and Applications (FICTA)
2014. Springer, 2015, pp. 693–700.
[9] J. Singh and R. Singh, “Merge sort algorithm,” International Journal
of Research, vol. 1, no. 10, pp. 1203–1207, 2014.
[10] M. Zhou and H. Wang, “An efficient selection sorting algorithm for two-
dimensional arrays,” in Genetic and Evolutionary Computing (ICGEC),
2010 Fourth International Conference on. IEEE, 2010, pp. 853–855.
Fig. 3. Comparison of Efficient Selection Sort and Optimized Selection Sort [11] A. Chadha, R. Misal, T. Mokashi, and A. Chadha, “Arc sort: Enhanced
Algorithm for Two Dimensional Arrays and time efficient sorting algorithm,” arXiv preprint arXiv:1406.2262,
2014.
[12] W. Min, “Analysis on 2-element insertion sort algorithm,” in Computer
VI. C ONCLUSION Design and Applications (ICCDA), 2010 International Conference on,
vol. 1. IEEE, 2010, pp. V1–143.
Optimized Selection Sort Algorithm for two dimensional [13] M. F. Umar, E. U. Munir, S. A. Shad, and M. W. Nisar, “Enhancement
array belongs to the family of comparison based sorting algo- of selection, bubble and insertion sorting algorithm,” 2014.

2553
Authorized licensed use limited to: Ingrid Nurtanio. Downloaded on October 01,2020 at [Link] UTC from IEEE Xplore. Restrictions apply.