Searching & Sorting Algorithms Overview
M
o
d
u
l
e
6
–
S
e
a
r
c
h
i
n
g
&
S
o
r
t
i
n
g
A
l
g
o
r
i
t
h
m
s
L
i
n
e
a
r
S
e
a
r
c
h
A
l
g
o
r
i
t
h
m
CREATE
list
G
, target, isInList
isInList =
false
BEGIN
FOR each element temp in
list
G
IF (temp ==
target
)
isInList = true
BREAK
ENDIF
ENDFOR
END
C
+
+
L
i
n
e
a
r
S
e
a
r
c
h
A
l
g
o
r
i
t
h
m
bool
isFound =
false
;
for
(
int
i = 0; i < size; i++)
{// If we find a match, set isFound to true and BREAK
if
(array[i] == target)
{isFound
= true
;
break;
}
}
Binary Search Algorithm
CREATE low = 0, mid = 0
CREATE high = length of searchArray - 1
CREATE found = false
WHILE (high >= low)
mid = (low + high) / 2
IF (find < searchArray[mid]) THEN
high = mid - 1
ELSE IF (find == searchArray[mid]) THEN
found = true and stop looking
ELSE
low = mid + 1
END WHILE
PRINT (find + " is " + found)
C++ Binary Search Algorithm
int
low =
0
, mid =
0
;
int
high = arraySize;
bool
found =
false
;
while
(high >= low)
{mid = (low + high) /
2
;
if
(find < searchArray[mid]) {high = mid -
1
;
}
else
if
(find == searchArray[mid]) {found =
true
;
break
;
}
else
low = mid +
1
;
}
BubbleSort Code
for
(
int
i =
0
; i < n-
1
; i++)
{for
(
int
j =
0
; j < n-i-
1
; j++)
{if
(arr[j] > arr[j+
1
])
{// swap temp and arr[i]
int
temp = arr[j];
arr[j] = arr[j+
1
];
arr[j+
1
] = temp;
}
}
}
Selection Sort Algorithm
FOR each I from 0 to n
minPos = I
FOR each J from I + 1 to n
IF
(
B[j] < B[minPos]
)
minPos = J
ENDIF
ENDFOR
IF
(I
!= minPos AND minPos < n
)
temp = B[minPos]
B[minPos] = B[
I
]
B[
I
] = temp
ENDIF
ENDFOR
I
n
s
e
r
t
i
o
n
S
o
r
t
A
l
g
o
r
i
t
h
m
FOR each index from 1 to n
key = A[index]
position = index
// Shift larger values to the right
WHILE (position > 0 AND key < A[position-1])
A
[position] = A[position - 1]
position = position - 1
ENDWHILE
A [position] = key
ENDFOR
C
+
+
I
n
s
e
r
t
i
o
n
S
o
r
t
A
l
g
o
r
i
t
h
m
for
(
int
index=1; index < size; index++)
{int
key = list [index];
int
position = index;
// Shift larger values to the right
while
(position > 0 && key < list[position-1])
{list [position] = list [position - 1];
position--;
}
list [position] = key;
}
S
o
r
t
i
n
g
i
n
a
C
+
+
P
r
o
g
r
a
m
•
Vectors can be sorted by including “algorithm”, but it’s
complicated:
#include <algorithm>
•
Beyond the scope of this class
Explore various sorting and searching algorithms such as Linear Search, Binary Search, Bubble Sort, Selection Sort, and Insertion Sort. The provided content presents code snippets and explanations for each algorithm, illustrating their implementation in both C++ and generic pseudocode.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Ps Module 6 Module 6 Searching & Searching & Sorting Algorithms Sorting Algorithms
Linear Search Algorithm Linear Search Algorithm CREATE list G, target, isInList isInList = false BEGIN FOR each element temp in list G IF (temp == target) isInList = true ENDIF ENDFOR END BREAK Ps
C++ Linear Search Algorithm C++ Linear Search Algorithm bool isFound = false; for (int i = 0; i < size; i++) { // If we find a match, set isFound to true and BREAK if (array[i] == target) { isFound = true; break; } }
Binary Search Algorithm CREATE low = 0, mid = 0 CREATE high = length of searchArray - 1 CREATE found = false WHILE (high >= low) mid = (low + high) / 2 IF (find < searchArray[mid]) THEN high = mid - 1 ELSE IF (find == searchArray[mid]) THEN found = true and stop looking ELSE low = mid + 1 Ps END WHILE PRINT (find + " is " + found)
C++ Binary Search Algorithm int low = 0, mid = 0; int high = arraySize; bool found = false; while (high >= low) { mid = (low + high) / 2; if (find < searchArray[mid]) { high = mid - 1; } else if (find == searchArray[mid]) { found = true; break; } else low = mid + 1; }
BubbleSort Code for (int i = 0; i < n-1; i++) { for (int j = 0; j < n-i-1; j++) { if (arr[j] > arr[j+1]) {// swap temp and arr[i] } } } int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp;
Selection Sort Algorithm FOR each I from 0 to n minPos = I FOR each J from I + 1 to n IF (B[j] < B[minPos]) minPos = J ENDIF ENDFOR IF (I != minPos AND minPos < n) temp = B[minPos] B[minPos] = B[I] B[I] = temp ENDIF ENDFOR Ps
Insertion Sort Algorithm Insertion Sort Algorithm FOR each index from 1 to n key = A[index] position = index // Shift larger values to the right WHILE (position > 0 AND key < A[position-1]) A[position] = A[position - 1] position = position - 1 ENDWHILE A [position] = key ENDFOR Ps
C++ Insertion Sort Algorithm C++ Insertion Sort Algorithm for (int index=1; index < size; index++) { int key = list [index]; int position = index; // Shift larger values to the right while (position > 0 && key < list[position-1]) { list [position] = list [position - 1]; position--; } list [position] = key; }
Sorting in a C++ Program Sorting in a C++ Program Vectors can be sorted by including algorithm , but it s complicated: #include <algorithm> Beyond the scope of this class
