1501118

Data Structures
and Algorithms

Chapter 8:
Basic Search
and Sorting

2nd semester AY2024

School of Information
Technology

Copyright 2025 School of IT

 Outline 1
• Basic Search
– Linear Search
– Binary Search
• Why sorting?
• How to implement
sorting.
• How to choose the
algorithm.
 Outline 2
• Sorting algorithms
– Bubble Sort
– Selection Sort
– Insertion Sort
– Merge Sort
– Quick Sort
• Comparison
• Summary
 Is Searching Necessary?
• We develop data structures to keep data
• Searching is a necessary process to get
specific data from data structures
• Well-known example: Web search engine

Image source: http://searchengineprofiling.com/search-engine-marketing/

 Basic Search
• Given a set of data in a data structure such
as an array, how to find a specific element?
• Ex: Is there 11 in the array below? Where is
it?
index 0 1 2 3 4
value 55 99 44 11 33

• Two basic searches:

– Linear Search (Brute-force, sequential)
– Binary Search
 Linear Search
• Searching from the first or the last* element until
find the search value
• If found, return the position. Otherwise, return -1
(or any specific number) or not found.
• Example: search for “11” in
0 1 2 3 4
55 99 44 11 33
Searching
• Result: Found “11” at the position “3”
*From the last to the first element is also possible
 Linear Search Algorithm
• Given an array namely “data” of size “n”
• Search for a “value”

• Repeat
– if(data[i] == value)
• return i
• Until end of data
• Return -1 //not found, for integer search
Linear Search in Java
 Linear Search Efficiency
• Simplest but less efficient
• In worst case, the search element is at the
last position or is not found
• Therefore, we have to iterate all elements
and the algorithm runs in O(n)
0 1 2 3 4
55 99 44 11 33
Worst case is here
Searching or not found
 Binary Search
• A special case when all data are sorted.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2 4 5 7 8 9 12 14 17 19 22 25 27 28 33 37

• Can you explain how to search for a value

“22”?
 Binary Search
Objective: find 22
• mid = (low+high) /2

Image source: M. T. Goodrich et al., Data Structures and Algorithms in Java

 Exercise
• Explain how to search for “9”
 Solution Objective: find 9
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2 4 5 7 8 9 12 14 17 19 22 25 27 28 33 37
low mid high
9<14
0 1 2 3 4 5 6
2 4 5 7 8 9 12
low mid high
9>7

4 5 6
8 9 12
low high
9=9 Find 9 at position 5
 Binary Search Algorithm
• Given a sorted array “data” of size “n”
• Search for a “value”
• Repeat
– mid = (low+high)/2
– if(value==data[mid])
• return mid;
– else if(value<data[mid])
• high = mid -1
– else
• low = mid + 1
• Until low>high
• return -1 // not found, for integer search
Binary Search using Recursion

search(data, value, low, high)

search(data, 22, 0, 15)

search(data, 22, 8, 15)

search(data, 22, 8, 10)

search(data, 22, 10, 10)

Image source: M. T. Goodrich et al., Data Structures and Algorithms in Java

 Binary Search using Recursion
• How many base cases?
• What are they?

• Solution
– There are two base cases:
• Not found, return -1 (or any defined number)
• Found, return the middle position
 Binary Search Efficiency
• Worst case: search for first or last element
• Search for “37”

• In linear search, it requires 16 iterations

 Binary Search Efficiency
• Search for “37”
• In binary search, it requires
– 1 (mid=7) + 1 (mid=11) + 1 (mid=13) + 1 (mid=14)
+ 1 (mid=15) = 5 iterations

• Every round the data is cut off nearly by half

• It can be proved that binary search is O(log n)
 Binary Search in Java
• Java provides a built-in function “binarySearch”
to perform binary search in arrays
• See details at
https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html
 Example
import java.util.Arrays; Found 44 at position 3

public class BinarySearch {

public static void main(String[] args) {
int[] data = {11,22,33,44,55};
int key = 44;
int index = Arrays.binarySearch(data, key);
if(index>=0) {
System.out.println("Found "+key+" at position "+index);
}
else {
System.out.println(key+" is not found");
}
}
}
SORTING ALGORITHMS
 Why Sorting Is Needed
• Search in sorted collection is much faster
than an un-sorted collection.
• Sorting is useful to speed up for searching
large data.
• Ex.
– To look up a word in a dictionary, or
– To get the cheap price item from
google search.

Image source: https://www.pinterest.com/unitedteaching/math-sorting/

 Implementation of sorting
