C-Programming -

Sorting
TOPICS TO BE COVERED
❖ Introduction to Sorting
❖ Bubble Sort
❖ Selection Sort
❖ Insertion Sort
Sorting
4 Sorting……
 A fundamental application for computers
Done to make finding data (searching)
faster
Many different algorithms for sorting
One of the difficulties with sorting is working
with a fixed size storage container (array)
i f resize, that is expensive (slow)
The "simple" sorts run in quadratic time O(N2)
bubble sort
selection sort
insertion sort
 Sorting……
To arrange a set of items in sequence.
It is estimated that 25~50% of all
computing power is used for sorting
activities.
Possible reasons:
Many applications require sorting;
Many applications perform sorting when
they don't have to;
Many applications use inefficient sorting
algorithms.
 Sorting Applications
 To prepare a list of student ID, names, and
scores in a table (sorted by ID or name) for
easy checking.
 To prepare a list of scores before letter
grade assignment.
 To produce a list of horses after a race
(sorted by the finishing times) for payoff
calculation.
 To prepare an originally unsorted array for
ordered binary searching.
Bubble Sort
 Bubble Sort……
Bubble sort examines the array from start
to finish, comparing elements as it goes.
Any time it finds a larger element before a smaller
element, it swaps the two.
 In this way, the larger elements are passed towards
the end.
The largest element of the array therefore "bubbles"
to the end of the array.
Then it repeats the process for the unsorted portion of
the array until the whole array is sorted.
 Bubble Sort……
Bubble sort works on the same general
principle as shaking a soft drink bottle.
Right after shaking, the contents are a mixture
of bubbles and soft drink, distributed randomly.
Because bubbles are lighter than the soft
drink, they rise to the surface, displacing the
soft drink downwards.
This is how bubble sort got its name, because
the smaller elements "float" to the top, while
the larger elements "sink" to the bottom.
"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
42 Swap4277
77 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
42 7735 ap35
77 12 101 5
S
w
"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 7712 Swap 12
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 1015 Swap 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

 An Animated Example

N 8 did_swap true

to_do 7

index

98 23 45 14 6 67 33 42

1 2 3 4 5 6 7 8
 An Animated Example

N 8 did_swap false

to_do 7

index 1

98 23 45 14 6 67 33 42

1 2 3 4 5 6 7 8
 An Animated Example

N 8 did_swap false

to_do 7

index 1

Swap

98 23 45 14 6 67 33 42

1 2 3 4 5 6 7 8
 An Animated Example

N 8 did_swap true

to_do 7

index 1

Swap

23 98 45 14 6 67 33 42

1 2 3 4 5 6 7 8
 An Animated Example

N 8 did_swap true

to_do 7

index 2

23 98 45 14 6 67 33 42

1 2 3 4 5 6 7 8
 An Animated Example

N 8 did_swap true

to_do 7

index 2

Swap

23 98 45 14 6 67 33 42

1 2 3 4 5 6 7 8
 An Animated Example

N 8 did_swap true

to_do 7

index 2

Swap

23 45 98 14 6 67 33 42

1 2 3 4 5 6 7 8
 An Animated Example

N 8 did_swap true

to_do 7

index 3

23 45 98 14 6 67 33 42

1 2 3 4 5 6 7 8
 An Animated Example

N 8 did_swap true

to_do 7

index 3

Swap

23 45 98 14 6 67 33 42

1 2 3 4 5 6 7 8
 An Animated Example

N 8 did_swap true

to_do 7

index 3

Swap

23 45 14 98 6 67 33 42

1 2 3 4 5 6 7 8
 An Animated Example

N 8 did_swap true

to_do 7

index 4

23 45 14 98 6 67 33 42

1 2 3 4 5 6 7 8
 An Animated Example

N 8 did_swap true

to_do 7

index 4

Swap

23 45 14 98 6 67 33 42

1 2 3 4 5 6 7 8
 An Animated Example

N 8 did_swap true

to_do 7

index 4

Swap

23 45 14 6 98 67 33 42

1 2 3 4 5 6 7 8
 An Animated Example

N 8 did_swap true

to_do 7

index 5

23 45 14 6 98 67 33 42

