[CS50] week 3 - アルゴリズム

初めに

今回はアルゴリズムの基礎への理解を深めるために、C言語で練習コードを書いてみました。

（映像からいろいろヒントを得たが、今までの経験から解釈したり、実際書くと分からないところもあって以前の練習や調べた文章を参考しながら書いていました。）

week3

C言語

JavaScript

Memo

• データ構造とアルゴリズムを勉強すべき理由：

  • Data Search
  • Processor speed
  • Multiple requests

• アルゴリズムの応用面：

  • 探索（Search）
  • ソート（Sort）
  • 挿入（Insert）
  • アップデート（Update）
  • 削除（Delete）

• 時間計算量：

  • O(n)：一重ループ。
  • O(n^2)：二重ループ。
    • （多重ループ→O(n^n)）
  • O(log n)：二分探索法。
  • O(n log n)：一重ループに加えて二分探索の再帰で改良した方法。

• 基本整列アルゴリズム：

  • 選択ソート
  • バブルソート
  • 挿入ソート

• 高速整列アルゴリズム：

  • マージソート
  • ヒープソート（今回の練習では書いていません）
  • クイックソート
  • シェルソート（今回の練習では書いていません）

線型探索（Linear Search）

• 時間計算量（Worst/Best）：O(n)/Ω(1)

概念：

• 未ソート／ソート済みのデータからある要素を特定する。

映像内容のまとめ：

• 配列のインデックスを通して順番通りに走査する。

// linear search
#include <stdio.h>
#define getLength(x) (sizeof(x) / sizeof((x)[0]))

void linear(int *data, int length, int target);

