【算法笔记】Some pieces of code
online c programming exerciseshttps://w3resource.com/c-programming-exercises/
online compiler for c：https://www.onlinegdb.com/online_c_compiler
online c formatting:
https://codebeautify.org/c-formatter-beautifier#copy
1 C program for binary search
Write a C program for binary search.
Note: Binary Search : In computer science, a binary search or half-interval search algorithm finds the position of a target value within a sorted array. The binary search algorithm can be classified as a dichotomies divide-and-conquer search algorithm and executes in logarithmic time.
#include <stdio.h>
// Recursive Function- It returns location of x assumiung array arr[l..r] is present, otherwise -1
int binarysearch(int arr[], int l, int r, int x)
{
if (r >= l)
{
int mid = l + (r - l)/2;
// If element is present at middle
if (arr[mid] == x) return mid;
// If element is smaller than middle
if (arr[mid] > x) return binarysearch(arr, l, mid-1, x);
// Else element is in right subarray
return binarysearch(arr, mid+1, r, x);
}
// When element is not present in array
return -1;
}
int main(void)
{
// give function an array to work with
int arr[] = {2, 3, 4, 10, 40};
// get size of array
int n = sizeof(arr)/ sizeof(arr[0]);
//set value to look for
int x = 10;
// set result to what is returned from binarysearch
int result = binarysearch(arr, 0, n-1, x);
// print out result
(result == -1) ? printf("Element is not in the array\n")
: printf("Element is present at index %d\n", result);
return 0;
}
2 selection sort
Write a C program to sort a list of elements using the selection sort algorithm.
According to Wikipedia “In computer science, selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n2) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort”.
Note:
a) To find maximum of elements
b) To swap two elements
#include <stdio.h>
int main() {
int arr[10];
int i, j, N, temp;
/* function declaration */
int find_max(int b[10], int k);
void exchang(int b[10], int k);
printf("Input no. of values in the array : \n");
scanf("%d", & N);
printf("Input the elements one by one: \n");
for (i = 0; i < N; i++) {
scanf("%d", & arr[i]);
}
/* Selection sorting begins */
exchang(arr, N);
printf("Sorted array :\n");
for (i = 0; i < N; i++) {
printf("%d\n", arr[i]);
}
}
/* function to find the maximum value */
int find_max(int b[10], int k) {
int max = 0, j;
for (j = 1; j <= k; j++) {
if (b[j] > b[max]) {
max = j;
}
}
return (max);
}
void exchang(int b[10], int k) {
int temp, big, j;
for (j = k - 1; j >= 1; j--) {
big = find_max(b, j);
temp = b[big];
b[big] = b[j];
b[j] = temp;
}
return;
}
3 bubble sort
Note: Bubble Sort works by repeatedly swapping the adjacent elements if they are in wrong order.
#include <stdio.h>
void bubble_sort(int * x, int n) {
int i, t, j = n, s = 1;
while (s) {
s = 0;
for (i = 1; i < j; i++) {
if (x[i] < x[i - 1]) {
t = x[i];
x[i] = x[i - 1];
x[i - 1] = t;
s = 1;
}
}
j--;
}
}
int main() {
int x[] = {
15,
56,
12,
-21,
1,
659,
3,
83,
51,
3,
135,
0
};
int n = sizeof x / sizeof x[0];
int i;
for (i = 0; i < n; i++)
printf("%d%s", x[i], i == n - 1 ? "\n" : " ");
bubble_sort(x, n);
for (i = 0; i < n; i++)
printf("%d%s", x[i], i == n - 1 ? "\n" : " ");
return 0;
}
4 insertion sort
Write a C program to sort a list of elements using the insertion sort algorithm.
Note:
Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than other algorithms such as quicksort, heapsort, or merge sort.
#include<stdio.h>
int main() {
int arra[10], i, j, n, array_key;
printf("Input no. of values in the array: \n");
scanf("%d", & n);
printf("Input %d array value(s): \n", n);
for (i = 0; i < n; i++)
scanf("%d", & arra[i]);
/* Insertion Sort */
for (i = 1; i < n; i++) {
array_key = arra[i];
j = i - 1;
while (j >= 0 && arra[j] > array_key) {
arra[j + 1] = arra[j];
j = j - 1;
}
arra[j + 1] = array_key;
}
printf("Sorted Array: \n");
for (i = 0; i < n; i++)
printf("%d \n", arra[i]);
}
5 merge sort
Note: Merge sort is an O(n log n) comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output.
#include<stdio.h>
/* Function to merge the two haves arra[l..m] and arra[m+1..r] of array arra[] */
void merge(int arra[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
/* create temp arrays */
int L[n1], R[n2];
/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
L[i] = arra[l + i];
for (j = 0; j < n2; j++)
R[j] = arra[m + 1 + j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arra[k] = L[i];
i++;
} else {
arra[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arra[k] = L[i];
i++;
k++;
}
while (j < n2) {
arra[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arra[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2; //Same as (l+r)/2, but avoids overflow for large l and h
mergeSort(arra, l, m);
mergeSort(arra, m + 1, r);
merge(arra, l, m, r);
}
}
/* Function to print an array */
void print_array(int A[], int size) {
int i;
for (i = 0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}
/* Test above functions */
int main() {
int arra[] = {
125,
181,
130,
25,
61,
887
};
int arr_size = sizeof(arra) / sizeof(arra[0]);
printf("Given array is \n");
print_array(arra, arr_size);
mergeSort(arra, 0, arr_size - 1);
printf("\nSorted array is \n");
print_array(arra, arr_size);
return 0;
}
6 heap sort
Note:
A sorting algorithm that works by first organizing the data to be sorted into a special type of binary tree called a heap.
#include <stdio.h>
int main() {
int arr[10], no, i, j, c, heap_root, temp;
printf("Input number of elements: \n");
scanf("%d", & no);
printf("Input array values one by one :\n ");
for (i = 0; i < no; i++)
scanf("%d", & arr[i]);
for (i = 1; i < no; i++) {
c = i;
do {
heap_root = (c - 1) / 2;
/* to create MAX arr array */
if (arr[heap_root] < arr[c]) {
temp = arr[heap_root];
arr[heap_root] = arr[c];
arr[c] = temp;
}
c = heap_root;
} while (c != 0);
}
printf("Heap array : ");
for (i = 0; i < no; i++)
printf("%d\t ", arr[i]);
for (j = no - 1; j >= 0; j--) {
temp = arr[0];
arr[0] = arr[j];
arr[j] = temp;
heap_root = 0;
do {
c = 2 * heap_root + 1;
if ((arr[c] < arr[c + 1]) && c < j - 1)
c++;
if (arr[heap_root] < arr[c] && c < j) {
temp = arr[heap_root];
arr[heap_root] = arr[c];
arr[c] = temp;
}
heap_root = c;
} while (c < j);
}
printf("\nSorted array : \n");
for (i = 0; i < no; i++)
printf("\t%d", arr[i]);
printf("\n");
}
7 quick sort
Note: Quick sort is a comparison sort, meaning that it can sort items of any type for which a "less-than" relation (formally, a total order) is defined.
Read n values into array and Sort using Quick Sort.
#include<stdio.h>
int n;
int main() {
int arr[30], l, r, i;
void quick_sort(int arr[], int, int);
printf("Input number of elements: \n ");
scanf(" %d", & n);
printf("Input array values one by one: \n");
for (i = 0; i < n; i++)
scanf(" %d", & arr[i]);
l = 0;
r = n - 1;
quick_sort(arr, l, r);
printf("\nThe quick sorted array is: \n ");
for (i = 0; i < n; i++)
printf(" %d", arr[i]);
printf("\n");
}
void quick_sort(int arr[], int low, int high) {
int temp, left, right, x, k;
if (low >= high)
return;
else {
x = arr[low];
right = low + 1;
left = high;
while (right <= left) {
while (arr[right] < x && right <= high) {
right++;
}
while (arr[left] > x && left > low) {
left--;
}
if (right < left) {
temp = arr[right];
arr[right] = arr[left];
arr[left] = temp;
right++;
left--;
}
}
arr[low] = arr[left];
arr[left] = x;
quick_sort(arr, low, left - 1);
quick_sort(arr, left + 1, high);
}
}
8 Shell sort
According to Wikipedia "Shell sort or Shell's method, is an in-place comparison sort. It can be seen as either a generalization of sorting by exchange (bubble sort) or sorting by insertion (insertion sort). The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. Starting with far apart elements can move some out-of-place elements into position faster than a simple nearest neighbor exchange."
#include <stdio.h>
void shell_sort (int *a, int n) {
int h, i, j, t;
for (h = n; h /= 2;) {
for (i = h; i < n; i++) {
t = a[i];
for (j = i; j >= h && t < a[j - h]; j -= h) {
a[j] = a[j - h];
}
a[j] = t;
}
}
}
int main (int ac, char **av) {
int a[] = {4, 65, 2, -31, 0, 99, 2, 83, 782, 1};
int n = sizeof a / sizeof a[0];
int i;
printf("Original Array:\n");
for (i = 0; i < n; i++)
printf("%d%s", a[i], i == n - 1 ? "\n" : " ");
shell_sort(a, n);
printf("\nSorted Array:\n");
for (i = 0; i < n; i++)
printf("%d%s", a[i], i == n - 1 ? "\n" : " ");
return 0;
}
9 radix sort
Note:
Radix sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value.
#include <stdio.h>
int print(int * a, int n) {
int i;
for (i = 0; i < n; i++)
printf("%d\t", a[i]);
}
void radix_sort(int * a, int n) {
int i, b[10], m = 0, exp = 1;
for (i = 0; i < n; i++) {
if (a[i] > m)
m = a[i];
}
while (m / exp > 0) {
int box[10] = {
0
};
for (i = 0; i < n; i++)
box[a[i] / exp % 10]++;
for (i = 1; i < 10; i++)
box[i] += box[i - 1];
for (i = n - 1; i >= 0; i--)
b[--box[a[i] / exp % 10]] = a[i];
for (i = 0; i < n; i++)
a[i] = b[i];
exp *= 10;
}
}
int main() {
int arr[10];
int i, num;
printf("Input number of elements: \n");
scanf("%d", & num);
printf("Input array elements one by one : \n");
for (i = 0; i < num; i++)
scanf("%d", & arr[i]);
printf("Array elements : \n");
print( & arr[0], num);
radix_sort( & arr[0], num);
printf("\nSorted elements :\n ");
print( & arr[0], num);
return 0;
}
10 counting sort
According to Wikipedia "In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to determine the positions of each key value in the output sequence. Its running time is linear in the number of items and the difference between the maximum and minimum key values, so it is only suitable for direct use in situations where the variation in keys is not significantly greater than the number of items. However, it is often used as a subroutine in another sorting algorithm, radix sort, that can handle larger keys more efficiently".
#include <stdio.h>
int counting_sort(int a[], int k, int n) {
int i, j;
int b[15], c[100];
for (i = 0; i <= k; i++)
c[i] = 0;
for (j = 1; j <= n; j++)
c[a[j]] = c[a[j]] + 1;
for (i = 1; i <= k; i++)
c[i] = c[i] + c[i - 1];
for (j = n; j >= 1; j--) {
b[c[a[j]]] = a[j];
c[a[j]] = c[a[j]] - 1;
}
printf("The Sorted array is : ");
for (i = 1; i <= n; i++)
printf("%d,", b[i]);
}
int main() {
int n, k = 0, a[15], i;
printf("Input number of elements: ");
scanf("%d", & n);
printf("Input the array elements one by one: \n");
for (i = 1; i <= n; i++) {
scanf("%d", & a[i]);
if (a[i] > k) {
k = a[i];
}
}
counting_sort(a, k, n);
printf("\n");
return 0;
}
11 two sum
Write a C program to get the indices of the two numbers of a given array of integers, such that the sum of the two numbers equal to a specific target.
Expected Output:
Original Array: 4 2 1 5
Target Value: 7
Indices of the two numbers whose sum equal to target value: 7
1 3
#include <stdio.h>
int main()
{
int arr[]= {2, 3, 4, 10, 40};
int t=12;
int n = sizeof(arr)/ sizeof(arr[0]);
printf("Original Array:");
for (int i = 0; i < n-1; i++) {
printf("%d",arr[i]);
printf(" ");
}
printf("\nTarget Value: %d",t);
printf("\nIndices of the two numbers whose sum equal to target value: %d",t);
for (int i = 0; i < n-1; i++) {
for (int j = i+1; j < n-1; j++){
if(arr[i]+arr[j]==t){
printf("\n %d %d",i,j);
//https://stackoverflow.com/questions/9695902/how-to-break-out-of-nested-loops
i = j = 1000;
break;
}
}
}
return 0;
}
12 brackets check
Write a C programming to check if a given string is valid or not, the string contains the characters '(', ')', '{', '}', '[' and ']'. The string is valid if the open brackets must be closed by the same type of brackets and in correct order.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
static bool is_valid_Parentheses(char *s)
{
int n = 0, cap = 100;
char *tstack = malloc(cap);
while (*s != '\0') {
switch(*s) {
case '(':
case '[':
case '{':
if (n + 1 >= cap) {
cap *= 2;
tstack = realloc(tstack, cap);
}
tstack[n++] = *s;
break;
case ')':
if (tstack[--n] != '(') return false;
break;
case ']':
if (tstack[--n] != '[') return false;
break;
case '}':
if (tstack[--n] != '{') return false;
break;
default:
return false;
}
s++;
}
return n == 0;
}
int main(void)
{
//char **vbracket = "()[]{}";
char **vbracket = "([)]";
printf("%s\n", is_valid_Parentheses(vbracket) ? "true" : "false");
return 0;
}
13 roman number converter
Write a C programming to convert a given roman number to an integer.
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
#include <stdio.h>
#include <stdlib.h>
static int roman_to_integer(char c)
{
switch(c) {
case 'I':
return 1;
case 'V':
return 5;
case 'X':
return 10;
case 'L':
return 50;
case 'C':
return 100;
case 'D':
return 500;
case 'M':
return 1000;
default:
return 0;
}
}
int roman_to_int (char *s)
{
int i, int_num = roman_to_integer(s[0]);
for (i = 1; s[i] != '\0'; i++) {
int prev_num = roman_to_integer(s[i - 1]);
int cur_num = roman_to_integer(s[i]);
if (prev_num < cur_num) {
int_num = int_num - prev_num + (cur_num - prev_num);
} else {
int_num += cur_num;
}
}
return int_num;
}
int main(void)
{
char *str1 = "XIV";
printf("Original Roman number: %s", str1);
printf("\nRoman to integer: %d", roman_to_int(str1));
return 0;
}
