ThuatToanSX(InsertionSort,BubbleSort,ShakerSort,ShellSort)

#include "stdio.h"
#include "stdlib.h"

void XuatMang(int a[], int n)
{
	for (int i = 0; i < n; i++)
		printf("%d ", a[i]);

	printf("\n");
}

void HoanVi(int &x, int &y)
{
	int temp = x;
	x = y;
	y = temp;
}

void SelectionSort(int a[], int n)
{
	for (int i =0; i < n; i++)
	{
		int viTriMin = i;
		for (int j = i + 1; j < n; j++)
		{
			if (a[j] < a[viTriMin]) {
				viTriMin = j;
			}
		}

		HoanVi(a[viTriMin], a[i]);
		XuatMang(a, n);
	}
}

int TimViTriChen(int a[], int start, int end, int x)
{
	for (int i = start; i <= end; i++)
	{
		if (a[i] > x)
		{
			return i;
		}
	}
	return end + 1;
}

void ChenX(int a[], int start, int end, int viTriCanChen, int x)
{
	for (int i = end; i >= viTriCanChen; i--)
	{
		a[i + 1] = a[i];
	}

	a[viTriCanChen] = x;
}

void InsertionSort(int a[], int n)
{
	for (int i = 1; i < n; i++)
	{
		int x = a[i];
		//Tim vi tri chen trong mang a tu vi tri 0 -> i-1
		int viTriCanChen = TimViTriChen(a, 0, i - 1, x);

		//Chen x tai vi tri da tim ra
		ChenX(a, 0, i - 1, viTriCanChen, x);

		XuatMang(a, n);
	}
}

void InsertionSort2(int a[], int n)
{
	for (int i = 1; i < n; i++)
	{
		int x = a[i];
		int j;
		for (j = i - 1; j >= 0; j--)
		{
			if (a[j] > x)
			{
				a[j + 1] = a[j];
			}
			else {
				break;
			}
		}

		a[j + 1] = x;

		XuatMang(a, n);
	}
}


void BubbleSort(int a[], int n)
{
	int day = n - 1;
	int bm = 0;
	while (bm < day)
	{
		int i = day;
		while (i > bm)
		{
			if (a[i] < a[i - 1]) {
				HoanVi(a[i], a[i - 1]);
			}
			i--;

			XuatMang(a, n);
		}
		bm++;
	}
}


void ShakerSort(int a[], int n)
{
	int day = n - 1;
	int bm = 0;
	int noiHoanViCuoiCung = day;
	while (bm < day)
	{
		int i = day;
		while (i > bm)
		{
			if (a[i] < a[i - 1]) {
				HoanVi(a[i], a[i - 1]);
				noiHoanViCuoiCung = i;
			}
			i--;
		}
		bm = noiHoanViCuoiCung;

		i = bm;
		while (i < day)
		{
			if (a[i] > a[i + 1]) {
				HoanVi(a[i], a[i + 1]);
				noiHoanViCuoiCung = i;
			}
			i++;
		}
		day = noiHoanViCuoiCung;
	}

}

void ShellSort(int a[], int n)
{
	int kichThuocSo[] = { 5, 3, 1 };
	int m = 3;
	for (int i = 0; i < m; i++)
	{
		int buocNhay = kichThuocSo[i];

		int viTriDauTienCuaSo = 0;

		while (viTriDauTienCuaSo < buocNhay)
		{
			int j = viTriDauTienCuaSo + buocNhay;

			while (j < n)
			{
				int x = a[j];
				int k = j - buocNhay;
				while (k >= 0 && x < a[k])
				{
					a[k + buocNhay] = a[k];
					k -= buocNhay;
				}
				a[k + buocNhay] = x;
				j += buocNhay;
			}

			viTriDauTienCuaSo++;
		}
	}
}

void main()
{
	int a[] = { 23, 17, 97, 44, 35, 10, 12, 8, 5, 78};
	int n = 10;
	printf("Mang truoc khi sap xep: \n");
	XuatMang(a, n);

	ShellSort(a, n);

	printf("Mang sau khi sap xep: \n");
	XuatMang(a, n);

	system("pause");
}