Sorting and Searching

Sorting Problem

A teacher maintains a list of data with two

fields namely student name and grade. She
wants to have the list rearranged according to
non-increasing order of the grade of the
students in order to pick up the names of the
students in the top 5 grades.

For example: The initial list is ((Ram, 9),

(Mohan, 10), (Selvam, 8),(Vikash, 9)).
The reordered list is ((Mohan, 10), (Ram, 9),
(Vikash, 9) (Selvam, 8))
 Sorting Definition

Rearranging the elements of the set such that

the values of the key are in a given order (an
increasing or a decreasing order).

Key?:
 Let us consider a set of entities, each entity having a
characteristics whose values are can be ordered (there
exists a relation of total ordering on the set of these values
a1<a2<…<an). This characteristics is called sorting key.

 Sometimes the entire entity is the sorting key (for instance

in the case of a set of numerical values).
 Sorting
Measures of cost:
 Comparisons
 Swaps

4
 Types of sorting

Internal sorting
 The elements of the set are stored on a random access

memory.
 Bubble sort
 Insertion sort
 Selection sort

External sorting
 when the data to be sorted are stored in files on hard

disks.
 Bubble sort

 Requires comparison of elements in adjacent position and

swapped if they are out of order.

 During the first pass, the largest element will be bubbled

and moved to the right most end and it forms the sorted
portion.

 During successive passes, next largest element will be

bubbled and find its place on the right side and thus
increasing the area of sorted portion.

 Hence, the comparisons are made for the elements in

unsorted portion and no need to go till the end of the array.
 Bubble
7
Sort

Compares neighboring pairs of

array elements, starting with
values [1] 36 the first array element, and
swaps neighbors whenever they
are not in correct order.
[2] 24
On each pass, this causes the
[3]
10 biggest element to “bubble up”
to its correct place in the array.
[4]
6
[ 5]
12
 Bubble Sort:
8
Pass One

values [1] 36 U
N
[2] 24 S
O
[3]
10 R
[4]
6 T
E
[ 5]
12 D
 Bubble Sort:
9
Pass One

values [1] 24 U
N
S
[2] 36 O
R
T
[3]
10 E
D
[4]
6
[ 5]
12
 Bubble Sort:
10
Pass One

values [1] 24 U
N
S
[2] 10 O
R
T
[3]
36 E
D
[4]
6
[ 5]
12
 Bubble Sort:
11
Pass One

values [1] 24 U
N
S
[2] 10 O
R
T
[3]
6 E
D
[4]
36
[ 5]
12
 Bubble Sort: 12End Pass One

values [1] 24 N
S
O
[2] 10 R
T
E
[3]
6 D

[4]
12
[ 5] SORTED
36
 Bubble Sort:
13
Pass Two

values [1] 24 N
S
O
[2] 10 R
T
E
[3]
6 D

[4]
12
[ 5] SORTED
36
 Bubble Sort:
14
Pass Two

values [1] 10 N
S
O
[2] 24 R
T
E
[3]
6 D

[4]
12
[ 5] SORTED
36
 Bubble Sort:
15
Pass Two

values [1] 10 N
S
O
[2] 6 R
T
E
[3]
24 D

[4]
12
[ 5] SORTED
36
 Bubble Sort: End
16
Pass Two

U
values [1] 10 N
S
O
[2] 6 R
T
E
[3]
12 D
[4]
24
SORTED
[ 5]
36
 Bubble Sort:17 Pass Three

U
values [1] 10 N
S
O
[2] 6 R
T
E
[3]
12 D
[4]
24
SORTED
[ 5]
36
 Bubble Sort:18 Pass Three

U
values [1] 6 N
S
O
[2] 10 R
T
E
[3]
12 D
[4]
24 SORTED
[ 5]
36
 Bubble Sort: 19End Pass Three

values [1] 6
UNSORTED
[2] 10
[3]
12 S
O
[4] R
24 T
E
[ 5] D
36
 Bubble Sort:
20
Pass Four

values [1] 6
UNSORTED
[2] 10
[3]
12 S
O
[4] R
24 T
E
[ 5] D
36
Bubble Sort: 21 End Pass Four

6
S
10 O
R
12 T
24 E
D
36
 Bubble Sort: Pseudo code

Bubblesort(Elem A[], int n)

//Sorts a given array by bubble sort
//Input: An array A[1..n] of orderable elements
//Output: Array A[1..n] sorted in non-decreasing
order

Begin
for i=1 to n-1
for j = 1 to n-i
if (A[j]> A[j+1]))
swap(A, j, j+1)
End 22
 Insertion Sort
23

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 pile on
the table
 Insertion Sort

Insertion sort keeps making the left side of the array

sorted until the whole array is sorted.

It sorts the values seen far away and repeatedly

inserts unseen values in the array into the left sorted
array.

It is the simplest of all sorting algorithms.

Although it has the same complexity as Bubble Sort,

the insertion sort is a little over twice as efficient as
the bubble sort.
 Insertion Sort

25

To insert 12, we need

to make room for it by
moving first 36 and
6 10 2 4 36 then 24.

12
 Insertion Sort

26

6 10 24 36

12
 Insertion Sort
27

6 10 24 3
6

12
 Insertion Sort
28

1 0 12 24
6 36
 Insertion
29
Sort

values [0] Insert, one by one, each

36 unsorted array element into its
[1] proper place.

24 On each pass, this causes the

[2] number of already sorted
elements to increase by one.
[3]
10
[4] 6
12
 Insertion Sort:
30
Pass One

values [0]
36 SORTED

[1]
U
24 N
[2] S
O
[3]
10 R
T
[4] 6 E
D

