Sorting Algorithm in C-Bubble Sort and Selection Sort

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
1 2 3 4 5 6
42Swap77 12 101
77 42 35 5
Element
1 2 3 4 5 6
42 35Swap35
77 77 12 101 5
Element
1 2 3 4 5 6
42 35 12Swap12
77 77 101 5
Element
1 2 3 4 5 6
42 35 12 77 101 5
No need to swap
Element
1 2 3 4 5 6
42 35 12 77 5 Swap101
101 5
Element
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
• 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
• Finding the first smallest element by scanning the
remaining elements
1 2 3 4 5 6
77 42 35 12 101 5
Selection Sort
• 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
1 2 3 4 5 6
5 12 35 42 101 77
Selection Sort
1 2 3 4 5 6
5 12 35 42 101 77
Selection Sort
1 2 3 4 5 6
5 12 35 42 101 77
Selection Sort
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

Sorting Algorithm in C-Bubble Sort and Selection Sort

Uploaded by

Copyright:

Available Formats

Sorting Algorithm in C-Bubble Sort and Selection Sort

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Sorting Algorithm in C-Bubble Sort and Selection Sort

Uploaded by

Copyright:

Available Formats

SORTING ALGORITHM IN

 Example: Telephone directory.

 Procedure: In this technique, the two successive

• Traverse a collection of elements

Largest value correctly placed

Largest value correctly placed

• And if each time we bubble an element, we

• Then we repeat the “bubble up” process N – 1

 Procedure : In this technique after obtaining the smallest

You might also like