【C言語・バブルソート】僕でもわかるソート自作

概要

今回は「僕でもわかるソート自作」そーとー、わかりやすいですっ✨

課題でソートの勉強をひたすらしました。
実装の中核にはつかいませんでしたが、クイックソートを解説します。
僕のような初心者の方でも、楽しみながらソートの基本を学べます。

ソートとは...?

ソートとは、値をルールに則って順番に並べ替えることを指します。
例えば、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を表示する

stack_utils.c

#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()ではバブルソートの実装をしました。

sort.c

#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番目から格納する。
・ソートできているならそのまま表示
・ソート前を表示
・ソート関数にスタックを投げる
・ソート後を表示

main.c

#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);
}

次にヘッダーファイルに必要な関数をまとめます！

sort.h

#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を使って簡易テストできます！

Makefile

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で実装したよ！

main.py

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)