1 2 3 4 5 6 7 8
 An Animated Example

N 8 did_swap true

to_do 7

index 5

Swap

23 45 14 6 98 67 33 42

1 2 3 4 5 6 7 8
 An Animated Example

N 8 did_swap true

to_do 7

index 5

Swap

23 45 14 6 67 98 33 42

1 2 3 4 5 6 7 8
 An Animated Example

N 8 did_swap true

to_do 7

index 6

23 45 14 6 67 98 33 42

1 2 3 4 5 6 7 8
 An Animated Example

N 8 did_swap true

to_do 7

index 6

Swap

23 45 14 6 67 98 33 42

1 2 3 4 5 6 7 8
 An Animated Example

N 8 did_swap true

to_do 7

index 6

Swap

23 45 14 6 67 33 98 42

1 2 3 4 5 6 7 8
 An Animated Example

N 8 did_swap true

to_do 7

index 7

23 45 14 6 67 33 98 42

1 2 3 4 5 6 7 8
 An Animated Example

N 8 did_swap true

to_do 7

index 7

Swap

23 45 14 6 67 33 98 42

1 2 3 4 5 6 7 8
 An Animated Example

N 8 did_swap true

to_do 7

index 7

Swap

23 45 14 6 67 33 42 98

1 2 3 4 5 6 7 8
 After First Pass of Outer Loop

N 8 did_swap true

to_do 7

index 8 Finished first “Bubble Up”

23 45 14 6 67 33 42 98

1 2 3 4 5 6 7 8
 The Second “Bubble Up”

N 8 did_swap false

to_do 6

index 1

23 45 14 6 67 33 42 98

1 2 3 4 5 6 7 8
 The Second “Bubble Up”

N 8 did_swap false

to_do 6

index 1

No Swap

23 45 14 6 67 33 42 98

1 2 3 4 5 6 7 8
 The Second “Bubble Up”

N 8 did_swap false

to_do 6

index 2

23 45 14 6 67 33 42 98

1 2 3 4 5 6 7 8
 The Second “Bubble Up”

N 8 did_swap false

to_do 6

index 2

Swap

23 45 14 6 67 33 42 98

1 2 3 4 5 6 7 8
 The Second “Bubble Up”

N 8 did_swap true

to_do 6

index 2

Swap

23 14 45 6 67 33 42 98

1 2 3 4 5 6 7 8
 The Second “Bubble Up”

N 8 did_swap true

to_do 6

index 3

23 14 45 6 67 33 42 98

1 2 3 4 5 6 7 8
 The Second “Bubble Up”

N 8 did_swap true

to_do 6

index 3

Swap

23 14 45 6 67 33 42 98

1 2 3 4 5 6 7 8
 The Second “Bubble Up”

N 8 did_swap true

to_do 6

index 3

Swap

23 14 6 45 67 33 42 98

1 2 3 4 5 6 7 8
 The Second “Bubble Up”

N 8 did_swap true

to_do 6

index 4

23 14 6 45 67 33 42 98

1 2 3 4 5 6 7 8
 The Second “Bubble Up”

N 8 did_swap true

to_do 6

index 4

No Swap

23 14 6 45 67 33 42 98

1 2 3 4 5 6 7 8
 The Second “Bubble Up”

N 8 did_swap true

to_do 6

index 5

23 14 6 45 67 33 42 98

1 2 3 4 5 6 7 8
 The Second “Bubble Up”

N 8 did_swap true

to_do 6

index 5

Swap

23 14 6 45 67 33 42 98

1 2 3 4 5 6 7 8
 The Second “Bubble Up”

N 8 did_swap true

to_do 6

index 5

Swap

23 14 6 45 33 67 42 98

1 2 3 4 5 6 7 8
 The Second “Bubble Up”

N 8 did_swap true

to_do 6

index 6

23 14 6 45 33 67 42 98

1 2 3 4 5 6 7 8
 The Second “Bubble Up”

N 8 did_swap true

to_do 6

index 6

Swap

23 14 6 45 33 67 42 98

1 2 3 4 5 6 7 8
 The Second “Bubble Up”

N 8 did_swap true

to_do 6

index 6

Swap

23 14 6 45 33 42 67 98

