C言語の配列とアルゴリズムを練習してみた

# 初めに
配列に関するアルゴリズム、そしてC言語配列の練習度を上げたいと思い、メモを取ってみました。

# 基礎の使い方
## 1次元配列
https://prepinsta.com/c-program/introduction-to-arrays/

```c
#include <stdio.h>
int main(void)
{
  int num;
  printf("Input number of array: ");
  scanf("%d", &num);
  int intArr[num];
  int sum = 0;

  printf("Input value: \n");
  for (int i = 0; i < num; i++)
  {
    scanf("%d", &intArr[i]);
  }

  printf("intArr array: ");
  for (int i = 0; i < num; i++)
  {
    printf("%d ", intArr[i]);
    sum = sum + intArr[i];
  }
  printf("\n");

  for (int i = 0; i < num; i++)
  {
    printf("Address of intArr[%d]: %p\n", i, &intArr[i]);
  }

  printf("Sum of intArr: %d\n", sum);
  printf("Average of intArr: %d\n", sum / num);

  return 0;
}
// intArr array: 10 33 78 56 21
// Address of intArr[0]: 0x7ffd4e6ba640
// Address of intArr[1]: 0x7ffd4e6ba644
// Address of intArr[2]: 0x7ffd4e6ba648
// Address of intArr[3]: 0x7ffd4e6ba64c
// Address of intArr[4]: 0x7ffd4e6ba650
// Sum of intArr: 198
// Average of intArr: 39
```


## 2次元配列
https://prepinsta.com/c-program/two-dimensional-array/

```c
#include <stdio.h>

int main(void)
{
  int num;
  int elementSize;
  printf("Enter number of elements: ");
  scanf("%d", &num);
  printf("Enter size of each element: ");
  scanf("%d", &elementSize);

  int student[num][elementSize];
  int sum = 0;
  for (int i = 0; i < num; i++)
  {
    for (int j = 0; j < elementSize; j++)
    {
      printf("Enter student %d in subject %d, marks : ", i + 1, j + 1);
      scanf("%d", &student[i][j]);
    }
  }

  for (int i = 0; i < num; i++)
  {
    sum = 0;
    for (int j = 0; j < elementSize; j++)
    {
      sum = sum + student[i][j];
    }
    printf("Total marks of student %d is : %d\n", i + 1, sum);
  }

  return 0;
}
// Enter number of elements: 3
// Enter size of each element: 3
// Enter student 1 in subject 1, marks : 66
// Enter student 1 in subject 2, marks : 80
// Enter student 1 in subject 3, marks : 85
// Enter student 2 in subject 1, marks : 78
// Enter student 2 in subject 2, marks : 90
// Enter student 2 in subject 3, marks : 58
// Enter student 3 in subject 1, marks : 67
// Enter student 3 in subject 2, marks : 88
// Enter student 3 in subject 3, marks : 66
// Total marks of student 1 is : 231
// Total marks of student 2 is : 226
// Total marks of student 3 is : 221
```

# ソート（Sort）
## バブルソート（Bubble sort）
https://prepinsta.com/c-program/sorting-of-array/

```c
#include <stdio.h>

int main(void)
{
  int num;
  printf("Enter number of intArray: ");
  scanf("%d", &num);
  int intArray[num];
  int sum;
  int temp;

  for (int i = 0; i < num; i++)
  {
    scanf("%d", &intArray[i]);
  }

  for (int i = 0; i < num; i++)
  {
    for (int j = i + 1; j < num; j++)
    {
      if (intArray[i] > intArray[j])
      {
        temp = intArray[i];
        intArray[i] = intArray[j];
        intArray[j] = temp;
      }
    }
  }

  printf("intArray: ");
  for (int i = 0; i < num; i++)
  {
    printf("%d ", intArray[i]);
  }
  printf("\n");

  return 0;
}
// Enter number of intArray: 5
// 5
// 17
// 3
// 67
// 9
// intArray: 3 5 9 17 67
```

## 波形のようにソートする
https://prepinsta.com/c-program/sort-array-in-waveform/

