SORTING ALGORITHM IN
C-
BUBBLE SORT AND
SELECTION SORT
Contents
Introduction to Sorting
Bubble Sort
Selection Sort
Advantages
Disadvantages
Summary
Introduction To Sorting
Sorting is a process in which records are arranged in
ascending or descending order.
Example: Telephone directory.
Sorting
• Sorting takes an unordered collection and makes it an
ordered one.
1 2 3 4 5 6
77 42 35 12 101 5
1 2 3 4 5 6
5 12 35 42 77 101
BUBBLE SORT
Oldest, most easiest, straightforward and simplistic
method of sorting data.
Procedure: In this technique, the two successive
elements A[i] and A[i+1] are exchanged whenever
A[i] >= A[i+1].
Bubble Sort Algorithm
for(i=1;i<n;i++)
{
for(j=0;j<n-i;j++)
{
if(a[j]>=a[j+1])
{
exchange (a[j],a[j+1])
}
}
}
BUBBLE SORT
“Bubbling Up" the Largest Element
• Traverse a collection of elements
– Move from the front to the end
– “Bubble” the largest value to the end using pair-
wise comparisons and swapping
1 2 3 4 5 6
77 42 35 12 101 5
"Bubbling Up" the Largest
Element
• Traverse a collection of elements
– Move from the front to the end
– “Bubble” the largest value to the end using pair-
wise comparisons and swapping
1 2 3 4 5 6
42Swap77 12 101
77 42 35 5
"Bubbling Up" the Largest
Element
• Traverse a collection of elements
– Move from the front to the end
– “Bubble” the largest value to the end using pair-
wise comparisons and swapping
1 2 3 4 5 6
42 35Swap35
77 77 12 101 5
"Bubbling Up" the Largest
Element
• Traverse a collection of elements
– Move from the front to the end
– “Bubble” the largest value to the end using pair-
wise comparisons and swapping
1 2 3 4 5 6
42 35 12Swap12
77 77 101 5
"Bubbling Up" the Largest
Element
• Traverse a collection of elements
– Move from the front to the end
– “Bubble” the largest value to the end using pair-
wise comparisons and swapping
1 2 3 4 5 6
42 35 12 77 101 5
No need to swap
"Bubbling Up" the Largest
Element
• Traverse a collection of elements
– Move from the front to the end
– “Bubble” the largest value to the end using pair-
wise comparisons and swapping
1 2 3 4 5 6
42 35 12 77 5 Swap101
101 5
"Bubbling Up" the Largest
Element
• Traverse a collection of elements
– Move from the front to the end
– “Bubble” the largest value to the end using pair-
wise comparisons and swapping
1 2 3 4 5 6
42 35 12 77 5 101
Largest value correctly placed
Items of Interest
• Notice that only the largest value is correctly
placed
• All other values are still out of order
• So we need to repeat this process
1 2 3 4 5 6
42 35 12 77 5 101
Largest value correctly placed
Repeat “Bubble Up” How Many
Times?
• If we have N elements…
• And if each time we bubble an element, we
place it in its correct location…
• Then we repeat the “bubble up” process N – 1
times.
“Bubbling” All the Elements
1 2 3 4 5 6
42 35 12 77 5 101
1 2 3 4 5 6
35 12 42 5 77 101
1 2 3 4 5 6
N-1
12 35 5 42 77 101
1 2 3 4 5 6
12 5 35 42 77 101
1 2 3 4 5 6
5 12 35 42 77 101
Advantages & Disadvantages of Bubble Sort
Advantages:
very simple
easy to program
can be implemented in a short amount of time
preferable when short lists are used.
Disadvantages:
runs slowly and hence it is not efficient.
Even if the elements are sorted, n-1 passes are
required to sort.
Selection Sort
Selection sort determines the minimum (or maximum) of
the list and swaps it with the element at the index where
it is supposed to be.
Procedure : In this technique after obtaining the smallest
element, it should be exchanged with the element in the
ith position.
temp = A[pos];
A[pos] = A[i];
A[i] = temp;
Selection Sort Algorithm
for(i=0;i<n-1;i++)
{
pos=i
for(j=i+1;j<n;j++)
{
if(a[j]<a[pos])
pos=j
}
temp=a[pos]
a[pos]=a[i]
a[i]=temp
}
Selection Sort
• Traverse a collection of elements
• It works by first finding the smallest element using a
linear scan and swapping it into the first position in
the list.
1 2 3 4 5 6
77 42 35 12 101 5
Selection Sort
• Traverse a collection of elements
• Finding the first smallest element by scanning the
remaining elements
1 2 3 4 5 6
77 42 35 12 101 5
Selection Sort
• Traverse a collection of elements
• Finding the second smallest element by scanning the
remaining elements, and so on....
1 2 3 4 5 6
5 42 35 12 101 77
Selection Sort
• Traverse a collection of elements
1 2 3 4 5 6
5 12 35 42 101 77
Selection Sort
• Traverse a collection of elements
1 2 3 4 5 6
5 12 35 42 101 77
Selection Sort
• Traverse a collection of elements
1 2 3 4 5 6
5 12 35 42 101 77
Selection Sort
• Traverse a collection of elements
1 2 3 4 5 6
5 12 35 42 77 101
Advantages & Disadvantages of Selection Sort
Advantages:
Better to use when sorting through arrays.
Performance is quicker than Bubble sort.
Notable for its programming
The simplest of sorting techniques and works very well for
small files
Disadvantages:
Quite inefficient for sorting large data volumes.
Spends most of its time trying to find the minimum
element in the "unsorted" part of the array.
Summary
The choice of a sort algorithm normally bases on
some properties of the data you have to sort.
Bubble sort is not a practical sorting algorithm
when n is large.
Selection sort algorithm is an easy-to-program,
but very inefficient sorting algorithm.
References
[1] Ashok N. Kamthane, Introduction to Data
Structures in C, Pearson Education, India, 2007
[2] A. M. Padma Reddy, Systematic Approach to Data
Structures Using C, 7th Edition, 2007
[3] Ellis Horowitz, Fundamentals of Computer
Algorithms, Universities Press, 2nd Edition, 2009
THANK YOU