1 2 3 4 5 6 7 8
 After Second Pass of Outer Loop

N 8 did_swap true

to_do 6

index 7 Finished second “Bubble Up”

23 14 6 45 33 42 67 98

1 2 3 4 5 6 7 8
 The Third “Bubble Up”

N 8 did_swap false

to_do 5

index 1

23 14 6 45 33 42 67 98

1 2 3 4 5 6 7 8
 The Third “Bubble Up”

N 8 did_swap false

to_do 5

index 1

Swap

23 14 6 45 33 42 67 98

1 2 3 4 5 6 7 8
 The Third “Bubble Up”

N 8 did_swap true

to_do 5

index 1

Swap

14 23 6 45 33 42 67 98

1 2 3 4 5 6 7 8
 The Third “Bubble Up”

N 8 did_swap true

to_do 5

index 2

14 23 6 45 33 42 67 98

1 2 3 4 5 6 7 8
 The Third “Bubble Up”

N 8 did_swap true

to_do 5

index 2

Swap

14 23 6 45 33 42 67 98

1 2 3 4 5 6 7 8
 The Third “Bubble Up”

N 8 did_swap true

to_do 5

index 2

Swap

14 6 23 45 33 42 67 98

1 2 3 4 5 6 7 8
 The Third “Bubble Up”

N 8 did_swap true

to_do 5

index 3

14 6 23 45 33 42 67 98

1 2 3 4 5 6 7 8
 The Third “Bubble Up”

N 8 did_swap true

to_do 5

index 3

No Swap

14 6 23 45 33 42 67 98

1 2 3 4 5 6 7 8
 The Third “Bubble Up”

N 8 did_swap true

to_do 5

index 4

14 6 23 45 33 42 67 98

1 2 3 4 5 6 7 8
 The Third “Bubble Up”

N 8 did_swap true

to_do 5

index 4

Swap

14 6 23 45 33 42 67 98

1 2 3 4 5 6 7 8
 The Third “Bubble Up”

N 8 did_swap true

to_do 5

index 4

Swap

14 6 23 33 45 42 67 98

1 2 3 4 5 6 7 8
 The Third “Bubble Up”

N 8 did_swap true

to_do 5

index 5

14 6 23 33 45 42 67 98

1 2 3 4 5 6 7 8
 The Third “Bubble Up”

N 8 did_swap true

to_do 5

index 5

Swap

14 6 23 33 45 42 67 98

1 2 3 4 5 6 7 8
 The Third “Bubble Up”

N 8 did_swap true

to_do 5

index 5

Swap

14 6 23 33 42 45 67 98

1 2 3 4 5 6 7 8
 After Third Pass of Outer Loop

N 8 did_swap true

to_do 5

index 6 Finished third “Bubble Up”

14 6 23 33 42 45 67 98

1 2 3 4 5 6 7 8
 The Fourth “Bubble Up”

N 8 did_swap false

to_do 4

index 1

14 6 23 33 42 45 67 98

1 2 3 4 5 6 7 8
 The Fourth “Bubble Up”

N 8 did_swap false

to_do 4

index 1

Swap

14 6 23 33 42 45 67 98

1 2 3 4 5 6 7 8
 The Fourth “Bubble Up”

N 8 did_swap true

to_do 4

index 1

Swap

6 14 23 33 42 45 67 98

1 2 3 4 5 6 7 8
 The Fourth “Bubble Up”

N 8 did_swap true

to_do 4

index 2

6 14 23 33 42 45 67 98

1 2 3 4 5 6 7 8
 The Fourth “Bubble Up”

N 8 did_swap true

to_do 4

index 2

No Swap

6 14 23 33 42 45 67 98

1 2 3 4 5 6 7 8
 The Fourth “Bubble Up”

N 8 did_swap true

to_do 4

index 3

6 14 23 33 42 45 67 98

1 2 3 4 5 6 7 8
 The Fourth “Bubble Up”

N 8 did_swap true

to_do 4

index 3

No Swap

6 14 23 33 42 45 67 98

1 2 3 4 5 6 7 8
 The Fourth “Bubble Up”

N 8 did_swap true

to_do 4

index 4

6 14 23 33 42 45 67 98