**O(nLogn)**
```c
#include <stdio.h>

void display(int arr[], int size)
{
  printf("arr: ");
  for (int i = 0; i < size; i++)
  {
    printf("%d ", arr[i]);
  }
  printf("\n");
}

// method1
int main(void)
{
  int arr[] = {10, 5, 7, 9, 1, 8, 6};
  int size = sizeof(arr) / sizeof(arr[0]);
  int temp;

  // step1 sort array
  for (int i = 0; i < size; i++)
  {
    for (int j = i + 1; j < size; j++)
    {
      if (arr[i] > arr[j])
      {
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
    }
  }
  display(arr, size);
  // step2 exchange with left element
  // otherwise it will access invalid memory
  for (int i = 1; i < size; i = i + 2)
  {
    temp = arr[i - 1];
    arr[i - 1] = arr[i];
    arr[i] = temp;
  }
  display(arr, size);

  return 0;
}
// arr: 1 5 6 7 8 9 10
// arr: 5 1 7 6 9 8 10
```

**O(n)**
```c
// method2 O(n)
int main(void)
{
  // int arr[] = {10, 5, 1, 9, 9, 18, 100};
  int arr[] = {10, 5, 1, 9, 9, -1, -5};
  int size = sizeof(arr) / sizeof(arr[0]);
  int temp;

  for (int i = 1; i < size; i = i + 2)
  {
    if (arr[i - 1] > arr[i])
    {
      temp = arr[i];
      arr[i] = arr[i - 1];
      arr[i - 1] = temp;
    }

    if (arr[i - 1] == arr[i])
    {
      temp = arr[i];
      arr[i] = arr[i + 1];
      arr[i + 1] = temp;
    }
    else if (arr[i] == arr[i + 1])
    {
      temp = arr[i];
      arr[i] = arr[i + 2];
      arr[i + 2] = temp;
    }

    if (i < size - 1 && arr[i] < arr[i + 1])
    {
      temp = arr[i];
      arr[i] = arr[i + 1];
      arr[i + 1] = temp;
    }
  }
  display(arr, size);

  return 0;
}
// arr: 5 10 1 18 9 100 9
// arr: 5 10 1 9 -1 9 -5
```

# 回転（Rotation）
https://prepinsta.com/c-program/array-rotation/

```c
#include <stdio.h>

void leftRotateOne(int arr[], int size)
{
  int temp = arr[0];
  for (int i = 0; i < size; i++)
  {
    arr[i] = arr[i + 1];
  }
  arr[size - 1] = temp;
}

void leftRotate(int arr[], int round, int size)
{
  for (int i = 0; i < round; i++)
  {
    leftRotateOne(arr, size);
  }
}

void rightRotateOne(int arr[], int size)
{
  int temp = arr[size - 1];
  for (int i = size - 1; i >= 0; i--)
  {
    arr[i] = arr[i - 1];
  }
  arr[0] = temp;
}

void rightRotate(int arr[], int round, int size)
{
  for (int i = 0; i < round; i++)
  {
    rightRotateOne(arr, size);
  }
}

void display(int arr[], int size)
{
  printf("array: ");
  for (int i = 0; i < size; i++)
  {
    printf("%d ", arr[i]);
  }
  printf("\n");
}

int main(void)
{
  int arr[] = {10, 20, 30, 40, 50, 60, 70};
  int size = sizeof(arr) / sizeof(arr[0]);

  display(arr, size);
  leftRotate(arr, 2, size);
  display(arr, size);

  rightRotate(arr, 2, size);
  display(arr, size);

  return 0;
}
// array: 10 20 30 40 50 60 70
// array: 30 40 50 60 70 10 20
// array: 10 20 30 40 50 60 70
```

# 反転（Reverse）
https://prepinsta.com/c-program/reverse-of-an-array/

```c
#include <stdio.h>

void display(int arr[], int size)
{
  printf("arr: ");
  for (int i = 0; i < size; i++)
  {
    printf("%d ", arr[i]);
  }
  printf("\n");
}

int main(void)
{
  int arr[] = {11, 22, 33, 44, 55, 66, 77, 88, 99};
  int size = sizeof(arr) / sizeof(arr[0]);
  int temp;

  display(arr, size);
  for (int i = 0; i < (size / 2); i++)
  {
    temp = arr[i];
    // fold, the first one <-> the last one
    arr[i] = arr[size - 1 - i];
    arr[size - 1 - i] = temp;
  }
  display(arr, size);

  return 0;
}
// arr: 11 22 33 44 55 66 77 88 99
// arr: 99 88 77 66 55 44 33 22 11
```