• Use array to store data i.e. integers to be sorted.
0 1 2 3 4
55 99 44 11 33

• Processes
– Swapping two elements of the array.
0 1 2 3 4
11 99 44 55 33

– Divide and Conquer (recursive)

• split the array in two subarrays. (Divide)
• merge the sorted subarrays. (Conquer)
• Ex. Quick sort, Merge sort
 How to choose the algorithm.
• Factors that influence the choice of a sorting
algorithm:

– Stable sort

– In-place sort

– Time Complexity
 Stable VS non stable sorting
• A “stable” sorting method preserves the
original input order among duplicates in the
output.
• Ex.

Useful when each data is a structure of {key, value}.

Ref: Cpt S 223. School of EECS, WSU

 In-place sort
• All operations are done in place of the input
array (i.e., without creating temp array).
• Or used only a small amount of additional
memory.
• Ex.

Swapping between 2 elements during sorting process.

 Swap Method
• It would be helpful to have a method that
swaps two elements of the array.
 Time Complexity
• Focusing on the growing term of the number of
operations that an algorithm can perform.
• Ex. An algorithm that performs n2/2-n/2
operations is a O(n2)
 Sorting algorithms
• Bubble Sort
• Selection Sort
• Insertion Sort
• Merge Sort
• Quick Sort
 Bubble Sort
• Basic Idea:
– Perform a sequence of passes through the array.
– On each pass: proceed from left to right, swapping adjacent
elements if they are out of order.
– Larger elements “bubble up” to the end of the array.
– At the end of the kth pass, the k rightmost elements are in
their final positions.
• Algorithm:
– Makes n-1 passes , n is no. of elements
– Each pass, move from a[0] to a[n-1]
• Compare a[i] and a[i+1] and swap if a[i]>=a[i+1]
(ascending order)
 Bubble Sort (cont.)
• Given a set of data in a data structure such
as an array

int[ ] data = {77,44,99,66,33,55,88,22}

0 1 2 3 4 5 6 7
77 44 99 66 33 55 88 22
 Bubble Sort (Ex.)
Index 0 1 2 3 4 5 6 7
Begin 77 44 99 66 33 55 88 22
Pass#1 44 77 99 66 33 55 88 22
77 99 swap 33 and 99
swap 66 and 99 66 99
or
swap(a[i],a[i+1]) 33 99 No.of
55 99 swap=7

88 99
22 99
After 44 77 66 33 55 88 22 99
Pass#1
 Bubble Sort (Ex.)
Index 0 1 2 3 4 5 6 7
Begin 77 44 99 66 33 55 88 22
Pass#1 44 77 66 33 55 88 22 99
Pass#2 44 66 33 55 77 22 88 99
Pass#3 44 33 55 66 22 77 88 99
Pass#4 33 44 55 22 66 77 88 99
Pass#5 33 44 22 55 66 77 88 99
Pass#6 33 22 44 55 66 77 88 99
Pass#7 22 33 44 55 66 77 88 99
7 passes, 18 swaps, and all
elements are sorted
 Bubble Sort: Pseudocode