1 2 3 4 5 6 7 8
 The Fourth “Bubble Up”

N 8 did_swap true

to_do 4

index 4

No Swap

6 14 23 33 42 45 67 98

1 2 3 4 5 6 7 8
 After Fourth Pass of Outer Loop

N 8 did_swap true

to_do 4

index 5 Finished fourth “Bubble Up”

6 14 23 33 42 45 67 98

1 2 3 4 5 6 7 8
 The Fifth “Bubble Up”

N 8 did_swap false

to_do 3

index 1

6 14 23 33 42 45 67 98

1 2 3 4 5 6 7 8
 The Fifth “Bubble Up”

N 8 did_swap false

to_do 3

index 1

No Swap

6 14 23 33 42 45 67 98

1 2 3 4 5 6 7 8
 The Fifth “Bubble Up”

N 8 did_swap false

to_do 3

index 2

6 14 23 33 42 45 67 98

1 2 3 4 5 6 7 8
 The Fifth “Bubble Up”

N 8 did_swap false

to_do 3

index 2

No Swap

6 14 23 33 42 45 67 98

1 2 3 4 5 6 7 8
 The Fifth “Bubble Up”

N 8 did_swap false

to_do 3

index 3

6 14 23 33 42 45 67 98

1 2 3 4 5 6 7 8
 The Fifth “Bubble Up”

N 8 did_swap false

to_do 3

index 3

No Swap

6 14 23 33 42 45 67 98

1 2 3 4 5 6 7 8
 After Fifth Pass of Outer Loop

N 8 did_swap false

to_do 3

index 4 Finished fifth “Bubble Up”

6 14 23 33 42 45 67 98

1 2 3 4 5 6 7 8
 Finished “Early”

N 8 did_swap false

to_do 3
We didn’t do any swapping,
index 4 so all of the other elements
must be correctly placed.

We can “skip” the last two

passes of the outer loop.

6 14 23 33 42 45 67 98

1 2 3 4 5 6 7 8
Example:
void bubble_sort(int *arr , int size)
{
int a , b , temp ;
bool flag;
for(a = 0 ; a < size ; a++)
{
flag = false;
for(b = 0 ; b < =size -2 –a ; b++)
if(arr[b] > arr[b+1])
{temp = arr[b] ; arr[b] = arr[b+1] ; arr[b+1] = temp ; flag = true;}
if(flag == false) break;
}
}
void main(void)
{
int y[10];
for(int k = 0 ; k <= 9 ; k++)
y[k] = rand() % 100 ;
bubble_sort(y , 10);
for(int k = 0 ; k <= 9 ; k++)
cout << y[k] << "\t" ;
}
Selection Sort……
 Selection Sort……
Idea:
Find the largest element in the array
Exchange it with the element in the
rightmost position
Find the second largest element and
exchange it with the element in the
second rightmost position
Continue until the array is sorted
Before sorting 14 2 10 5 1 3 17 7

After pass 1 14 2 10 5 1 3 7 17

After pass 2 7 2 10 5 1 3 14 17

After pass 3 7 2 3 5 1 10 14 17

After pass 4 1 2 3 5 7 10 14 17
Selection Sort

5 1 3 4 6 2

Comparison

Data Movement

Sorted
Selection Sort

5 1 3 4 6 2

Comparison

Data Movement

Sorted
Selection Sort

5 1 3 4 6 2

Comparison

Data Movement

Sorted
Selection Sort

5 1 3 4 6 2

Comparison

Data Movement

Sorted
Selection Sort

5 1 3 4 6 2

Comparison

Data Movement

Sorted
Selection Sort

5 1 3 4 6 2

Comparison

Data Movement

Sorted
Selection Sort

5 1 3 4 6 2

Comparison

Data Movement

Sorted
Selection Sort

5 1 3 4 6 2
Largest

Comparison

Data Movement

Sorted
Selection Sort

5 1 3 4 2 6

Comparison

Data Movement

Sorted
Selection Sort

5 1 3 4 2 6

Comparison

Data Movement

Sorted
Selection Sort

5 1 3 4 2 6

Comparison

Data Movement

Sorted
Selection Sort

5 1 3 4 2 6