# ペア探し（Pairs）
https://prepinsta.com/c-program/find-pairs-in-array-with-given-sum/

```c
#include <stdio.h>

int main(void)
{
  int arr[] = {10, 15, 20, 25, 30, 40, 50, 35, 45};
  int size = sizeof(arr) / sizeof(arr[0]);
  int check;
  int sum = 0;
  int count = 0;

  printf("Enter check value: ");
  scanf("%d", &check);
  for (int i = 0; i < size; i++)
  {
    for (int j = i + 1; j < size; j++)
    {
      sum = arr[i] + arr[j];
      if (sum == check)
      {
        printf("[%d %d]\n", arr[i], arr[j]);
        count++;
      }
    }
  }
  printf("Total number of pairs: %d\n", count);

  return 0;
}
// Enter check value: 50
// [10 40]
// [15 35]
// [20 30]
// Total number of pairs: 3

// Enter check value: 35
// [10 25]
// [15 20]
// Total number of pairs: 2
```

# 出現頻度（Majority）
https://prepinsta.com/c-program/majority-element-in-an-array/

```c
#include <stdio.h>

#define MAX 10

int index = 0;
int occurred = 1;
int total = 0;

void findMajority(int arr[], int size)
{
  int temp;
  for (int i = 0; i < size; i++)
  {
    temp = arr[i];
    for (int j = i + 1; j < size; j++)
    {
      if (arr[j] == temp)
      {
        occurred++;
      }
    }
    // if occurs times > current total
    if (occurred > total)
    {
      total = occurred;
      index = i;
    }
    // reset
    occurred = 1;
  }
  if (total < 2)
  {
    printf("No majority element found\n");
  }
  else
  {
    printf("Majority element is %d, occurred %d times\n", arr[index], total);
  }
}

void display(int arr[], int size)
{
  printf("Array: ");
  for (int i = 0; i < size; i++)
  {
    printf("%d ", arr[i]);
  }
  printf("\n");
}

int main(void)
{
  // int arr[] = {1, 2, 1, 2, 1, 4, 5, 1, 2};
  int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
  int size = sizeof(arr) / sizeof(arr[0]);

  display(arr, size);
  findMajority(arr, size);
}
// Array: 1 2 1 2 1 4 5 1 2
// Majority element is 1, occurred 4 times

// Array: 1 2 3 4 5 6 7 8
// No majority element found
```

# ボイヤー・ムーア法（Boyer-Moore）
https://www.geeksforgeeks.org/boyer-moore-algorithm-for-pattern-searching/

文字列検索アルゴリズムというのは今まであまり触れていないジャンルだったので理解することさえ難しかったです。少し調べたらこんなにたくさんあったんですね...。

http://www-igm.univ-mlv.fr/~lecroq/string/index.html


GeeksforGeeks文章のデモコード、自分が読みやすくなるように書き直してみたけど少し冗長になってしまいました。

```: pattern table
- 0  1  2  3 ... 65  66  67  68  69 ... -
 -1 -1 -1 -1 ... 0   1   2  -1   -1 ...
                 A   B   C
```
```
  ↓ shift index
- 0 1  2  3 4 5 6 7 8 9 -
  L O 'P' I A A A B C D       'P' and 'C' doesn't match,
  A B 'C'                     'P' is not any character in pattern => return -1
- 0 1  2  3 4 5 6 7 8 9 -     next shift index is (0 + (2 - (-1)))
       ↑ pattern's last index (2)
```

```
        ↓ shift index
- 0 1 2 3 4  5  6 7 8 9 -      'A' and 'C' doesn't match,
  L O P I A 'A' A B C D        but 'A' is one character in pattern.
        A B 'C'               from 'A' to the last one in pattern table is 2 => return 2
- 0 1 2 3 4  5  6 7 8 9 -      next shift index is (3 + (2 - 0))
```

