概要
今回は「僕でもわかるソート自作」そーとー、わかりやすいですっ✨
課題でソートの勉強をひたすらしました。
実装の中核にはつかいませんでしたが、クイックソートを解説します。
僕のような初心者の方でも、楽しみながらソートの基本を学べます。
ソートとは...?
ソートとは、値をルールに則って順番に並べ替えることを指します。
例えば、1 3 2を小さい順にソートすると1 2 3となります。
要するに 並べ替え ですね！
今回は、この 並べ替え を自動でやってくれるプログラムを作成します。
実装！
バブルソート
実はソートする考え方は1通りではありません。
ここではバブルソートについて解説します。
バブルソートは横並びになっている 2数の大小を比較していけばいつかは並び変わるだろう！ という戦略です。
具体例を見てみましょう！
このような数列があります。
1 3 0 2 4
最初に1と3を比較します。大丈夫そうですね。
3と0を比較しました。「おやっ！？」並べ替えましょう！
1 0 3 2 4
3と2を比較しました。「おやっ？！」並べ替えましょう！
1 0 2 3 4
3と4を比較しました。大丈夫そうですね。
まだソートしきれてないので、もう1週行きます。
1と0を比較しました。「おやっ？！」並べ替えましょう！
0 1 2 3 4
これできれいにソートできました 🎉
実装手順
以下のように実装します
０）ソートできたかチェック
１）比較
２）必要であれば並べ替え、ソートできたかチェック
３）ソートできてなかったら０に戻る
レッツプログラム！
stack_utils.cでは以下の関数を作ります。
・引数を
stackに書き込む。その際にすでにある要素を追加しないようにis_in_list()を呼んで確認する。また、数字のみが入るように引数をチェックする
・stackを表示する
#include "sort.h"
static int is_in_list(int n, int *stack, int end)
{
int m;
m = 0;
while (m < end)
{
if (n == stack[m])
return (1);
m++;
}
return (0);
}
int write_stack(int *stack, char **argv)
{
int n;
n = 1;
while (argv[n])
{
if (atoi(argv[n]) == 0)
{
if (!(argv[n][0] == '0' && argv[n][1] == '\0'))
return (1);
}
if (is_in_list(atoi(argv[n]), stack, n) == 1)
return (1);
stack[n - 1] = atoi(argv[n]);
n++;
}
return (0);
}
void print_stack(int *stack, int stack_size, char *msg)
{
int n;
n = 0;
printf("%s", msg);
while (n < stack_size - 1)
{
printf(" %d ", stack[n]);
n++;
}
printf("\n");
}
sort.cでは以下のことをします。
・
is_sorted()ではstackがソートされているかチェックします。
・buble_sort()ではバブルソートの実装をしました。
#include "sort.h"
int is_sorted(int *stack, int stack_size)
{
int n;
n = 0;
while (n < stack_size - 2)
{
if (!(stack[n] < stack[n + 1]))
return (1);
n++;
}
return (0);
}
void buble_sort(int *stack, int stack_size)
{
int n;
int tmp;
while (is_sorted(stack, stack_size))
{
n = 0;
while (n < stack_size - 2)
{
if (!(stack[n] < stack[n + 1]))
{
tmp = stack[n];
stack[n] = stack[n + 1];
stack[n + 1] = tmp;
}
n++;
}
}
}
main.cでは以下のことをします。
・引数が与えられなかった場合、Usageを表示。
・stackという変数に引数の1番目から格納する。
・ソートできているならそのまま表示
・ソート前を表示
・ソート関数にスタックを投げる
・ソート後を表示
#include "sort.h"
static int print_usage(void)
{
printf("./sort <numbers that u want to sort!>\n");
return (1);
}
int main(int argc, char **argv)
{
int stack_size;
int stack[argc];
if (argc == 1)
return (print_usage());
stack_size = argc;
if (write_stack(stack, argv) == 1)
return (print_usage());
if (is_sorted(stack, stack_size) == 0)
{
print_stack(stack, stack_size, "Sorted : ");
printf("\n");
return (0);
}
print_stack(stack, stack_size, "Befor : ");
buble_sort(stack, stack_size);
print_stack(stack, stack_size, "After : ");
printf("\n");
return (0);
}
次にヘッダーファイルに必要な関数をまとめます！
#ifndef SORT_H
# define SORT_H
# include <stdio.h>
# include <stdlib.h>
# include <string.h>
// stack_utils.c
int write_stack(int *stack, char **argv);
void print_stack(int *stack, int stack_size, char *msg);
// sort.c
int is_sorted(int *stack, int stack_size);
void buble_sort(int *stack, int stack_size);
#endif
最後に任意でMakefileを作成しましょう！
一応サニタイザー入れてますが、必要ない...?
make testを使って簡易テストできます！
NAME = sort
CC = gcc
CFLAGS = -Wall -Wextra -Werror
DBG = -fsanitize=address -fsanitize=leak
RM = rm -rf
SRCS = main.c sort.c stack_utils.c
all : $(NAME)
$(NAME) : $(SRCS)
clear
$(CC) $(SRCS) $(CFLAGS) $(DBG) -o $(NAME)
clean :
$(RM) $(NAME)
re : clean all
test : re
clear
./sort 1 2 3
./sort 1 4 5 6 9 10
./sort 1 -1 0 -3 4
./sort 5 9 16 17 12 8 15 4 19 7 18 10 11 2 14 6 20 3 1 13
./sort 4 12 8 6 11 17 5 19 3 20 2 14 9 7 18 15 1 16 10 13
./sort 29 30 15 13 16 -21 40 7 31 34 35 8 14 -6 18 37 -24 5 9 23 25 26 12 -2 11 3 33 17 4 28 -20 32 36 22 38 19 10 1 27 -39
振り返り
数学みたいな感じで、楽しかったですー！
アルゴリズムは特に難しくなかったので、1時間くらいで実装できる！
友達と時間勝負してみるのもいいかもですね！
Pythonで実装したよ！
import sys
import os
def is_sort(argList):
n = 0
while n < len(argList) - 1:
if (av[n] > av[n + 1]):
return 1
n = n + 1
return 0
def usage():
print("python3 " + __file__ + " <Number that u wanna sort.>")
def write_arg(av, args):
flag = 0
for i in args:
if (i == "python3" or i == "python"):
pass
elif (i == __file__):
pass
elif (i.isdecimal() and i not in av):
av.append(i)
else:
usage()
return (1)
return (0)
args = sys.argv
av = []
if (write_arg(av, args) == 1):
sys.exit()
n = 0
while (is_sort(av) == 1):
n = 0
while (n < len(av) - 1):
if (av[n] > av[n + 1]):
av[n], av[n + 1] = av[n + 1], av[n]
n = n + 1
print(av)