CSC 344 – Algorithms and
Complexity
Lecture #3 – Internal Sorting
What is the Brute Force Approach?
• A straightforward approach, usually based
directly on the problem’s statement and
definitions of the concepts involved
• Examples:
1. Computing an (a > 0, n a nonnegative integer)
2. Computing n!
3. Multiplying two matrices
4. Searching for a key of a given value in a list
, Brute-Force Sorting Algorithm
• Selection Sort
– Scan the array to find its smallest element and swap it with
the first element.
– Starting with the second element, scan the elements after it
to find the smallest among them and swap it with the
second elements.
– Generally, on pass i (0 ≤ i ≤ n-2), find the smallest element
after A[i] and swap it with A[i]:
A[0] ≤ . . . ≤ A[i-1] | A[i], . . . , A[min], . . ., A[n-1]
in their final positions
• Example: 7 3 2 5
Selection Sort
// selectionSort() - The selection sort where we
// seek the ith smallest value and
// swap it into its proper place
void selectionSort(int x[], int n) {
int i, j, min;
for (i = 0; i < n-1; i++) {
min = i;
for (j = i; j < n; j++) {
if (x[j] < x[min])
min = j;
swap(x[i], x[min]);
}
}
}
, Analysis of Selection Sort
• Time efficiency:
• Space efficiency:
• Stability:
Decrease and Conquer
1. Reduce problem instance to smaller instance of the
same problem
2. Solve smaller instance
3. Extend solution of smaller instance to obtain solution
to original instance
• Can be implemented either top-down or bottom-up
• Also referred to as inductive or incremental approach
, 3 Types of Decrease and Conquer
• Decrease by a constant (usually by 1):
– insertion sort
• Decrease by a constant factor (usually by half)
– binary search
– exponentiation by squaring
• Variable-size decrease
– Euclid’s algorithm
– Nim-like games
Insertion Sort
• To sort array A[0..n-1], sort A[0..n-2] recursively and
then insert A[n-1] in its proper place among the
sorted A[0..n-2]
• Usually implemented bottom up (nonrecursively)
• Example: Sort 6, 4, 1, 8, 5
6|4 1 8 5
4 6|1 8 5
1 4 6|8 5
1 4 6 8|5
1 4 5 6 8
Complexity
Lecture #3 – Internal Sorting
What is the Brute Force Approach?
• A straightforward approach, usually based
directly on the problem’s statement and
definitions of the concepts involved
• Examples:
1. Computing an (a > 0, n a nonnegative integer)
2. Computing n!
3. Multiplying two matrices
4. Searching for a key of a given value in a list
, Brute-Force Sorting Algorithm
• Selection Sort
– Scan the array to find its smallest element and swap it with
the first element.
– Starting with the second element, scan the elements after it
to find the smallest among them and swap it with the
second elements.
– Generally, on pass i (0 ≤ i ≤ n-2), find the smallest element
after A[i] and swap it with A[i]:
A[0] ≤ . . . ≤ A[i-1] | A[i], . . . , A[min], . . ., A[n-1]
in their final positions
• Example: 7 3 2 5
Selection Sort
// selectionSort() - The selection sort where we
// seek the ith smallest value and
// swap it into its proper place
void selectionSort(int x[], int n) {
int i, j, min;
for (i = 0; i < n-1; i++) {
min = i;
for (j = i; j < n; j++) {
if (x[j] < x[min])
min = j;
swap(x[i], x[min]);
}
}
}
, Analysis of Selection Sort
• Time efficiency:
• Space efficiency:
• Stability:
Decrease and Conquer
1. Reduce problem instance to smaller instance of the
same problem
2. Solve smaller instance
3. Extend solution of smaller instance to obtain solution
to original instance
• Can be implemented either top-down or bottom-up
• Also referred to as inductive or incremental approach
, 3 Types of Decrease and Conquer
• Decrease by a constant (usually by 1):
– insertion sort
• Decrease by a constant factor (usually by half)
– binary search
– exponentiation by squaring
• Variable-size decrease
– Euclid’s algorithm
– Nim-like games
Insertion Sort
• To sort array A[0..n-1], sort A[0..n-2] recursively and
then insert A[n-1] in its proper place among the
sorted A[0..n-2]
• Usually implemented bottom up (nonrecursively)
• Example: Sort 6, 4, 1, 8, 5
6|4 1 8 5
4 6|1 8 5
1 4 6|8 5
1 4 6 8|5
1 4 5 6 8