```
            ↓ shift index
- 0 1 2 3 4 5 6  7  8 9 -      'B' and 'C' doesn't match,
  L O P I A A A 'B' C D        but 'B' is one character in pattern.
            A B 'C'            from 'A' to the last one in pattern is 1 => return 1
- 0 1 2 3 4 5 6  7  8 9 -      next shift index is (5 + (2 - 1))
```

```
               ↓ shift index
- 0 1 2 3 4 5  6   7   8  9 -      'C' and 'C' matches, pattern last index -1,
  L O P I A A 'A' 'B' 'C' D        'B' and 'B' matches, pattern last index -1,
              'A' 'B'  C           'A' and 'A' matches, pattern last index -1,
- 0 1 2 3 4 5  6   7   8  9 -      pattern last index = -1, pattern occurs at shift at 6
```

```c
#include <stdio.h>
#include <string.h>
#include <limits.h>

#define NO_OF_CHARS 256 //  extended ASCII char set

// utility
int getMax(int a, int b)
{
  return (a > b) ? a : b;
}

// create table
void badCharHeuristic(char *pattern, int size, int badChar[NO_OF_CHARS])
{
  for (int i = 0; i < NO_OF_CHARS; i++)
  {
    badChar[i] = -1;
  }

  for (int i = 0; i < size; i++)
  {
    badChar[(int)pattern[i]] = i;
  }

  // printf("badChar : ");
  // for (int i = 0; i < NO_OF_CHARS; i++)
  // {
  //   printf("%d ", badChar[i]);
  //   if (badChar[i] >= 0)
  //   {
  //     printf("\n i is : %d\n", i);
  //   }
  // }
  // printf("\n");
}

void boyerMooreSearch(char *text, char *pattern)
{
  int patternLen = strlen(pattern);
  int textLen = strlen(text);
  int badChar[NO_OF_CHARS];

  // create pattern table
  badCharHeuristic(pattern, patternLen, badChar);
  int shift = 0; // shift pattern by this index

  // if pattern length wasn't over text length
  // or shift index didn't go over the valid index in text
  while ((textLen - patternLen) >= shift)
  {
    int patternLastIndex = patternLen - 1;

    // check pattern here
    // start from the last index to the first index
    while (patternLastIndex >= 0 && pattern[patternLastIndex] == text[shift + patternLastIndex])
    {
      patternLastIndex--;
    }

    if (patternLastIndex < 0)
    {
      // if lastIndex is -1, it matches
      printf("pattern occurs at shift %d\n", shift);
      // for next occurrence
      // if the current last location doesn't go over text length return (pattern length +1)
      // note: pattern length is the end of the current last location, we can go on next index by plus 1
      shift += (shift + patternLen < textLen) ? patternLen - badChar[(int)text[shift + patternLen]] : 1;
      // shift index is equal or greater than text length, return 1
    }
    else
    {
      // otherwise, let shift index plus reducing pattern length
      //  or at least 1
      shift = shift + getMax(1, patternLastIndex - badChar[(int)text[shift + patternLastIndex]]);
      // A B C
      // 0 1 2, or -1
      // 2 1 0, or 3 // patternLastIndex - badChar[(int)text[shift + patternLastIndex]]
      // 2 1 1, or 3 // getMax(...)
    }
  }
}

int main(void)
{
  char text[] = "LOPIAAABCD";
  char pattern[] = "ABC";
  boyerMooreSearch(text, pattern);

  return 0;
}
// pattern occurs at shift 6
```

`#define NO_OF_CHARS 256`を使う理由は↓

https://www.asciitable.com/


# 連続した最大部分配列和
https://prepinsta.com/c-program/largest-sum-contigous-subarray/

**kadaneアルゴリズム**
- 連続した二つの要素が負数の場合は考慮しない、リセットする。
- 今までの最大和`result`より`temp`が大きい場合は、`temp`の値が最大和`result`に入れる。

