(ALGL5) Decrease & Conquer

Insertion Sort

#include <stdio.h>
#include <math.h>
#define MAX 5

void insertionSort(int arr[])
{
    int i, key, j;
    for (i = 1; i < MAX; i++)
    {
        key = arr[i];
        j = i - 1;

        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

void main()
{
    int i, arr[MAX];

    printf("\n--- ELEMENTS OF ARRAY ---\n");
    for (i = 0; i < MAX; i++)
        scanf("%d", &arr[i]);
    printf("\n");

    printf("\nOriginal Array: ");
    for (i = 0; i < MAX; i++)
        printf("%d ", arr[i]);

    insertionSort(arr);

    printf("\nSorted Array: ");
    for (i = 0; i < MAX; i++)
        printf("%d ", arr[i]);
}

Breadth-First Search

#include <stdio.h>
#define MAX 5

int graph[MAX][MAX] = {
	{1, 0, 1, 1, 0},
	{0, 1, 1, 1, 0},
	{1, 1, 1, 0, 0},
	{1, 0, 0, 0, 1},
	{1, 1, 0, 0, 0},
};
int visited[MAX] = {0, 0, 0, 0, 0};

int queue[MAX] = {0, 0, 0, 0, 0};
int front = 0;
int rear = 0;

void bfs(int i)
{
	for (int j = 0; j < MAX; j++)
	{
		if (graph[i][j] && !visited[j])
		{
			visited[j] = 1;
			printf("%d\t", j);
			queue[rear++] = j;
		}
	}

	if (front <= rear)
		bfs(queue[front++]);
}

void main()
{
	printf("0\t");
	visited[0] = 1;
	bfs(0);
}

Depth-First Search

#include <stdio.h>
#define MAX 4

int graph[MAX][MAX] = {
	{0, 1, 1, 0},
	{1, 0, 0, 0},
	{1, 1, 0, 1},
	{1, 1, 1, 0},
};
int visited[MAX] = {0, 0, 0, 0};

void dfs(int i)
{
	printf("%d ", i);
	visited[i] = 1;
	for (int j = 0; j < MAX; j++)
	{
		if (graph[i][j] && !visited[j])
			dfs(j);
	}
}

void main()
{
	for (int i = 0; i < MAX; i++)
	{
		if (!visited[i])
			dfs(i);
	}
}