Transcript Computational Thinking Presentation 06 Algorithms and

Algorithms and Programming
Chin-Sung Lin
Eleanor Roosevelt High School
Algorithms and Programming
• Types of Algorithms
– Brute-Force (or Exhaustive Search)
– Divide and Conquer
– The Greedy Method
– Recursion
• Algorithms of Skyscrapers Project
– Review of Pseudo Code
– Decimal-to-Binary Conversion Algorithm
• Programming: A Crash Course of C
• Sorting Algorithms and Implementations
• Searching Algorithms and Implementations
Brute-Force Algorithms
Brute-Force (or Exhaustive Search)
• Brute-force is a straightforward approach to solving a
problem, usually directly based on the problem ’ s
statement and definitions of the concepts involved.
• Try out all possible values or combinations to solve a
problem, or try every possible solution to see which is best.
Brute-Force (or Exhaustive Search) Example
• Example:
Try out all possible combinations to
open a lock.
• Example:
Try out all possible password
values to log into an account.
Brute-Force (or Exhaustive Search) Example
• Example:
Compute an for a given number a and a nonnegative integer
n. By the definition of exponentiation, an = a  a    a.
n times
• Example:
Build 250-block skyscraper by
adding one block each week.
Brute-Force (or Exhaustive Search)
Though inefficient in general, the brute-force algorithm should not be
overlooked as an important algorithm design strategy for the following
reasons:
• It is applicable to a very wide variety problems, and seems to be the
only general approach for all problems.
• The expense of designing a more efficient algorithm may be
unjustifiable if only a few instances of a problem need to be solved
and a brute-force algorithm can solve those instances with
acceptable speed.
• It is useful for solving small-size instances of a problem.
• It can serve as an important theoretical or education purpose, e.g.,
as a benchmark to judge more efficient alternatives algorithms.
Divide and Conquer Algorithms
Divide and Conquer
• Repeatedly reduces an instance of a problem to one or more
smaller instances of the same problem (usually recursively)
until the instances are small enough to solve easily. The
solutions to the subproblems are then combined to give a
solution to the original problem.
Divide and Conquer
The most well known algorithm design strategy:
1.
Divide the problem into two or more smaller subproblems.
2.
Conquer the subproblems by solving them recursively.
3.
Combine the solutions to the subproblems into the
solutions for the original problem.
Divide and Conquer Example
Example:
Large-integer multiplication (The Grade-School
Algorithm)
x
a1 a2 … a n
b1 b2 … bn
(d10) d11d12 … d1n
(d20) d21d22 … d2n
…………………
(dn0) dn1dn2 … dnn
This process requires n2 single digit multiplications.
For 1231  2012, this process requires 16 multiplications.
Divide and Conquer Example
Large-integer multiplication (Divide and Conquer Algorithm)
1231  2012
= (12*102 + 31) * (20*102 + 12)
= (12*20)*104 + c1*102 + 31*12
where c1 = (12+31)*(20+12) – 12*20 – 31*12 = 764
12*20 = (1*10 + 2) * (2*10 + 0)
= (1*2)*102 + c2*10 + 2*0
where c2 = (1+2)*(2+0) – 1*2 – 2*0 = 4
31*12 = (3*10 + 1) * (1*10 + 2)
= (3*1)*102 + c3*10 + 1*2
where c3 = (3+1)*(1+2) – 3*1 – 1*2 = 7
(12+31)*(20+12) = 43 * 32
= (4*10 + 3) * (3*10 + 2)
= (4*3)*102 + c4*10 + 3*2
where c4 = (4+3)*(3+2) – 4*3 – 3*2 = 17
This process requires 9 digit multiplications as opposed to 16.
Greedy Algorithms
Greedy Algorithms
• An optimization problem is one in which you want to find,
not just a solution, but the best solution.
• It is not exhaustive, and does not give an accurate answer
to many problems. But when it works, it is the fastest
method.
• A greedy algorithm works in phases. At each phase:
– You take the best you can get right now, without regard for
future consequences
– You hope that by choosing a local optimum at each step, you
will end up at a global optimum
14
Greedy Algorithm Example
• Example:
Pay out the exact amount of money
using US monetary system.
• Example:
The knapsack problem – Given a
set of items, each with a mass and
a value, determine the number of
each item to include in a collection
so that the total weight is less than
or equal to a given limit and the total
value is as large as possible.
Greedy Algorithm Example
• Example: Dijkstra's algorithm (single-source shortest path
problem)
Works on both directed and undirected graphs. However, all
edges must have nonnegative weights.
Input: Weighted graph and source vertex (v) such that all
edge weights are nonnegative
Output: Lengths of shortest paths (or the shortest paths
themselves) from a given source vertex (v) to all other
vertices
Greedy Algorithm Example
Greedy Algorithm Example
Greedy Algorithm Example
Greedy Algorithm Example
Greedy Algorithm Example
Greedy Algorithm Example
Greedy Algorithm Example
Greedy Algorithm Example
Greedy Algorithm Example
Greedy Algorithm Example
Recursive
Algorithms
Recursive
Algorithms
Recursive
Algorithms
Recursive
Algorithms
Recursive
Algorithms
Recursive
Algorithms
Recursive
Algorithms
Recursion
A recursive function is one which calls itself. To prevent infinite
recursion, you need an if-else statement (of some sort) where
one branch makes a recursive call, and the other branch does
not.
Recursion
Dream (problem)
{
If problems solved
return solution
else
dream(problem)
}
Recursion Example
• Example: Calculate the factorial of N:
N! = N x (N-1) x (N-2) x ……. x 3 x 2 x 1
Traditional algorithm using Loop:
Factorial ()
1.
Let index = 1
2.
Let product = 1
3.
For index = 1 to N
product = product x index
4.
end-For
5.
return product
Recursion Example
•
Example: Calculate the factorial of N:
N! = N x (N-1) x (N-2) x ……. x 3 x 2 x 1
Recursive algorithm:
Factorial(long n)
{
if (n==1)
return(n
}
*
return(n);
else
factorial(n-1));
Recursion Example
A traditional algorithm for finding the Fibonacci Numbers (0, 1,
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ……)
Fibonacci ()
1. Input N
2. Let result0 = 0
3. Let result1 = 1
4. If N = 1 or N = 2
5.
result = N - 1
6. else
7.
for loop counter = 2 to N – 1
8.
result = result1 + result0
9.
result0 = result1
10.
result1 = result
11.
end-for loop
12. end-if
13. output result
Recursion Example
A recursive algorithm for finding the Fibonacci Numbers (0, 1, 1, 2, 3,
5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ……)
Fibonacci (N)
1. If N = 1 or N = 2
2.
return (N – 1)
3. else
4.
return Fibonacci (N – 1) + Fibonacci (N – 2)
5. end-if
Algorithms of Skyscrapers Project
Algorithms of Skyscrapers Project
Rules:
• Using prefabricated-modular blocks of 100 meters long, 100 meters
wide, and 5 meters tall.
• The blocks interlock on top and bottom (like Legos), and they
cannot be stacked sideways.
• Using special lifters, putting stacks of blocks at the same height on
ground or on top of another set of equal-height stacks takes one
week regardless of how tall the stacks are or how many stacks are
lifted.
• The prefabrication time of the blocks doesn’t count since they are
already in stock.
• No resource/budget limitations (i.e., you can have as many stacks
as possible at the same time),
Algorithms of Skyscrapers Project
Problem Part A:
• If a client wants to build a 100-meter long, 100-meter wide, and
1250-meter high tower as quickly as possible, what is the shortest
amount of time that it will take to build the tower?
• Show your algorithm in both flowchart and pseudocode forms.
Problem Part B:
• Develop a general algorithm for skyscrapers of 100-meter long,
100-meter wide, and N-meter high (where N is a multiple of 5) in
pseudocode format.
Review of Pseudocode
Convention of Pseudocode
Write pseudocode for:
• calculating total number of blocks needed for N-meter high
skyscraper.
• calculating the remainder of number of stacks divided by 2.
• creating a while loop to work as long as the number of stacks is
not equal to 1.
• creating a counter to increment the week count in a while loop.
Convention of Pseudocode
Write pseudocode for:
• calculating total number of blocks needed for N-meter high
skyscraper.
1. numberBlock = N/5
Convention of Pseudocode
Write pseudocode for:
• calculating the remainder of number of stacks divided by 2.
1. Remainder = numberStack % 2
Convention of Pseudocode
Write pseudocode for:
• creating a while loop to work as long as the number of stacks is
not equal to 1.
1. While loop numberStack ≠ 1
2.
……
3. end-loop
Convention of Pseudocode
Write pseudocode for:
• creating a counter to increment the week count in a while loop.
1. weekCounter = 0
2. While loop numberStack ≠ 1
3.
weekCounter = weekCounter + 1
4. end-loop
Group Presentation of
Skyscraper Algorithms
Decimal-to-Binary Conversion
Algorithm
Decimal-to-Binary Conversion
2
2
240
0
120
0
60
0
30
0
2
15
1
2
7
1
2
3
1
2
2
1
Decimal:
240
Binary:
11110000
No. of Division
7
No. of One’s:
4
No. of Weeks: 7 + 4 = 11
Programming:
A Crash Course of C
C Example: Sum of 1+ 2+…+N
1.
// Calculate the Sum of 1 + 2 + 3 + ….. + N
2.
#include <stdio.h>
3.
int main ()
4.
{
5.
int n, i;
6.
int sum = 0;
7.
printf("Enter N: ");
8.
scanf("%d", &n);
9.
for (i = 1; i <= n; i++)
10.
sum = sum + i;
11.
printf("Sum = %d\n", sum);
12.
return 0;
13. }
C Example: Average of Numbers
1.
// Calculate the average of three numbers
2.
// average = (a + b + c)/3
3.
#include <stdio.h>
4.
int main()
5.
{
6.
float a, b, c;
7.
float average;
8.
printf ("Averaging three numbers \n");
9.
printf ("Enter three numbers a, b, and c: ");
10.
scanf ("%f %f %f", &a, &b, &c);
11.
average = (a + b + c)/3.0;
12.
printf("Average = %.2f\n", average);
13.
return 0;
14. }
C Example: Linear Equation
1.
// Solve Linear Equation
2.
// ax + b = c, x = (c - b)/a
3.
#include <stdio.h>
4.
int main()
5.
{
6.
float a, b, c;
7.
float x;
8.
printf("Solve linear equation: ax + b = c\n");
9.
printf("Enter coefficients: a, b, c: ");
10.
scanf ("%f %f %f", &a, &b, &c);
11.
x = (c - b)/a;
12.
printf ("x = %.2f\n", x);
13.
return 0;
14. }
C Example: Skyscraper Algorithm
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
// Skyscraper Algorithm
#include <stdio.h>
int main()
{
int noWeek, buildingHeight, noStack, remainder;
noWeek = 1;
printf ("Hello! Please enter the building height: ");
scanf ("%d", &buildingHeight);
noStack = buildingHeight/5;
while (noStack != 1)
{
remainder = noStack%2;
noStack = noStack/2;
noWeek = noWeek + remainder + 1;
}
printf("Number of Week to Build the Skyscraper is: %d\n", noWeek);
return 0;
}
C Example: Square Root
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
#include <stdio.h>
#include <math.h>
int main()
{
float a;
float x;
printf("Please enter the number: ");
scanf("%f", &a);
if (a < 0)
printf("No solution.\n");
else
{
x = sqrt(a);
printf("sqrt(%.2f) = %.5f\n", a, x);
}
return 0;
}
C Example: Integer Array
1.
// Integer Array
2.
#include <stdio.h>
3.
#define MAX 5
4.
int main()
5.
{
6.
int array[MAX];
7.
float sum = 0.;
8.
int i;
9.
printf("Enter 5 integers: ");
10.
for (i =0; i < MAX; i++)
11.
{
12.
scanf("%d", &array[i]);
13.
sum = sum + array[i];
14.
}
15.
for (i =0; i < MAX; i++)
16.
printf("array[%d] = %d\n", i, array[i]);
17.
printf("Average = %.2f\n", sum/MAX);
18.
return 0;
19. }
C Example: Integer Array
Output:
Enter 5 integers:
Output:
1 2 3 4 5
Enter 5 integers:
array[0] = 1
array[0] = 1
array[1] = 2
array[1] = 2
array[2] = 3
array[2] = 3
array[3] = 4
array[3] = 4
array[4] = 5
array[4] = 6
Average = 3.00
Average = 3.20
1 2 3 4 6
C Example: Character Strings
1.
// Strings are Array of Characters.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
#include <stdio.h>
#include <string.h>
#define MAX_STRING_LENGTH 80
int main()
{
char str[MAX_STRING_LENGTH];
unsigned long length;
int i;
str[0] = 'H';
str[1] = 'e';
str[2] = 'l';
str[3] = 'l';
str[4] = 'o';
str[5] = '!';
str[6] = '\0';
length = strlen(str);
for (i = 0; i < length; i++)
printf("str[%d] = %c\n", i, str[i]);
printf("\nstring =\t%s\n", str);
printf("length =\t%lu\n", length);
return 0;
}
C Example: Character Strings
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
// Strings are Array of Characters.
#include <stdio.h>
#include <string.h>
#define MAX_STRING_LENGTH 80
int main()
{
char str[MAX_STRING_LENGTH];
unsigned long length;
int i;
str[0] = 'H';
str[1] = 'e';
str[2] = 'l';
str[3] = 'l';
str[4] = 'o';
str[5] = '!';
str[6] = '\0';
length = strlen(str);
for (i = 0; i < length; i++)
printf("str[%d] = %c\n", i, str[i]);
printf("\nstring =\t%s\n", str);
printf("length =\t%lu\n", length);
return 0;
}
Output:
str[0]
str[1]
str[2]
str[3]
str[4]
str[5]
=
=
=
=
=
=
string =
length =
H
e
l
l
o
!
Hello!
6
C Example: Strings Operations
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
// Strings IO from Command Line
// String Comparison, Concatenation &
Copy
#include <stdio.h>
#include <string.h>
#define MAX_STRING_LENGTH 80
int main()
{
char str1[MAX_STRING_LENGTH];
char str2[MAX_STRING_LENGTH];
char str3[MAX_STRING_LENGTH];
printf("\nString 1: ");
scanf("%s", str1);
printf("\nString 2: ");
scanf("%s", str2);
printf("\nString1 =\t%s\n", str1);
printf("\nString2 =\t%s\n", str2);
17. if(strcmp(str1, str2) > 0)
18.
{
19.
printf("\nString1 > String2\n");
20.
strcat(str1, str2);
21.
printf("\nString1=\t%s\n", str1);
22.
printf("\nString2=\t%s\n", str2);
23.
}
24.
else if (strcmp(str1, str2) < 0)
25.
{
26.
printf("\nString1 < String2\n");
27.
strcat(str2, str1);
28.
printf("\nString1=\t%s\n", str1);
29.
printf("\nString2=\t%s\n", str2);
30.
}
31.
else
32.
{
33.
printf("\nString1 = String2\n");
34.
strcpy(str3, str1);
35.
printf("\nString3: %s\n", str3);
36.
}
37.
return 0;
38. }
ASCII Code
C Example: Strings Operations
Output:
Output:
Output:
String 1: Ally
String 1: Alexia
String 1: ELRO
String 2: Henry
String 2: Zoe
String 2: ELRO
String1 = Ally
String1 = Alexia
String1 = ELRO
String2 = Henry
String2 = Zoe
String2 = ELRO
String1 < String2
String1 < String2
String1 = String2
String1=
Ally
String1=
Alexia
String3: ELRO
String2=
HenryAlly
String2=
ZoeAlexi
C Example: File R/W, Strings & Array
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
// Read / Write Strings and Integers from / to Files
#include <stdio.h>
#define FILESIZE 10
#define STRINGLENGTH 15
int main()
{
FILE* fileInput = NULL;
FILE* fileOutput = NULL;
char str[FILESIZE][STRINGLENGTH];
int number[FILESIZE];
int i;
fileInput = fopen("input.txt", "r");
fileOutput = fopen("output.txt", "w");
for (i = 0; i < FILESIZE; i++)
fscanf (fileInput, "%s %d", str[i], &number[i]);
for (i = 0; i < FILESIZE; i++)
fprintf(fileOutput, "string[%d] = %13s number[%d] = %3d\n\n", i, str[i], i, number[i]*2);
for (i = 0; i < FILESIZE; i++)
fprintf(fileOutput, "%s ", str[i]);
fprintf(fileOutput, "\n\n");
fclose(fileInput);
fclose(fileOutput);
}
C Example: File R/W, Strings & Array
In Xcode, after copying and pasting the program, follow
the following steps:
1. Drag and drop the input files into the project folder
2. Set Working Directory through: Product > Scheme >
Edit Scheme > Working Directory
3. Build and then run the current scheme
4. Display the output file through: Control Click Project
folder > Add Files to “project folder”……
C Example: File R/W, Strings & Array
FILE: in.txt
FILE: output.txt
The 10
purpose 20
of 30
this 40
project 50
is 60
to 70
have 80
fun 90
:) 100
string[0] =
The
number[0] =
20
string[1] =
purpose
number[1] =
40
string[2] =
of
number[2] =
60
string[3] =
this
number[3] =
80
string[4] =
project
number[4] = 100
string[5] =
is
number[5] = 120
string[6] =
to
number[6] = 140
string[7] =
have
number[7] = 160
string[8] =
fun
number[8] = 180
string[9] =
:)
number[9] = 200
The purpose of this project is to have fun :)
C Example: File R/W, Strings & Array
FILE: input.txt
FILE: output.txt
ELRO 1
Computational 2
Service 3
Company 4
is 5
based 6
in 7
New 8
York 9
City. 10
string[0] =
ELRO
number[0] =
2
string[1] = Computational
number[1] =
4
string[2] =
Service
number[2] =
6
string[3] =
Company
number[3] =
8
string[4] =
is
number[4] =
10
string[5] =
based
number[5] =
12
string[6] =
in
number[6] =
14
string[7] =
New
number[7] =
16
string[8] =
York
number[8] =
18
string[9] =
City.
number[9] =
20
ELRO Computational Service Company is based in New York City.
Sorting Algorithms
and Implementations
Sorting Algorithms
• Selection Sort I
• Bubble Sort
• Selection Sort 2
• Insertion Sort
Sort Main Functions
1.
// This is the main function which can call different sort functions
2.
#include <stdio.h>
3.
int main(int argc, const char * argv[])
4.
{
5.
int i, number;
6.
int a[20];
7.
printf("Number of integers: ");
8.
scanf("%d", &number);
9.
printf("Enter %d integers: ", number);
10.
for (i = 0; i< number; i++)
11.
scanf("%d", &a[i]);
12.
sort(a, number);
13.
for (i = 0; i< number; i++)
14.
printf("%d ", a[i]);
15.
printf("\n");
16.
return 0;
17. }
Selection Sort I
• Selection Sort I compares the element in the first position with the
elements in the rest of the array in order.
• Swap them if the first one is greater than any other element in the
array, and result in the smallest element in the first position.
• Find the second smallest element through the same procedure.
• Continue until the array is sorted
Selection Sort I Example
3
5
1
2
4
3
5
1
2
4
1
5
3
2
4
1
5
3
2
4
1
5
3
2
4
1
3
5
2
4
1
2
5
3
4
1
2
5
3
4
1
2
3
5
4
1
2
3
5
4
1
2
3
4
5
1
2
3
4
5
Selection Sort I Code
1. // Selection Sort: Compare the elements with the elements in the rest of the
2. // array in order. Swap them until the whole array is sorted.
3.
4. void SelectionSort (int a[], int array_size)
5. {
6.
int i, j, temp;
7.
for (i = 0; i < array_size-1; i++)
8.
for (j = i+1; j < array_size; j++)
9.
if (a[i] > a[j])
10.
{
11.
temp = a[i];
12.
a[i] = a[j];
13.
a[j] = temp;
14.
15. }
}
3
5
1
2
4
3
5
1
2
4
1
5
3
2
4
1
5
3
2
4
1
5
3
2
4
1
3
5
2
4
1
2
5
3
4
1
2
5
3
4
1
2
3
5
4
1
2
3
5
4
1
2
3
4
5
1
2
3
4
5
Selection Sort II
• It basically determines the minimum (or maximum) of the list and
swaps it with the element at the index where its supposed to be.
• 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.
Selection Sort II Example
3
5
1
2
4
1
5
3
2
4
1
2
3
5
4
1
2
3
5
4
1
2
3
4
5
1
2
3
4
5
Selection Sort II Code
1.
// Selection Sort: It basically determines the minimum (or maximum) of the list and
2.
// swaps it with the element at the index where its supposed to be.
3.
4.
void SelectionSort (int a[], int array_size)
5.
{
6.
int i;
7.
int j, min, temp;
8.
for (i = 0; i < array_size - 1; i++)
9.
{
10.
min = i;
11.
for (j = i+1; j < array_size; j++)
12.
{
3
5
1
2
4
1
5
3
2
4
1
2
3
5
4
1
2
3
5
4
13.
if (a[j] < a[min])
1
2
3
4
5
14.
min = j;
1
2
3
4
5
15.
}
16.
temp = a[i];
17.
a[i] = a[min];
18.
a[min] = temp;
19.
20. }
}
Bubble Sort
• Bubble Sort works by comparing each element of the list with the
element next to it and swapping them if required.
• When we compare pairs of adjacent elements and none are out of
order, the list is sorted.
• If any are out of order, we must have to swap them to get an ordered
list.
• Bubble sort will make passes though the list swapping any adjacent
elements that are out of order.
Bubble Sort
3
5
1
2
4
3
5
1
2
4
3
1
5
2
4
3
1
2
5
4
3
1
2
4
5
1
3
2
4
5
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
Bubble Sort Code
1. // Bubble Sort: comparing each element of the list with the element
2. // next to it and swapping them if required.
3.
4. void BubbleSort (int a[], int array_size)
5. {
6.
int i, j, temp;
7.
for (i = 0; i < (array_size - 1); ++i)
8.
for (j = 0; j < array_size - 1 - i; ++j )
9.
if (a[j] > a[j+1])
10.
{
3
5
1
2
4
3
5
1
2
4
3
1
5
2
4
3
1
2
5
4
3
1
2
4
5
1
3
2
4
5
1
2
3
4
5
11.
temp = a[j+1];
1
2
3
4
5
12.
a[j+1] = a[j];
1
2
3
4
5
13.
a[j] = temp;
1
2
3
4
5
1
2
3
4
5
14.
15. }
}
Insertion Sort
• Insertion Sort starts from the beginning, traverses through the list and
as you find elements misplaced by precedence you remove them and
insert them back into the right position. Eventually what you have is a
sorted list of elements.
• Adding a new element to a sorted list will keep the list sorted if the
element is inserted in the correct place.
• A single element list is sorted.
• Inserting a second element in the proper place keeps the list sorted.
• This is repeated until all the elements have been inserted into the
sorted part of the list.
Insertion Sort
3
5
1
2
4
3
5
1
2
4
1
3
5
2
4
1
2
3
5
4
1
2
3
4
5
Insertion Sort Code
1. // Insertion Sort: You start from the beginning, traverse through the list
2. // and as you find elements misplaced by precedence you remove them
3. // and insert them back into the right position.
4.
5. void insertionSort (int a[], int array_size)
6. {
7.
int i, j, key;
8.
for (i = 1; i < array_size; i++)
3
5
1
2
4
9.
{
3
5
1
2
4
10.
key = a[i];
1
3
5
2
4
11.
for (j = i; j > 0 && a[j-1] > key; j--)
1
2
3
5
4
1
2
3
4
5
12.
a[j] = a[j-1];
13.
14.
15. }
a[j] = key;
}
Sort Main Functions - Strings
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
// This is the main function which can call different sort functions
#include <stdio.h>
#include <string.h>
#define STRINGLENGTH 15
int main(int argc, const char * argv[])
{
int i, number;
char str[20][STRINGLENGTH];
printf("Number of strings: ");
scanf("%d", &number);
printf("Enter %d strings: ", number);
for (i = 0; i< number; i++)
scanf("%s", str[i]);
SortStr(str, number);
for (i = 0; i< number; i++)
printf("%s ", str[i]);
printf("\n");
return 0;
}
Selection Sort I Code - Strings
1. // Selection Sort: Compare the elements with the elements in the rest of the
2. // array in order. Swap them until the whole array is sorted.
3.
4. void SelectionSort (char str[][STRINGLENGTH], int array_size)
5. {
6.
int i, j;
7.
char temp[STRINGLENGTH];
8.
for (i = 0; i < array_size-1; i++)
9.
for (j = i+1; j < array_size; j++)
10.
if (strcmp(str[i], str[j]) > 0)
11.
{
12.
strcpy(temp, str[i]);
13.
strcpy(str[i], str[j]);
14.
strcpy(str[j], temp);
15.
16. }
}
Searching Algorithms
and Implementations
Searching Algorithms
• Linear Search
• Binary Search
Search Functions
1.
// This is the main function which can call different search functions
2.
#include <stdio.h>
3.
int main()
4.
{
5.
int i, number, key;
6.
int a[20];
7.
printf("Number of integers: ");
8.
scanf("%d", &number);
9.
printf("Enter %d integers: ", number);
10.
for (i = 0; i< number; i++)
11.
scanf("%d", &a[i]);
12.
printf("The array of integers:\n");
13.
for (i = 0; i< number; i++)
14.
printf("%d ", a[i]);
15.
printf("\n");
16.
printf("Enter your search key: ");
17.
scanf("%d", &key);
18.
search (key, a, number);
19.
return 0;
20.
}
Linear Search
• Linear Search is the simplest searching algorithm.
• It uses a loop to sequentially step through an array, starting with the
first element.
• It compares each element with the value being searched for and stops
when that value is found or the end of the array is reached.
Linear Search Code
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
// Linear Search
int LinearSearch (int key, int a[], int array_size)
{
int i, found = 0;
for(i = 0; i < array_size; i++)
{
if (a[i] == key)
{
found = 1;
printf ("%2d] %2d\n\n", i, a[i]);
}
}
if (found == 1)
return 1;
else
{
printf ("Can not find %d\n", key);
return -1;
}
}
Binary Search
• Binary search is much more efficient than the linear search.
• It requires the list to be in order.
• The algorithm starts searching with the middle element.
• If the item is less than the middle element, it starts over searching the
first half of the list.
• If the item is greater than the middle element, the search starts over
starting with the middle element in the second half of the list.
• It then continues halving the list until the item is found.
Binary Search
Binary Search Code
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
// Binary Search:
int binsearch(int x, int v[], int n)
{
int low,high,mid;
low = 0;
high = n - 1;
while(low<=high)
{
mid = (low + high) / 2;
if(x < v[mid])
{
high = mid + 1;
}
else if(x > v[mid])
{
low = mid + 1;
}
else
{
return mid;
}
return -1;
}
}
Algorithms and Programming
• Types of Algorithms
– Brute-Force (or Exhaustive Search)
– Divide and Conquer
– The Greedy Method
– Recursion
• Algorithms of Skyscrapers Project
– Review of Pseudo Code
– Decimal-to-Binary Conversion Algorithm
• Programming: A Crash Course of C
• Sorting Algorithms and Implementations
• Searching Algorithms and Implementations
Q&A