int main(void)
{
  int data1[] = {-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  int data2[] = {1, -5, 7, 5, 2, 6, 2, 1, 3, -2, 0};
  int target;
  printf("Which element do you want to find?\n");
  scanf("%d", &target);

  printf("in data1\n");
  linear(data1, getLength(data1), target);
  printf("in data2\n");
  linear(data2, getLength(data2), target);

  return 0;
}

void linear(int *data, int length, int target)
{
  for (int i = 0; i < length; i++)
  {
    if (data[i] == target)
    {
      printf("target %d index is %d\n", target, i);
    }
  }
}

二分探索（Binary Search）

• 時間計算量（Worst/Best）：O(log n)/Ω(1)

概念：

• ソート済みの配列を分割そして征服する（divide and conquer）。
• 毎回の探索では範囲を半分にする。（半分の要素を捨てる）

映像内容のまとめ：

• 現在の配列の中間位置を算出する。
• 探索対象（値）がちょうど中間位置にある値であれば探索終了。
• 探索対象＞中間位置の値⇒中間位置より左にある全て要素を無視し、右にある範囲で探索再開。
• 探索対象＞中間位置の値⇒中間位置より右にある全て要素を無視し、左にある範囲で探索再開。
• 探索する配列のサイズが0になると元の配列には該当要素がないことを意味する。

// binary search
#include <stdio.h>
#include <math.h>

int findTarget(int *data, int target, int start, int end);

int main(void)
{
  int data[] = {-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  int length = sizeof(data) / sizeof(data[0]);
  int completed = -1;
  int target;

  printf("Which element do you want to find?");
  scanf("%d", &target);

  while (completed == -1)
  {
    int result = findTarget(data, target, 0, length - 1);
    if (result > -1)
    {
      printf("Element index is %d\n", result);
      completed = result;
    }
    else
    {
      printf("Can not find target\n");
      completed = result;
    }
  }
  return 0;
}

int findTarget(int *data, int target, int start, int end)
{
  // last element
  if (end - start == 1 && data[end] == target)
  {
    return end;
  }
  // there is no element in data array
  if (end - start == 1 && data[start] != target && data[end] != target)
  {
    return -2;
  }

  int middle = start + floor((end - start) / 2);

  if (target > data[middle])
  {
    // printf("middle is %d\n", middle);
    return findTarget(data, target, middle, end);
  }
  else if (target < data[middle])
  {
    // printf("middle is %d\n", middle);
    return findTarget(data, target, start, middle);
  }
  else
  {
    return middle;
  }
}

選択ソート（Selection Sort）

• 時間計算量（Worst/Best）：O(n^2)/Ω(n^2)

概念：

• 現在の配列のなか、一番小さい値を見つけ出し先頭に置く。
• 毎回現在の配列から一番小さい値を見つけ出すことで、次回の走査では開始インデックスは+1、長さが-1。

映像内容のまとめ：

• 毎回の走査で一番小さい値を特定する。
• 一番小さい値を開始インデックスへ移動する。
• 開始インデックスは+1、長さが-1。
• 長さが1（要素が自分だけ残っている）場合は終了。

// selection sort
#include <stdio.h>

int main(void)
{
  int data[] = {9, 8, 7, 6, 5, 5, 4, 3, 2, 1, 0, -1};
  int length = sizeof(data) / sizeof(data[0]);
  int smallest;
  int index;

  for (int i = 0; i < length; i++)
  {
    smallest = data[i];
    index = i;
    for (int j = i + 1; j < length; j++)
    {
      if (data[j] < smallest)
      {
        smallest = data[j];
        index = j;
      }
    }
    data[index] = data[i];
    data[i] = smallest;
  }

  printf("After: ");
  for (int i = 0; i < length; i++)
  {
    printf("%d", data[i]);
  }

  printf("\n");
  return 0;
}
// After: -101234556789

バブルソート（Bubble Sort）

• 時間計算量（Worst/Best）：O(n^2)/Ω(n)

概念：

• 隣り合う要素と比較し交換していくなか、一番大きい値を現在配列の最後尾に置く。
• 毎回現在の配列から一番大きい値を見つけ出すことで、次回の走査では長さが-1。

映像内容のまとめ：

• swap counter（交換回数） を設置する。
• swap counterが0になるまで、今の要素と次の要素と比較する。
• 今の要素＝次の要素⇒交換か次に比べるインデックスだけ変える。
• 今の要素＞次の要素⇒互いにインデックス交換。
• 今の要素＜次の要素⇒次に比べるインデックスだけ変える。
• 毎回の走査が終わると配列の長さを-1。
• 以上を繰り返してswap counterが0になったら終了。

// bubble sort
#include <stdio.h>

int main(void)
{
  int data[] = {9, 8, 7, 6, 5, 5, 4, 3, 2, 1, 0, -1};
  int length = sizeof(data) / sizeof(data[0]);
  int counter = length;
  int temp;

  for (int i = length; i >= 0; i--)
  {
    for (int j = 1; j < i; j++)
    {
      temp = data[j - 1];
      if (data[j - 1] > data[j])
      {
        data[j - 1] = data[j];
        data[j] = temp;
      }
    }
  }

  printf("After: ");
  for (int i = 0; i < length; i++)
  {
    printf("%d", data[i]);
  }

  printf("\n");
  return 0;
}
// After: -101234556789

挿入ソート（Insertion Sort）

• 時間計算量（Worst/Best）：O(n^2)/Ω(n)

概念：

• 左側にあるソート済み要素と、右側にある未ソート要素と大小比較して挿入する。

映像内容のまとめ：

• 開始インデックスは1、常に左側の配列の要素と比べる。
• 左側の要素＞今の要素⇒今の要素が左側へ移動する。
• 左側の要素＜今の要素⇒次のインデックスのループへ。

// insertion sort
#include <stdio.h>

int main(void)
{
  int data[] = {9, 8, 7, 6, 5, 5, 4, 3, 2, 1, 0, -1};
  int length = sizeof(data) / sizeof(data[0]);
  int temp;
  int index;

  for (int i = 1; i < length; i++)
  {
    temp = data[i];
    for (int j = i - 1; j >= 0; j--)
    {
      if (data[j] > temp)
      {
        data[j + 1] = data[j];
        index = j;
      }
    }
    data[index] = temp;

    // printf("Current: ");
    // for (int k = 0; k < length; k++)
    // {
    //   printf("%d", data[k]);
    // }
    // printf("\n");
  }

  printf("After: ");
  for (int i = 0; i < length; i++)
  {
    printf("%d", data[i]);
  }

  printf("\n");
  return 0;
}
// After: -101234556789

再帰（Recursion）

概念：

• 同じ問題に何度も遭遇する可能性があれば、自分（関数）を呼び出すことで問題がなくなるまで同じ処理を行う。
• 問題を集約する。そして終了条件を設ける。

// recurison sort
#include <stdio.h>

int factorial(int num);

int main(void)
{
  int n;
  printf("n is: \n");
  scanf("%d", &n);

  printf("The sum is %d\n", factorial(n));
  return 0;
}

int factorial(int num)
{
  if (num == 1)
  {
    return 1;
  }
  else
  {
    return num * factorial(num - 1);
  }
}

int collatz(int num);

int main(void)
{
  int n;
  printf("n is: \n");
  scanf("%d", &n);

  printf("The result is %d\n", collatz(n));
  return 0;
}

int collatz(int num)
{
  if (num == 1)
  {
    return 0;
  }

  if (num % 2 == 0)
  {
    return 1 + collatz(num / 2);
  }
  else
  {
    return 1 + collatz(3 * num + 1);
  }
}

マージソート（Merge Sort）

• 時間計算量（Worst/Best）：O(n log n)/Ω(n log n)

（映像を見てもどう書くかは分からなくて参考文章のコードを真似して書いてみました。）

参考文章のまとめ：

• 中間位置を見つけることで現在の配列を二つにする。
• 二つの配列をマージソートにいれる。
  • 再帰の終了条件は開始位置＞＝終了位置、
  • 毎回中間位置をみつけてマージソートに入れる。
  • 最後はソートされた二つの要素、配列をマージする。
    （mergeSort関数では最初と最後のインデックスを用いて中間位置を特定する。実際のソートはmergeSort関数の再帰でmerge関数が行っている。）

// merge sort
#include <stdio.h>
#define arrSize(x) (sizeof(x) / sizeof((x)[0]))

void merge(int arr[], int left, int middle, int right);
void mergeSort(int arr[], int left, int right);
void printArray(int A[], int size);

int main(void)
{
  int data1[] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
  int data2[] = {1, -5, 7, 5, 2, 6, 2, 1, 3, -2, 0};

  printf("data1 result: \n");
  mergeSort(data1, 0, arrSize(data1) - 1);
  printArray(data1, arrSize(data1));

  printf("data2 result: \n");
  mergeSort(data2, 0, arrSize(data2) - 1);
  printArray(data2, arrSize(data2));

  return 0;
}

void merge(int arr[], int left, int middle, int right)
{
  int i, j, k;
  int size1 = middle - left + 1;
  int size2 = right - middle;

  // create temp arrays
  int L[size1], R[size2];

  // copy data to temp arrays
  for (i = 0; i < size1; i++)
  {
    L[i] = arr[left + i];
  }
  for (j = 0; j < size2; j++)
  {
    R[j] = arr[middle + 1 + j];
  }

  // initial index of two subarrays
  i = 0;
  j = 0;

  // initial index of merged subarray
  k = left;
  while (i < size1 && j < size2)
  {
    if (L[i] <= R[j])
    {
      arr[k] = L[i];
      i++;
    }
    else
    {
      arr[k] = R[j];
      j++;
    }
    k++;
  }

  // copy the remaining elements
  while (i < size1)
  {
    arr[k] = L[i];
    i++;
    k++;
  }

  while (j < size2)
  {
    arr[k] = R[j];
    j++;
    k++;
  }
}

void mergeSort(int arr[], int left, int right)
{
  if (left < right)
  {
    // avoid overflow for large l and h?
    int middle = left + (right - left) / 2;

    // sort first and second halves
    mergeSort(arr, left, middle);
    mergeSort(arr, middle + 1, right);

    merge(arr, left, middle, right);
  }
}

void printArray(int A[], int size)
{
  for (int i = 0; i < size; i++)
  {
    printf("%d ", A[i]);
  }
  printf("\n");
}
// data1 result: 
// 0 1 2 3 4 5 6 7 8 9 
// data2 result: 
// -5 -2 0 1 1 2 2 3 5 6 7

ヒープソート（Heap Sort）

クイックソート（Quick Sort）

// quick sort
#include <stdio.h>
#define arrSize(x) (sizeof(x) / sizeof((x)[0]))

void swap(int *a, int *b);
int partition(int arr[], int low, int high);
void quickSort(int arr[], int low, int high);
void printArray(int arr[], int size);

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

  quickSort(arr1, 0, arrSize(arr1));
  printArray(arr1, arrSize(arr1));
  quickSort(arr2, 0, arrSize(arr2));
  printArray(arr2, arrSize(arr2));

  return 0;
}

void swap(int *a, int *b)
{
  // store address to swap two elements
  int target = *a;
  *a = *b;
  *b = target;
}

int partition(int arr[], int low, int high)
{
  // pick up the last element as pivot（軸）
  // pivot is an intermediate value between two index(i&j)
  int pivot = arr[high];
  // start from - 1
  int i = low - 1;

  for (int j = low; j < high; j++)
  {
    // "j" => loop variable => 0 ~ (length - 1)
    // if current element <= the last element
    if (arr[j] <= pivot)
    {
      // "i" means the index of smaller element
      // "i" moves no to the next index (the value of previous i was sorted)
      i++;

      // "j" is always eqaul or greater than "i"
      // arr[i] is always smaller than pivot
      swap(&arr[i], &arr[j]);
      // when current arr[j] is greater than pivot, "i" won't move on
      // when current arr[j] is smaller than pivot, "i" will move on
      // to the previous greater arr[j] and exchange with current arr[j]
    }
  }
  // next index of "i" will always be equal or greater than pivot
  swap(&arr[i + 1], &arr[high]);
  // return the sorted index + 1
  return i + 1;
}

void quickSort(int arr[], int low, int high)
{
  if (low < high)
  {
    //
    int sortedIndex = partition(arr, low, high);

    // separate by the current sorted index
    // left part => smaller than previous pivot in partition
    quickSort(arr, low, sortedIndex - 1);
    // right part => greater than previous pivot in partition
    quickSort(arr, sortedIndex + 1, high);
  }
}

void printArray(int arr[], int size)
{
  for (int i = 0; i < size; i++)
  {
    printf("%d ", arr[i]);
  }
  printf("\n");
}
// 0 0 1 2 3 4 5 6 7 8 
// -5 -2 0 0 1 1 2 2 3 5 6

シェルソート（Shell Sort）

振り返り

去年の文章でJavaScriptでアルゴリズムを書いてみましたが、そのときでもマージソートが一番苦戦していました。しかし今振り返ると、そのとき書いたマージソートは実際マージソートではなく、ただ動きを真似した二重ループ関数に過ぎませんでした...。

O(n^2) と O(n log n) 、一番の違いは再帰をどこに、どう使うかと思いますが、今の自分にはまだまだ難しいようです。今回は真似から再帰という考え方や方法を練習しました。