```c
#include <stdio.h>

int maxSubArraySum(int arr[], int size)
{
  int temp = 0;
  int result = 0;
  for (int i = 0; i < size; i++)
  {
    temp += arr[i];
    // if sum is less than 0, reset
    if (temp < 0)
    {
      temp = 0;
    }

    if (temp > result)
    {
      result = temp;
    }
  }
  return result;
}

int main(void)
{
  // int arr[] = {-1, 8, 1, -7, -1, 5, 1, -3};
  int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
  int size = sizeof(arr) / sizeof(arr[0]);
  printf("Largest sum with contiguous sub-array is %d\n", maxSubArraySum(arr, size));

  return 0;
}
```
https://prepinsta.com/c-program/size-of-sub-array-with-max-sum/

```c
#include <stdio.h>

int result = 0;
int startIndex = 0;
int endIndex = 0;

int maxSubArraySum(int arr[], int size)
{
  int tempValue = 0;
  int tempIndex = 0;

  for (int i = 0; i < size; i++)
  {
    tempValue += arr[i];
    if (tempValue < 0)
    {
      tempValue = 0;
      tempIndex = i + 1;
    }

    if (tempValue > result)
    {
      result = tempValue;
      startIndex = tempIndex;
      endIndex = i;
    }
  }
  return endIndex - startIndex + 1;
}

int main(void)
{
  // int arr[] = {-7, 3, 4, -1, -12, 1, -9, -3};
  int arr[] = {-1, 4, -1, 3, -6};
  int size = sizeof(arr) / sizeof(arr[0]);
  printf("Length of sub-array with maximum sum is %d, start from index %d, the sum is %d\n", maxSubArraySum(arr, size), startIndex, result);

  return 0;
}
// Length of sub-array with maximum sum is 3, start from index 1, the sum is 6
```

# 指定の長さで配列最大和を求める
https://prepinsta.com/c-program/maximum-average-sub-array-of-k-length/

- 連続和の配列を作る。
- 長さを起点インデックスとし、最大和が続く配列ではインデックスが`+1`たびに一番古いインデックスの要素の値を引く。

```
  0   1    2   3   4   5
 -1, 10, -15, -9, 16, 35   original array
 -1,  9,  -6, 15,  1, 36   continuous sum arry
```

```
              ↓ current sumLastIndex
  0   1   2   3   4   5
 -1,  9, -6, 15,  1, 36    continuous sum arry
 ‾‾  ‾‾  ‾‾  ‾‾            currentSum = 15
```

```
                  ↓ current sumLastIndex
  0   1   2   3   4   5
 -1,  9, -6, 15,  1, 36    continuous sum arry
     ‾‾  ‾‾  ‾‾  ‾‾        currentSum = 15 - (-1)
```
```
                      ↓ current sumLastIndex
  0   1   2   3   4   5
 -1,  9, -6, 15,  1, 36    continuous sum arry
         ‾‾  ‾‾  ‾‾  ‾‾    currentSum = 36 - 9
```

```c
#include <stdio.h>

int findMaxAverage(int arr[], int size, int range)
{
  if (range > size)
  {
    return -1;
  }
  int *sum = arr;

  // put continuous sum to *sum
  for (int i = 1; i < size; i++)
  {
    sum[i] = sum[i - 1] + arr[i];
  }

  // printf("sum : ");
  // for (int i = 0; i < size; i++)
  // {
  //   printf("%d ", sum[i]);
  // }
  // printf("\n");
  // // sum : -1 9 -6 -15 1 36

  int sumLastIndex = range - 1;   // 0 - range
  int sumMax = sum[sumLastIndex]; // sumMax start from kth(range)

  // i start from sumLastIndex + 1
  for (int i = range; i < size; i++)
  {
    int currentSum = sum[i] - sum[i - range];
    if (currentSum > sumMax)
    {
      sumMax = currentSum;
      sumLastIndex = i;
    }
  }
  return sumLastIndex - range + 1;
}

int main(void)
{
  // int arr[] = {-1, 10, -15, -6, 50, 3};
  // int arr[] = {1, 12, -5, -6, 50, 3};
  int arr[] = {-1, 10, -15, -9, 16, 35};

  int range = 4;
  int size = sizeof(arr) / sizeof(arr[0]);
  printf("The maximum average sub-array of length %d begins at index %d\n", range, findMaxAverage(arr, size, range));

  return 0;
}
// The maximum average sub-array of length 4 begins at index 2
```


