(ALGL6) Divide & Conquer

Merge Sort

#include <stdio.h>
#include <stdlib.h>

#define N 10

void merge(int A[], int aLen, int B[], int bLen, int C[], int cLen)
{
	int i = 0, j = 0, k = 0;

	while ((i < bLen) && (j < cLen))
	{
		if (B[i] < C[j])
		{
			A[k] = B[i];
			i++;
		}
		else
		{
			A[k] = C[j];
			j++;
		}
		k++;
	}

	while (j < cLen)
	{
		A[k] = C[j];
		j++;
		k++;
	}

	while (i < bLen)
	{
		A[k] = B[i];
		i++;
		k++;
	}
}

void mergeSort(int arr[], int n)
{
	// exit condition
	if (n <= 1)
		return;

	// make two arrays of half the size
	int B[n / 2], C[n / 2];

	for (int i = 0; i < n / 2; i++)
		B[i] = arr[i];
	mergeSort(B, n / 2);

	for (int i = n / 2; i < n; i++)
		C[i - n / 2] = arr[i];
	mergeSort(C, n / 2);

	merge(arr, n, B, n / 2, C, n / 2);
}

void main()
{
	int arr[10] = {2, 5, 1, 3, 7, 6, 4, 9, 8, 10};
	int n = 10;

	printf("\n--- INPUT ARRAY ---\n");
	for (int i = 0; i < n; i++)
		printf("%d ", arr[i]);

	mergeSort(arr, n);

	printf("\n--- SORTED ARRAY ---\n");
	for (int i = 0; i < n; i++)
		printf("%d ", arr[i]);
}

--- INPUT ARRAY ---
2 5 1 3 7 6 4 9 8 10 
--- SORTED ARRAY ---
1 2 3 4 5 6 7 8 9 10

Quick Sort

#include <stdio.h>
#include <stdlib.h>

void swap(int *x, int *y)
{
	int temp = *x;
	*x = *y;
	*y = temp;
}

int partition(int arr[], int start, int end)
{
	int pivot = arr[end];
	int i = start - 1;

	for (int j = start; j < end; j++)
	{
		if (arr[j] < pivot)
		{
			i++;
			swap(&arr[i], &arr[j]);
		}
	}

	i++;
	swap(&arr[i], &arr[end]);

	return i;
}

void quickSort(int arr[], int start, int end)
{
	if (end <= start)
		return;

	int pivot = partition(arr, start, end);
	quickSort(arr, start, pivot - 1);
	quickSort(arr, pivot + 1, end);
}

void main()
{
	int arr[10] = {2, 5, 1, 3, 7, 6, 4, 9, 8, 10};
	int n = 10;

	printf("\n--- INPUT ARRAY ---\n");
	for (int i = 0; i < n; i++)
		printf("%d ", arr[i]);

	quickSort(arr, 0, n - 1);

	printf("\n--- SORTED ARRAY ---\n");
	for (int i = 0; i < n; i++)
		printf("%d ", arr[i]);
}

--- INPUT ARRAY ---
2 5 1 3 7 6 4 9 8 10 
--- SORTED ARRAY ---
1 2 3 4 5 6 7 8 9 10