Comparison

Data Movement

Sorted
Selection Sort

5 1 3 4 2 6

Comparison

Data Movement

Sorted
Selection Sort

5 1 3 4 2 6

Comparison

Data Movement

Sorted
Selection Sort

5 1 3 4 2 6

Comparison

Data Movement

Sorted
Selection Sort

5 1 3 4 2 6
Largest

Comparison

Data Movement

Sorted
Selection Sort

2 1 3 4 5 6

Comparison

Data Movement

Sorted
Selection Sort

2 1 3 4 5 6

Comparison

Data Movement

Sorted
Selection Sort

2 1 3 4 5 6

Comparison

Data Movement

Sorted
Selection Sort

2 1 3 4 5 6

Comparison

Data Movement

Sorted
Selection Sort

2 1 3 4 5 6

Comparison

Data Movement

Sorted
Selection Sort

2 1 3 4 5 6

Comparison

Data Movement

Sorted
Selection Sort

2 1 3 4 5 6
Largest

Comparison

Data Movement

Sorted
Selection Sort

2 1 3 4 5 6

Comparison

Data Movement

Sorted
Selection Sort

2 1 3 4 5 6

Comparison

Data Movement

Sorted
Selection Sort

2 1 3 4 5 6

Comparison

Data Movement

Sorted
Selection Sort

2 1 3 4 5 6

Comparison

Data Movement

Sorted
Selection Sort

2 1 3 4 5 6

Comparison

Data Movement

Sorted
Selection Sort

2 1 3 4 5 6
Largest

Comparison

Data Movement

Sorted
Selection Sort

2 1 3 4 5 6

Comparison

Data Movement

Sorted
Selection Sort

2 1 3 4 5 6

Comparison

Data Movement

Sorted
Selection Sort

2 1 3 4 5 6

Comparison

Data Movement

Sorted
Selection Sort

2 1 3 4 5 6

Comparison

Data Movement

Sorted
Selection Sort

2 1 3 4 5 6
Largest

Comparison

Data Movement

Sorted
Selection Sort

1 2 3 4 5 6

Comparison

Data Movement

Sorted
Selection Sort

1 2 3 4 5 6
DONE!
Comparison

Data Movement

Sorted
void selection_sort(int *arr , int size)
{
int temp , minloc;
for(int first = 0 ; first <= size - 2 ; first++)
{
minloc = first;
for(int k = first+1 ; k <= size-1 ; k++)
if(arr[minloc] > arr[k]) minloc = k ;

temp = arr[first] ;
arr[first] = arr[minloc] ;
arr[minloc] = temp ;
}
}
void main(void)
{
int y[10];
for(int k = 0 ; k <= 9 ; k++)
y[k] = rand() % 100 ;
selection_sort(y , 10);
for(int k = 0 ; k <= 9 ; k++)
cout << y[k] << "\t" ;
}
Insertion Sort……
Insertion Sort……
 Idea: like sorting a hand of playing cards
Start with an empty left hand and the cards facing
down on the table.
Remove one card at a time from the table, and insert
it into the correct position in the left hand
compare it with each of the cards already in the
hand, from right to left
The cards held in the left hand are sorted
these cards were originally the top cards of the
134
pile on the table
Insertion Sort

To insert 12, we need to

make room for it by
moving first 36 and then 24.

135
Insertion Sort

136
Insertion Sort

137
Insertion Sort
input array

5 2 4 6 1 3

at each iteration, the array is divided in two sub-arrays:

left sub-array right sub-array

sorted unsorted

138
Insertion Sort

139
void insertion_sort(int *arr , int size)
{
int a , b , temp ;
for(a = 1 ; a <= size -1 ; a++)
{
temp = arr[a];
for(b = a-1 ; b >= 0 ; b--)
if(arr[b] > temp) arr[b+1] = arr[b];
else break;
arr[b+1] = temp;
}
}
void main(void)
{
int y[10];
for(int k = 0 ; k <= 9 ; k++)
y[k] = rand() % 100 ;
insertion_sort(y , 10);
for(int k = 0 ; k <= 9 ; k++)
cout << y[k] << "\t" ;
}
THANK
FOR
YOU LISTENIN