# 指定された値により部分配列を特定する
https://prepinsta.com/c-program/sub-array-with-given-sum/
```c
#include <stdio.h>

void subArraySum(int arr[], int size, int givenSum)
{
  int currentSum = 0;
  for (int i = 0; i < size; i++)
  {
    currentSum = arr[i];
    for (int j = i + 1; j <= size; j++)
    {
      if (currentSum == givenSum)
      {
        printf("Sum found between indexes %d and %d\n", i, j - 1);
        return;
      }
      if (currentSum > givenSum || j == size)
      {
        break;
      }
      currentSum = currentSum + arr[j];
    }
  }
  printf("No matched sub-array found");
}

int main(void)
{
  // int arr[] = {1, 4, 0, 0, 3, 10, 5};
  int arr[] = {1, 6, 0, 0, 13, 20, 5};
  int size = sizeof(arr) / sizeof(arr[0]);
  int sum = 7;
  subArraySum(arr, size, sum);

  return 0;
}
// Sum found between indexes 1 and 4
// Sum found between indexes 0 and 1
```

# 頻出度順（Frequency）
https://prepinsta.com/data-structures/sort-elements-by-frequency-of-occurrences-code/

https://stackoverflow.com/questions/3911400/how-to-pass-2d-array-matrix-in-a-function-in-c

頻出度とは個人の中でかなり大事なテーマです。トレンドワードや量による順序づけなどあらゆる面において大事なアルゴリズムだと思います。
コードを理解しつつ自分の考えた方向へ変えようとしたんですが、どうしてもひと手間かける必要になってしまってなかなか難しかったです。自分の能力のなさに感じます...。
```c
#include <stdio.h>

int input[] = {1, 2, 3, 3, 2, 4, 1, 4, 4, 5};
int size = sizeof(input) / sizeof(input[0]);

void display2D(int x, int y, int arr[x][y])
{
  printf("arr : ");
  for (int i = 0; i < x; i++)
  {
    printf("[%d %d] ", arr[i][0], arr[i][1]);
  }
  printf("\n");
}

int main(void)
{
  int temp = 0;
  int count = 0;
  int independentElem = 0;

  int arr[size][2];
  int map[size][2];

  for (int i = 0; i < size; i++)
  {
    arr[i][0] = input[i];
    arr[i][1] = 0;
  }
  display2D(size, 2, arr);
  // arr : [1 0] [2 0] [3 0] [3 0] [2 0] [4 0] [1 0] [4 0] [4 0] [5 0]

  for (int i = 0; i < size; i++)
  {
    // skip the counted elements
    if (arr[i][1])
    {
      continue;
    }

    count = 1; // first occurrence
    for (int j = i + 1; j < size; j++)
    {
      if (arr[i][0] == arr[j][0])
      {
        arr[j][1] = 1; // for skipping the counted elements
        count++;
      }
    }

    map[independentElem][0] = arr[i][0];
    map[independentElem][1] = count;
    independentElem++;
  }
  display2D(size, 2, map);
  // arr : [1 2] [2 2] [3 2] [4 3] [5 1] [0 0] [0 0] [0 0] [0 0] [0 0]

  size = independentElem;
  for (int i = 0; i < size - 1; i++)
  {
    temp = map[i][1];
    for (int j = i + 1; j < size; j++)
    {
      if (temp < map[j][1])
      {
        temp = map[j][1];
        map[j][1] = map[i][1];
        map[i][1] = temp;

        temp = map[j][0];
        map[j][0] = map[i][0];
        map[i][0] = temp;
      }
    }
  }
  display2D(size, 2, map);
  // arr : [4 3] [2 2] [3 2] [1 2] [5 1]

  printf("Result : ");
  for (int i = 0; i < size; i++)
  {
    for (int j = 0; j < map[i][1]; j++)
    {
      printf("%d ", map[i][0]);
    }
  }
  printf("\n");

  return 0;
}
// Result : 4 4 4 2 2 3 3 1 1 5
```

# ピタゴラス数／三平方の定理（Pythagorean triple）
https://prepinsta.com/c-program/pythagorean-triples/

