C言語でソート 3

2023年1月7日

僕の体形どう？太って見えるけどガッシリとしているでしょうと言っている柴犬です。

概要

データ構造を2次元配列から構造体の1次元配列に変更しました。

i、ｊの範囲設定をしました。

GO、RUST、C の作成した実行ファイルの大きさを比べてみました。

見直し

typedef struct で構造体 line 型を作りました。結果、分かりやすいコードになりました。

C言語は大きなプログラムになるとメモリ管理が大変そうですが、個人で管理できる小さいものを作るにはいいかもと思うようになりました。

今回作業した限りでみれば、C言語は原始的であるが故、分かりやすいと感じました。

copy

#include <stdlib.h>
#include <stdio.h>
#include <wchar.h>
#include <locale.h>
#include <string.h>

#define N 1200000

typedef struct
{
  char f1[40];
  char f2[50];
} line;

void quicksort(line record[], int left, int right);
void swap(line *record1, line *record2);
int getposi(line record[], int left, int right);

int main()
{
  FILE *fin;
  FILE *fout;
  wchar_t *res;
  int f;

  setlocale(LC_CTYPE, "");

  fin = fopen("./input.csv", "r");
  fout = fopen("./output.csv", "w");

  const wchar_t *const separator = L",";

  // メモリの動的確保
  // malloc ではなく calloc を使うことにしました。
  line *record = (line *)calloc(N, sizeof(line));

  int count = 0;
  for (;;)
  {
    wchar_t str[90];
    f = 0;
    if (fgetws(str, sizeof(str) / sizeof(str[0]), fin) == NULL)
    {
      if (feof(fin))
      {
        // ファイルの終わり
        break;
      }
      else
      {
        fputs("エラーが発生しました。\n", stderr);
        exit(EXIT_FAILURE);
      }
    }

    wchar_t *token = wcstok(str, separator);
    while (token != NULL)
    {
      if (f == 0)
      {
        res = wcsncpy(record[count].f1, token, 20);
      }
      else
      {
        res = wcsncpy(record[count].f2, token, 30);
      }
      f += 1;
      token = wcstok(NULL, separator);
    }
    count += 1;
  }

  wprintf(L"%ls\n", record[count - 1].f1);
  wprintf(L"%ls\n", record[count - 1].f2);
  printf("\nData has been getten...%d\n", count);

  quicksort(record, 0, count - 1);

  int i = 0;
  for (;;)
  {
    if (i == count)
    {
      break;
    }
    fwprintf(fout, L"%ls", record[i].f1);
    fwprintf(fout, L"%ls", L",");
    fwprintf(fout, L"%ls", record[i].f2);
    i += 1;
  }

  fclose(fin);
  fclose(fout);

  wprintf(L"%ls\n", record[count - 1].f1);
  wprintf(L"%ls\n", record[count - 1].f2);
  printf("\nFile has been created...%d\n", count);

  free(record);
  return 0;
}

void quicksort(line record[], int left, int right)
{
  int posi;
  if (left < right)
  {
    posi = getposi(record, left, right);
    // int型なのでOK
    quicksort(record, left, posi - 1);
    quicksort(record, posi + 1, right);
  }

  return;
}

int getposi(line record[], int left, int right)
{
  char *pivot1;
  char *pivot2;
  // 軸を左端
  pivot1 = record[left].f1;
  pivot2 = record[left].f2;
  // 開始位置
  int i = left + 1;
  int j = right;

  // 昇順にするため左を小さいもののエリアにしています。
  // 無限ループにしています。
  while (1)
  {
    // i、j が取り得る範囲 left + 1 <= i、j <= right 
    // 条件が真の間 i をすすめます。
    while (i <= right && (wcscmp(pivot1, record[i].f1) > 0 || (wcscmp(pivot1, record[i].f1) == 0 && wcscmp(pivot2, record[i].f2) > 0)))
    {
      // 次の位置
      i += 1;
    }
    // 条件が真の間 j をすすめます。 
    while (j >= left + 1 && (wcscmp(record[j].f1, pivot1) > 0 || (wcscmp(record[j].f1, pivot1) == 0 && wcscmp(record[j].f2, pivot2) >= 0)))
    {
      // 次の位置
      j -= 1;
    }
    // 結果、交差したら終了
    if (i >= j)
    {
      break;
    }

    // 交差していなければ交換
    swap(&record[i], &record[j]);
  }

  // pivotの位置iが定まったので交換
  swap(&record[left], &record[j]);
  // 位置を返す
  return j;
}

void swap(line *record1, line *record2)
{
  line temp;
  temp = *record1;
  *record1 = *record2;
  *record2 = temp;
  return;
}