12
 Insertion Sort:
31
Pass Two

values [0]
24 SORTED
[1]

36 U
[2]
N

[3]
10 S
O
R
[4] 6 T
E
D
12
 Insertion Sort:
32
Pass Three

values [0] S
10 O
[1] R
24 T
E
[2] D

[3]
36
[4] 6
UNSORTED

12
 Insertion Sort:
33
Pass Four

values [0]
6 S
[1] O
R
10 T
[2] E
D
[3]
24
[4] 36
12 UNSORTED
 Insertion Sort:
34
Pass Five

values [0]
6
[1]
S
10 O
[2] R
T
[3]
12 E
D
[4] 24
36
 Insertion Sorting - Pseudocode
ALGORITHM InsertionSort(A[0..n − 1])
//Sorts a given array by insertion sort
//Input: An array A[0..n − 1] of n orderable elements
//Output: Array A[0..n − 1] sorted in non-decreasing
order
for i ←1 to n − 1 do
key ←A[i]
j ←i − 1
while j ≥ 0 and A[j ]> key do
A[j + 1]←A[j ]
j ←j − 1
A[j + 1]←key
 Insertion Sort - Summary
36

Advantages
 Good running time for “almost sorted” arrays (n)
Disadvantages
 (n2) running time in worst and average case
Selection Sort
37

Idea:
 Find the smallest element in the array
 Exchange it with the element in the first position
 Find the second smallest element and exchange it
with the element in the second position
 Continue until the array is sorted
Disadvantage:
 Running time depends only slightly on the amount of
order in the file
 Selection Sort

 Select minimum value as A[0].

 Store it in a variable min
 Keep on find whether there is minimum element
from index A[0]-A[4].
 If found make it a new min. Swap it with second
index A[0]
 Otherwise keep the same.
Goes on this way till the complete array got
sorted.
At this point when we see the array is divided
into 2 parts, one is sorted , and the other one is
unsorted
 Selection
39
Sort

values [0] Divides the array into two

36 parts: already sorted, and not
[1] yet sorted.

24 On each pass, finds the

[2] smallest of the unsorted
elements, and swaps it into its
[3]
10 correct place, thereby
increasing the number of
sorted elements by one.
[4] 6
12
 Selection Sort:
40
Pass One

values [0]
36 U
[1]
N
24 S
[2]
O
[3]
10 R
[4] 6 T
E
12 D
 Selection Sort:41 End Pass One

values [0]
6 SORTED

[1]
U
24 N
[2] S
O
[3]
10 R
T
[4] 36 E
D

12
 Selection Sort:
42
Pass Two

values [0]
6 SORTED

[1]
U
24 N
[2] S
O
[3]
10 R
T
[4] 36 E
D

12
 Selection Sort: End Pass Two
43

values [0]
6 SORTED
[1]

10
[2]
U
[3]
24 N
S
O
[4] 36 R
T
12 E
D
 Selection Sort: Pass Three
44

values [0]
6 SORTED
[1]

10
[2]
U
[3]
24 N
S
O
[4] 36 R
T
12 E
D
 Selection Sort: End Pass Three
45

values [0] S
6 O
[1] R
10 T
E
[2] D

[3]
12
[4] 36
UNSORTED

24
 Selection Sort: Pass Four
46

values [0] S
6 O
[1] R
10 T
E
[2] D

[3]
12
[4] 36
UNSORTED

24
 Selection Sort:47 End Pass Four

values [0]
6
[1] S
10 O
[2]
R
[3]
12 T
[4] 24 E
D
36
 Selection Sort: Pseudo code
ALGORITHM SelectionSort(A[0..n − 1])
//Sorts a given array by selection sort
//Input: An array A[0..n − 1] of orderable
elements
//Output: Array A[0..n − 1] sorted in
nondecreasing order
for i ←1 to n do
min←i
for j ←i + 1 to n do
if A[j ]<A[min] min←j
swap A[i] and A[min]
 Searching Problem

You want to meet a faculty of SCSE. The

faculty members are seated in their cabins.
However, you do not know the cabin no. of
the faculty. How do you find that faculty for
the first time?
 Searching - Definition

Searching is the algorithmic process of

finding a particular item in a collection of
items.
 A search typically answers
either True or False as to whether the item is
present.
 Sequential/ Linear Search
51

A sequential search of a list/array begins

at the beginning of the list/array and
continues until the item is found or the
entire list/array has been searched.
EXAMPLE
Linear Search Algorithm
 Search Algorithms
54array. The following expression
Suppose that there are n elements in the
gives the average number of comparisons:

It is known that

Therefore, the following expression gives the average number of comparisons

made by the sequential search in the successful case:
 Search Algorithms
55

Data Structures Using C++

 Searching Problem

Consider the same scenario of meeting a

faculty of SCSE. The faculty members are
seated in their cabins where cabin numbers
are in order. Now, you know the cabin no. of
the faculty you are searching for. How do you
find that faculty for the first time?
 57
Binary Search
O(log2 n)

A binary search looks for

an item in a list using a
divide-and-conquer strategy
 Binary58Search
 Binary search algorithm assumes that the
items in the array being searched are
sorted
 The algorithm begins at the middle of
the array in a binary search
 If the item for which we are searching is
less than the item in the middle, we
know that the item won’t be in the second
half of the array
 Once again we examine the “middle”
element
 The process continues with each
comparison cutting in half the portion of
Binary Search
59
Binary Search: middle element
60

left + right
mid =
2
Binary Search: Example
61
Binary Search Algorithm
Binary63Search
Binary64Search