//a[0] to a[n-1] is the array to sort
For i=n-1 to 1
for j=0 to j<i //index >i is already sorted
if (data[j] > data[j+1] //if this pair is out of order
swap (a[j], a[j+1]) //swap this pair
end if
end for
end for
 Bubble Sort Analysis
• Worst-case complexity О(n2), where n is the
number of elements
– when data is in reverse order.
– Every item have to be swapped with every other item
on every pass.

• It is In-place.

• It is Stable.
 Selection Sort
• Basic idea:
– It selects the smallest/largest value.
– and put it in the correct position by swapping.

• Algorithm:
– No of passes = n-1 , n is no. of elements
– At each pass
• Unsorted element with the smallest/ largest value is
moved to its proper position.
 Selection sort example
Given array : int[ ] data = {77,44,99,66,33,55,88,22}
Find min value

0 1 2 3 4 5 6 7 Min
value
77 44 99 66 33 55 88 22 22
i j=i+1 jMin
Swap (data[i],data[jMin])

Pass#1 22 44 99 66 33 55 88 77 22
 jMin Find min value
i j=i+1
Pass#2 22 44 99 66 33 55 88 77 33
swap

22 44 99 66 33 55 88 77

j=i+1 jMin Find min value

i
Pass#3 22 33 99 66 44 55 88 77 44
swap

22 33 44 66 99 55 88 77
 Selection Sort (Ex.)
Index 0 1 2 3 4 5 6 7 Min
swap value
Begin 77 44 99 66 33 55 88 22
Pass#1 22 44 99 66 33 55 88 77 22
Pass#2 22 33 99 66 44 55 88 77 33
Pass#3 22 33 44 66 99 55 88 77 44
Pass#4 22 33 44 55 99 66 88 77 55
Pass#5 22 33 44 55 66 99 88 77 66
Pass#6 22 33 44 55 66 77 88 99 77
Pass#7 22 33 44 55 66 77 88 99 88
7 passes, 6 swaps, and all
elements are sorted
 Selection Sort Pseudocode
For i=0 to n-1
//find the min element in the unsorted a[i..n-1]
jMin = i; //assume the min is the first element
//test against elements after j to find the smallest
For j=i+1 to n
//if this element is less, then it is the new minimum
if (a[j]<a[jMin])
//found new minimum; remember its index
jMin = j;
End if
End for
if (a[jMin] > a[i])
swap(a[i], a[jMin])
End if
End for
 Selection Sort Analysis
• More efficient than Bubble Sort
– Only one swap on each pass

• Time complexity --> O(n2)

– Selecting min element (scan all n element)
--> O(n-1)
– Find next min element --> O(n-1)

• It is in-place and stable algorithm.

 Insertion Sort
• Unlike other sorts, it passes through array
only once.

• Start with the elements and determine

where to insert them in the array

• Ex. A handful of playing cards

– Pick up the random card at a time
– Insert it into correct position in your hand
Image source: http://mathbits.com/MathBits/Java/arrays/InsertionSort.htm
 Insertion sort: Basic idea
• going from left to right, “insert” each
element into its proper place “sliding over”
other elements to make room.
 Insertion Sort: Algorithm
• Makes n-1 passes, consider data[i] when data[0] to
data[i-1] are sorted.
Ex. data[3]

• At each pass, consider j=i-1, i-2,…

– Make a copy of data[i], store it in (temp) variable insert.
insert

– If data[j]> insert, slide it over to the right

insert
– Stop when data[j]<= insert

– Copy insert into the hole.

 Insertion Sort: Example
Index 0 1 2 3 4 5 6 7
data 77 44 99 66 33 55 88 22
Greater value of j is moved to the right and
j=i-1 i 44 is inserted before 77 insert
Pass 1 77 44 99 66 33 55 88 22 44

44 77 99 66 33 55 88 22 44
No greater value of j is moved,
j i insert
99 is at the proper position.
Pass 2 44 77 99 66 33 55 88 22 99

44 77 99 66 33 55 88 22 99
 Insertion Sort: Example
greater values 99 and 77 are moved to the right
66 is inserted before 77
j i insert
Pass 3 44 77 99 66 33 55 88 22 66

44 66 77 99 33 55 88 22 66

greater values 99,77,66,44 are moved to the right

33 is inserted before 44
j i insert
Pass 4 44 66 77 99 33 55 88 22 33

33 44 66 77 99 55 88 22 33
 Insertion Sort (Ex)
Sorted
Index 0 1 2 3 4 5 6 7
Begin 77 44 99 66 33 55 88 22
Pass#1 44 77 99 66 33 55 88 22
Pass#2 44 77 99 66 33 55 88 22
Pass#3 44 66 77 99 33 55 88 22
Pass#4 33 44 66 77 99 55 88 22
Pass#5 33 44 55 66 77 99 88 22
Pass#6 33 44 55 66 77 88 99 22
Pass#7 22 33 44 55 66 77 88 99
 Insertion Sort: Pseudocode
//data[0] to data[n-1] is the array to sort
Let i be the no. of items sorted so far
Let insert be the item to be inserted
For i=1 to n //start with second element
insert= data[i]
j = i-1;
//move the greater value up
while (j>=0 and insert< data[j])
data[j+1] = data[j]
j=j-1
end while
data[j+1] = insert// place the insert in its proper position (the hole)
end for
 Insertion Sort Analysis
• Efficient for smaller data but very inefficient for
large data

• Its efficiency increases if given a partially sorted

list.

• Worst case O(n2) → reversed ordered elements

• It is in-place and stable algorithm.

 Merge Sort : Basic idea
• It applies divide-and-conquer strategy to
sort a list.
• It is naturally recursive.
• Divide-and-conquer
– Divide: split the array in half, form two
subarrays and apply mergesort recursively to
subarrays, stop when a subarray has a single
element.
– Conquer: merge the sorted subarrays
 Merge Sort (Ex)
77 44 99 66 33 55 88 22

77 44 99 66 33 55 88 22

Split
O(log n) 77 44 99 66 33 55 88 22

77 44 99 66 33 55 88 22

44 77 66 99 33 55 22 88
Merge
and 44 66 77 99 22 33 55 88
compare
O(n log n)
22 33 44 55 66 77 88 99
 Merge Sort: Algorithm
Let data = {data[low],…, data[high]}
1. If low+high>1, do steps 2-5
2. Split data into 2 subarrays, A={data[low],…
data[mid]}
and B = {data[mid+1],…, data[high]}, where
mid=(low+high)/2
3. Sort A.
4. Sort B.
5. Merge A and B back in preserving order.
 Merge Sort Pseudocode
//data[0] to data[n-1] is the array to sort
mergeSort (int[ ] data){
mSort(0, n-1)
}
mSort (low, high){
if (low+high>1)
mid = (low+high)/2; //split to two subarray
mSort(low, mid) //sort first half subarray
mSort(mid+1, high) //sort second half subarray
merge(low, mid, high) //merge 2 subarrays back
else //base case: there will be one or two elements
if(low<high) //two elements
if(data[low]>data[high])
swap(data[low],data[high])
else //one element then do nothing
}
 Merge algorithm
• Copy sorted array data to array temp and
set index to each start point.

• Repeat the following

– Compare temp[i] and temp[j]
– Copy the smaller value between both to data[k]
– Increment index of the array whose element
was copied
– Increment k
 How to merge 2 sorted arrays
compare A[i] and B[j] • copy the smaller of the two to C[k] • increment the
index of the array whose element was copied • increment k
i
A 44 66 77 99 k
j 22
B 22 33 55 88
B[j]<A[i]→ copy B[j]
i
A 44 66 77 99 k
j 22 33
B 22 33 55 88
B[j]<A[i]→ copy B[j]
 i
A 44 66 77 99 k
j 22 33 44
B 22 33 55 88
A[i]<B[j]→ copy A[i]
i
A 44 66 77 99 k
j 22 33 44 55
B 22 33 55 88
B[j]<A[i]→ copy B[j]
i
A 44 66 77 99 k
j 22 33 44 55 66
B 22 33 55 88
A[i]<B[j]→ copy A[i]
 i

A 44 66 77 99 k
j 22 33 44 55 66 77
B 22 33 55 88
A[i]<B[j]→ copy A[i]
i

A 44 66 77 99 k
j 22 33 44 55 66 77 88
B 22 33 55 88
B[j]<A[i]→ copy B[j]
i

A 44 66 77 99 k
22 33 44 55 66 77 88 99
B 22 33 55 88
copy A[i]
 Merge Sort Pseudocode
merge (low, mid, high){
//copy data to new array, n is no. of elements
temp = Arrays.copyOf(data, n)
//temp array is split to 2 parts: left and right
i = low //left part
j = mid+1 //right part
k= low //index to fill in the original array
While (i<=mid and j<=high)
if (temp[i]<=temp[j]) // ascending array
data[k]=temp[i]
i++
else
data[k]=temp[j]
j++
end if
k++
End while
//copy the rest to the original array
While (i<=mid)
data[k] = temp[i]
i++ , k++
End while
 Merge Sort Analysis
• Time Complexity
– Best case and worst case --> O(n log n)
– As merge sort always divides the array in two
halves and take linear time to merge two halves.

• It is stable algorithm.

• It is not in-place algorithm (need extra

temporary array).
 Quick Sort: Basic idea
• It applies divide-and-conquer.
• It is naturally recursive:
– partition the array into two pieces separated by the pivot
element.
• All left elements <= pivot <= all right elements

– then call the quicksort procedure recursively to sort the

two partitions,

Image source: https://www.cs.auckland.ac.nz/software/AlgAnim/qsort.html

 Quick Sort: Algorithm
Let data = {data[low],…, data[high]}
1. If low<high, do steps 2-5
2. Apply Partition Algorithm to data[] to obtain
index pivot .
3. The pivot data[pivot] is in its correct sorted
position.
4. Apply quick sort to {data[low],…, data[pivot-1]}
5. Apply quick sort to {data[pivot+1],…, data[high]}
Quick Sort: Algorithm (cont)
Partition algorithm

Let data = {data[low],…, data[high]}

1. Set pivot = data[low] (the pivot element)
2. Set i = low and j = high
3. Repeat steps 4-7 while i<j
4. Increment i until data[i]>=pivot
5. Decrement j until data[j]<= pivot
6. Swap data[i] and data[j]
 Quick sort: example
• Given array data []
low high
77 44 99 66 33 55 88 22

• index i ,j (starting outside array)

– i=low - 1 i j
77 44 99 66 33 55 88 22
– j = high +1
– pivot = data[low]=77
• Find i and j :
– Increment i until data[i]>=pivot
– Decrement j until data[j] <=pivot
i j
77 44 99 66 33 55 88 22

• Swap data[i] and data[j]

i j
22 44 99 66 33 55 88 77
 Quick sort: example (cont)
pivot = 77
i j
• Previous 22 44 99 66 33 55 88 77

i j
• Find 22 44 99 66 33 55 88 77

i j
• Swap 22 44 77 66 33 55 88 99

i j
• Find 22 44 77 66 33 55 88 99

i j
• Swap 22 44 55 66 33 77 88 99
 Quick sort: example (cont.)
i j
• Previous 22 44 55 66 33 77 88 99

i, j
• Find i=j and return j 22 44 55 66 33 77 88 99

• Left = {data[low], … , data[j-1] } and right = {data[j+1], … ,

data[high] } low j-1 i, j j+1 high
22 44 55 66 33 77 88 99
• Do recursively the partition on left and right arrays
• At each partition the pivot is in its correct position and then obtain the sorted
result
22 44 55 66 33 77 88 99
pivot pivot
22 44 55 66 33 88 99

22 44 55 66 33 88 99

pivot 99
44 55 66 33
33 44 66 55 • Partition O(log n) x comparison O(n)
• Total time complexity is O(n log n)
pivot
33
66 55
55 66
55
Sorted array
22 33 44 55 66 77 88 99
 Quick Sort: Pseudocode
//data[0] to data[n-1] is the array to sort
quickSort(int[] data) {
qSort(data, 0, n – 1)
}

qSort(int[] data, low, high) {

split = partition(data, low, high)
if (low< split)
qSort(data, low, split) // left subarray
end if
if (high> split + 1)
qSort(data, split + 1, high); // right subarray
end if
}
 Quick Sort: Pseudocode (cont)
int partition(int[] data, low, high) {
pivot = data[low]
i = low- 1 // index going left to right
j = high+ 1 // index going right to left
while (true)
do
i++
while (data[i] < pivot) // stop when “data[i] >= pivot”
do
j--
while (data[j] > pivot) // stop when “data[j] <= pivot”
if (i < j)
swap( i, j)
else
return j // data[j] = end of left array
end if
end while
}
 Possible Pivot Values
• Good pivot is one that creates two even sized
partitions.
• Some possible pivot values :
– First or last element
• Risky, can lead to worst-case
• Poor if array is almost sorted
– Randomly chosen element
• Still possible to get some bad choices
• Requires execution of random number generator
– Median of array
• Best choice but expensive to calculate
 Quick Sort Analysis
• Best case : O(n log n)
– The elements are randomly distributed so that they can
split in balance.
• Worse case: O(n2) (rare case)
– The array is already sorted (or sorted in reversed).
– The partition algorithm selects the pivot which make
most unbalanced split: one piece has n-1 elements and
another piece has 1 element
• Average case: O(n log n)
– The case occurs when the pivot splits the array in half or
nearly in half on each pass. Each pass through the
algorithm requires N comparisons.
 Quick Sort Analysis (cont.)
• Time complexity: the worse case is rare so
that it has time of O(n log n).

• It is in-place algorithm.

• It is not stable algorithm.

Sorting Algorithms Comparison
Algorithm Time In-place Stable remarks
Complexity
(Worst case)
Insertion sort O(n2) Yes Yes
Selection sort O(n2) Yes No
Bubble sort O(n2) Yes Yes
Merge sort O(n log n) No Yes Typical not-in-
place but can be
in-place.
Quick sort O(n2) Yes No O(n log n) in
average case.
Worst case is
rare.
 Useful java in sorting
• Print method
 Useful java in sorting

• Array.sort() method is defined in java class

library.
• For primitive type, it implements the quick
sort.
 Summary
• What is the difference between linear search
and binary search?
• Why sorting is needed?
• How do bubble, selection, insertion, merge,
quick sort work?
• How are they different?
• What is divide-and-conguer?
• Which sort algorithm use divide and conquer?