2010 International Forum on Information Technology and Applications
Analysis on Bubble Sort Algorithm Optimization
Wang Min
Computer Science Department, Weinan Teachers University, Shanxi Weinan 714000, China
[email protected]
ABSTRACT: Based on the analysis of the traditional bubble sort
algorithm, this paper proposes two bidirectional bubble sort II. BUBBLE SORT ALGORITHM
algorithm design ideas. After giving C language description of The bubble sort method, known as the adjacent
the three algorithms, the paper tests the new algorithms, analyzes comparison, is a simple internal exchange sort method. It is
comparatively the time complexity and space complexity of the the process during which the sequence to be sorted will
three algorithms, and summarizes such a conclusion that the
gradually be sorted into an ordered sequence through
first new algorithm has the same average time complexity and
space complexity as the original algorithm, while the second is
exchange of the adjacent data elements for each other[1,2].
time efficient than the original one, and thus truly reaches the The following assumes that all record keywords will be
optimization purpose. sorted in accordance with the non-decreasing order.
The sort methods used by the sequence of records can be
KEYWORDS: bubble sort; bidirectional bubble sort; time divided into three kinds: vector sort, (list) table sort and
complexity; space complexity address sort, according to the different storage ways[ 4]. This
paper chooses the first method, that is, a set of records to be
I. INTRODUCTION sorted are stored in the address of a contiguous group of
memory cells. The type of records to be sorted can be
Search operations are often needed in computer data defined in C as follows:
processing. In order to use more efficient search method, it is typedef struct{
often needed that the data to be processed in an ordered KeyType key;
arrangement according to the keywords. Thus sort operation OtherType otherinfo;
is one of the basic operations in computer programming[1]. } RecordType;
An n records sequence {R 1 ,R 2 , Ă ,R n }, whoes
corresponding sequence of keywords is {K 1 , K 2 , ...,K n }, is A. Algorithm Design Ideas
required to be sorted to identify a permutation p1, p2,..., pn The basic design idea of the algorithm is as follows: All
of the current subscript sequence 1,2, ...,n, so that the the trips to sort the table begin with the first record keyword
appropriate keywords meet the non-decreasing (or non- of the disordered table, compare sequentially adjacent record
increasing) relationship, that is K p1 İK p2 İĂİK pn , in order keywords, exchange each other where there is reverse, and
to get an ordered record sequence by their keywords[1,2,3]. end the trip after the last two record keywords are compared.
Such process is known as sort. So that the i-th sort trip has n-i comparisons at the most. At
As the number of records to be sorted is different, which this point the maximum keyword of the disordered table is
makes the memories involved in sort processes are different, changed to the end of the disordered table, that is, its final
the sort process can be divided into two categories: One is location, and an ordered table is formed in the rear of the
the internal sort, referring to the process during which the disordered table; Then followed by the next trip bubble sort.
records to be sorted are stored in the computer random There are theoretically n-1 sort trips when there are n
access memory; the other is the external sort, referring to the records to be sorted, but the actual times of sort trips may be
process during which the external memories are still needed less than the theoretical one through determining whether
to be visited for the number of records to be sorted is too any exchanges occur between adjacent record keywords of
large for the memory to accommodate to[2,4]. all the comparisons in the last sort trip before the next one
This paper presents and analyzes the bubble sort begins. If there is no exchange occurs during the last sort trip,
algorithm, one of the existing internal sort algorithms, the entire sort process will be ended. In this way, the real
proposes two kinds of bidirectional bubble sort algorithm number of comparisons may be less than the theoretical
design ideas, and gives all the algorithms described in C. value.
After analyzing comparatively the time complexity and
space complexity of the three algorithms, the paper B. Algorithm Description in C
summarizes that the first algorithm design idea has the same The labeled variable exchanged can be defined and used
average time complexity and space complexity as the to determine whether the exchange occurs during the last sort
original algorithm, while the second one is time efficient trip before the next one begins. At the beginning of the sort
than the original one, and thus truly reaches the optimization trip, exchanged is set firstly to be 0, but changed to 1 once
purpose. the exchange occurs during comparisons. The algorithm can
be described below in C based on the defined type
RecordType (where n is the number of records to be sorted):
978-0-7695-4115-0/10 $26.00 © 2010 IEEE 208
DOI 10.1109/IFITA.2010.9
Authorized licensed use limited to: National University of Modern Languages. Downloaded on October 01,2025 at 07:59:10 UTC from IEEE Xplore. Restrictions apply.
void BubbleSort(RecordType r[ ], int n) from 1 to n/2, but the real times of sort trips may be less than
{ int i, j, exchanged=1; the theoretical one through determining whether any
// i and j are used to indicate the vector subscripts of the records. exchanges occur in the latest sort trip before the next one
RecordType x; // x is the intermediate variable in exchange begins. If there is no exchange occurs during the latest sort
for(i=1; i<=n-1&&exchanged; i++) trip, the entire sort process will be ended. In this way, the
{ exchanged=0; actual number of comparisons may be less than the
theoretical value.
for(j=1; j<=n-i; j++)
if(r[j].key>r[j+1].key) B. The Description in C of First Algorithm
{ x=r[j]; The Initial condition of the algorithm is the same as the
r[j]=r[j+1]; previous algorithm, and the algorithm described in C based
r[j+1]=x; on the defined type RecordType is as follow:
exchanged=1; } void BubbleSort_1(RecordType r[ ], int n)
} { int i, j, k, exchanged=1;
} // i, j and k are used to indicate the vector subscripts of the records.
Zero is the starting number of array subscript in C, so the RecordType x; // x is the intermediate variable in exchange
initial condition of the algorithm described before is that the for(i=1; i<=n/2&&exchanged; i++)
0 subscript unit of the array r [ ] is idle, and the records to be { exchanged=0;
sorted are kept in the 1 ~ n subscript unit. for(j=i;j<=n-i;j++)
if(r[j].key>r[j+1].key)
III. BIDIRECTIONAL BUBBLE SORT ALGORITHM
{ x=r[j];
The original bubble sort algorithm is one-way r[j]=r[j+1];
comparison of two adjacent records from the head to tail of r[j+1]=x;
the disordered part in each sort trip. Of course, the direction exchanged=1; }
can also be the contrary, one-way comparison from the tail to
for(k=n-i;k>i;k--)
head of the disordered part. This will form gradually an
if(r[k].key<r[k-1].key)
ordered table at the head of the disordered table, and the
basic idea of the algorithm has no difference with the { x=r[k];
foregoing. You can also consider an alternative sort design r[k]=r[k-1];
concept, the comparison of each sort trip is a bidirectional r[k-1]=x;
comparison of two adjacent records, that is bidirectional exchanged=1; }
bubble sort. The following will describe and analyze two }
kinds of bidirectional bubble sort algorithm design ideas. }
A. The Design Idea of First Algorithm C. The Design Idea of Second Algorithm
The basic design idea of the algorithm is as follows: The basic design idea of the algorithm is as follows:
The i-th sort trip, for example, only for the comparison to The i-th sort trip only for the comparisons to the
the disordered part of the table, and in accordance with the disordered part of the table, subscript range i ~ n-i. In the i-th
following two steps: sort trip, for example, the two-way comparisons between
First, compare sequentially adjacent record keywords adjacent keywords execute concurrently. First, compare the i
from head to tail in the disordered table, exchange each other and i+1 record keywords, exchange them if reverse. Second,
where there is reverse, and end the trip after the last two compare the n-i+1 and n-i record keywords, exchange them
record keywords of the disordered table are compared. After if reverse. As the two-way comparison execute concurrently
n-2i+1 comparisons at the most has done, the maximum in each sort trip, the maximum keyword is changed to the
keyword is changed to the end of the disordered table, that is, end of the disordered table, and the minimum is changed to
its final location, and an ordered table is formed in the rear of the head after one sort trip, so the ordered parts are formed
the disordered table. gradually at both ends of the table to be sorted[ 7].
Second, compare sequentially adjacent record keywords Similarly, n records to be sorted need theoretically n/2
from tail to head in the disordered table, exchange each other sort trips, but the actual times of sort trips may be less than
where there is reverse, and end the trip after the 1st two the theoretical one through determining whether any
record keywords of the disordered table are compared. After exchanges occur in the latest sort trip before the next one
n-2i comparisons at the most has done, the minimum begins. If not, the entire sort process will be ended. In this
keyword is changed to the head of the disordered table, that way, the real number of comparisons may be less than the
is, its final location, and an ordered table is formed in the theoretical value.
front part of the disordered table[5].
After the steps above, the i-th sort trip is completed, and
then sort for the next trip.
There are theoretically n/2 sort trips when there are n
records to be sorted[6], that is variable i has the value range
209
Authorized licensed use limited to: National University of Modern Languages. Downloaded on October 01,2025 at 07:59:10 UTC from IEEE Xplore. Restrictions apply.
D. The Description in C of Second Algorithm
The Initial condition of the algorithm is the same as the
previous algorithms, and the algorithm described in C based
on the defined type RecordType is as follow:
void BubbleSort_2(RecordType r[ ], int n)
{ int i, j, exchange=1;
// i and j are used to indicate the vector subscripts of the records.
RecordType x; // x is the intermediate variable in exchange
for(i=1; i<=n/2&&exchange; i++) Figure 2. Example of the running result of BubbleSort_2( ) algorithm in
{ exchange=0; VC + + 6.0 environment
for(j=i;j<=n-i;j++)
{ if(r[j].key>r[j+1].key) A. Analysis on Time Complexity and Space Complexity of
{ x=r[j]; the Three Algorithms
r[j]=r[j+1];
Taking a look at the original bubble sort algorithm in C
r[j+1]=x; language description, you can see that the core statements in
exchange=1; } function BubbleSort() is a nested double loop components.
if(r[n-j+1].key<r[n-j].key) The basic loop statement (if statement) perform theoretically
{ x=r[n-j]; a total of n-1+n-2+...+1=n(n-1)/2 times[8], which is the total
r[n-j]=r[n-j+1]; number of keywords comparisons. Regarding the records
r[n-j+1]=x; number n as the problem scale, and according to this
exchange=1; } simplification of the given conditions (the record
} membership is relatively simple), you can determine that the
} mobile number of keywords (when the keywords is in
reverse ) is three times at the most than the number of
}
comparisons. Thus the algorithm average time complexity
IV. TEST AND ANALYSIS OF ALGORITHMS can be measured by the number of keywords comparisons,
that is T(n)=O(n2). In the best conditions, when the initial
To verify the correctness of the algorithm describing records are ordered, it needs only n-1 comparisons to
functions BubbleSort(), BubbleSort_1() and BubbleSort_2(), complete the entire sort process; In addition to the vector
the output function Print() and the calling function main() space used by the record elements, the function also
are added to ensure the integrity of the programs, so as to test introduces four variable auxiliary spaces i, j, x, and
them in Visual C ++ 6.0 environment. Where the function exchanged, and its space complexity is constant order, that is
Print() outputs sequentially subscript 1~n units of all record S(n)=O(1).
keywords; The function main() include initializing records From the algorithm description in C of the first design
vector, outputting record keywords by calling the function idea of the bidirectional bubble sort, you can see that the
Print(), calling sort operation, and outputting the record function BubbleSort_1() also uses a nested double loop
keywords after sorting and so on. At the same time, the components. As the loop body of the outer loop consists of
KeyType is set to the int type, and the RecordType remain two cycling steps execute sequentially, the number of the
only the keyword member key for simplifying the input and comparisons in two if statements totals theoretical to n-1+ n-
the output. 2+...+1=n(n-1)/2. The average time complexity of this
The results, running in VC environment by entering a algorithm is as same as that of the original bubble sort
number of different keywords, are all correct. As shown in algorithm, that is T(n)=O(n2). In the best conditions, when
Figure 1 and Figure 2 respectively, they are running result the initial records are ordered, it needs n-1+n-2=2n-3
samples of the two improved algorithm programs in C comparisons with two nested loop steps to complete the
running in VC ++ 6.0 environment. entire sort process; In addition to the vector space used by
the record elements, the function also introduces five
auxiliary variable spaces i, j, k, x, and exchanged. Although
it needs one more auxiliary variable space(k) than that of the
function BubbleSort(), its space complexity is still constant
order, that is S(n)=O(1). Thus the algorithm has the same
average time complexity and space complexity as the
original bubble sort algorithm, and only when the records to
be sorted ordered by keywords, its time efficiency is lower
than the original one.
Figure 1. Example of the running result of BubbleSort_1( ) algorithm in From the algorithm description in C of the second design
VC ++ 6.0 environment
idea of the bidirectional bubble sort, you can see that the
function BubbleSort_2() also uses a nested double loop
210
Authorized licensed use limited to: National University of Modern Languages. Downloaded on October 01,2025 at 07:59:10 UTC from IEEE Xplore. Restrictions apply.
components. Different from the first design idea, the inner efficient than the original one, and thus truly reaches the
loop in this function includes only two if statements. The optimization purpose.
number of the comparisons in two if statements in each trip This paper aims to give an alternative analysis idea of
totals theoretically to 2(n-2i+1) times at the most, and bubble sort algorithm through giving a detailed analysis of
therefore the whole number of comparisons totals theoretical two new algorithms design ideas, so as to playing a guiding
to 2((n-1)+(n-3)+(n-5)+ Ă +1)=n2/4. Obviously, compared role in teaching the relevant chapters in “Data Structure”
with the original algorithm, the total number of comparisons curriculum.
in this algorithm is reduced, but the algorithm average time
complexity is still T(n)=O(n2). In the best conditions, when ACKNOWLEDGMENT
the initial records are ordered, it needs 2(n-1) comparisons; This work is supported by Graduate Special Fund of
The function occupies the same amount of space as that of Weinan Teachers University (No. 10YKZ057).
the function BubbleSort(), its space complexity is still
S(n)=O(1). REFERENCES
V. CONCLUSION [1] GENG Guohua. Data Structure—C Language description[M]. Xi'an:
Bidirectional bubble sort algorithm is an improved Xi'an Electronic Science and Technology University Press, 2006.228-
235.
algorithm design idea proposed based on the original bubble
[2] XU Xiaokai. Simple Data Structure Tutorial[M].Beijing: Tsinghua
sort algorithm. In this paper, two bidirectional bubble sort University Press, 1995.193-205.
algorithm design ideas are discussed, and the algorithm
[3] XU Xusong. Introduction to Data Structures and Algorithms[M].
descriptions in C has passed through VC ++ 6.0 environment Beijing: Electronics Industry Press, 1996.162-170.
to test their accuracy. [4] YAN Weimin,WU Weimin. Data Structures[M].Beijing: Tsinghua
After analyzing comparatively the time complexity and University Press, 2000.263-264.
space complexity of the three algorithms, this paper drawed [5] LAN Chao. Optimizing of Bubble Sort Algorithm[J]. O.I.
the following conclusions ultimately: Automation, 2006,25(12): 50-52.
The bidirectional bubble sort algorithm using the first [6] CUI Jinping, WANG Conghua, XUN Zhengliang, GUO Xiaochun,
design idea has the same average time complexity and space WANG Xia. Data Structure—C Language description[M]. Beijing:
complexity as the original bubble sort algorithm, but has China Railway Publishing House, 2008. 317-318.
nearly twice comparison times than that of the original one if [7] XU Shanxiang, GAO Jun, JI Yuling. The Improvement of Bubble
the initial records are ordered by keywords. In addition, it Sort Algorithm[J]. Journal of Heilongjiang Institute of Science &
Technology, 2002,12(1).
introduces one more auxiliary variable space than that of the
[8] CHEN Yuanchun, ZHANG Liang, WANG Yong. Utility-Based Data
original algorithm. Structure[M]. Beijing: China Railway Publishing House, 2009,239-
The algorithm using the second design idea has the same 241.
space complexity as the original algorithm, but it is time
211
Authorized licensed use limited to: National University of Modern Languages. Downloaded on October 01,2025 at 07:59:10 UTC from IEEE Xplore. Restrictions apply.