```c
#include <stdio.h>

int isTriple(int arr[], int size)
{
  int x = 0;
  int y = 0;
  int z = 0;
  for (int i = 0; i < size; i++)
  {
    for (int j = i + 1; j < size; j++)
    {
      for (int k = j + 1; k < size; k++)
      {
        x = arr[i] * arr[i];
        y = arr[j] * arr[j];
        z = arr[k] * arr[k];
        if (x == y + z || y == x + z || z == x + y)
        {
          printf("%d, %d, %d is triple\n", arr[i], arr[j], arr[k]);
          return 1;
        }
      }
    }
  }
  return 0;
}

int main(void)
{
  // int arr[] = {3, 4, 6, 5, 7, 8};
  int arr[] = {10, 4, 6, 12, 5};
  int size = sizeof(arr) / sizeof(arr[0]);
  if (!isTriple(arr, size))
  {
    printf("No triples found\n");
  }
  return 0;
}
// No triples found
```

# 再順序付けする（Reorder）
https://prepinsta.com/data-structures/reorder-array-using-given-indexes/

```c
#include <stdio.h>

void reorder(int arr[], int index[], int size, int result[])
{
  for (int i = 0; i < size; i++)
  {
    result[index[i]] = arr[i];
  }
}

int main(void)
{
  int arr[] = {4, 2, 1, 3};
  int index[] = {3, 1, 2, 0};
  int size = sizeof(arr) / sizeof(arr[0]);
  int result[size];
  reorder(arr, index, size, result);

  printf("Result : ");
  for (int i = 0; i < size; i++)
  {
    printf("%d ", result[i]);
  }
  printf("\n");

  return 0;
}
// Result : 3 2 1 4
```

# 二つの配列を合併させる（Merge）
https://prepinsta.com/data-structures/merging-two-sorted-arrays/

```c
#include <stdio.h>

void display(int arr[], int size)
{
  printf("Arr : ");
  for (int i = 0; i < size; i++)
  {
    printf("%d ", arr[i]);
  }
  printf("\n");
}

void sortArr(int arr[], int size)
{
  int temp = 0;
  for (int i = 0; i < size; i++)
  {
    for (int j = i + 1; j < size; j++)
    {
      if (arr[i] > arr[j])
      {
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
    }
  }
}

void merge(int arr1[], int arr2[], int size1, int size2, int arr3[])
{
  int i = 0;
  int j = 0;
  int k = 0;

  while (i < size1 && j < size2)
  {
    if (arr1[i] < arr2[j])
    {
      arr3[k++] = arr1[i++];
    }
    else
    {
      arr3[k++] = arr2[j++];
    }
  }

  // fpr checking last one
  while (i < size1)
  {
    arr3[k++] = arr1[i++];
  }
  while (j < size2)
  {
    arr3[k++] = arr2[j++];
  }
}

int main(void)
{
  int arr1[] = {6, 1, 8, 3};
  int arr2[] = {2, 1, 4, 2};

  int size1 = sizeof(arr1) / sizeof(arr1[0]);
  int size2 = sizeof(arr2) / sizeof(arr2[0]);

  int arr3[size1 + size2];
  sortArr(arr1, size1);
  sortArr(arr2, size2);
  merge(arr1, arr2, size1, size2, arr3);
  display(arr3, size1 + size2);

  return 0;
}
```

# その他
https://prepinsta.com/data-structures/segregate-0s-1s-and-2s-in-an-array/

```c
#include <stdio.h>

int main(void)
{
  int num = 0;
  printf("Enter number of array : ");
  scanf("%d", &num);
  int count[3];
  int arr[num];

  for (int i = 0; i < num; i++)
  {
    scanf("%d", &arr[i]);
    count[arr[i]]++;
  }

  for (int i = 0; i < 3; i++)
  {
    for (int j = 0; j <= count[i]; j++)
    {
      printf("%d ", i);
    }
  }
  printf("\nend\n");
  return 0;
}
// Enter number of array : 5
// 1
// 0
// 1
// 0
// 2
// 0 0 0 1 1 1 2 2
// end
```

https://prepinsta.com/data-structures/minimum-number-of-merge-operations-to-make-an-array-palindrome/

https://prepinsta.com/c-program/find-zeros-to-be-flipped-so-that-number-of-consecutive-1s-is-maximized/