sorting algorithms

sort.cpp

#include <iostream>
#include <algorithm>
const int n = 10;
const int MAX = 100000;
int a[n];

void print()
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
void begin()
{
	for (int i = 0; i < n; i++)
	{
		a[i] = rand() % MAX;
	}
	printf("unsorted\n");
	print();
}
void end()
{
	printf("sorted\n");
	print();
	printf("-----------------------------------------------------\n");
}

void bubble_sort()
{
	begin();
	{
		for (int i = 0; i < n - 1; i++)
		{
			for (int j = i + 1; j < n; j++)
			{
				if (a[i] > a[j])
				{
					std::swap(a[i], a[j]);
				}
			}
		}
	}
	end();
}

void insertion_sort()
{
	begin();
	{
		for (int i = 1; i < n; i++)
		{
			int j = i;
			while (j > 0 && a[j] < a[j - 1])
			{
				std::swap(a[j], a[j - 1]);
				j--;
			}
		}
	}
	end();
}
void insertion_sort_no_swap()
{
	// this code is not optimized, to fully reflect the idea of insertion sort
	begin();
	{
		int b[n];
		b[0] = a[0];
		int m = 1;
		for (int i = 1; i < n; i++)
		{
			int k = m;
			for(int j = 0;j < m; j++)
			{
				if(a[i] < b[j])
				{
					k = j;
					break;
				}
			}
			int* right = b + k;
			int* right_shifted = right + 1;
			int size = m - k;
			memmove(right_shifted, right, size * sizeof(int));
			b[k] = a[i];
			m++;
		}
		memcpy(a, b, n * sizeof(int));
	}
	end();
}

void selection_sort()
{
	begin();
	{
		for (int i = 0; i < n; i++)
		{
			int k = i;
			for (int j = i + 1; j < n; j++)
			{
				if (a[j] < a[k])
				{
					k = j;
				}
			}
			std::swap(a[i], a[k]);
		}
	}
	end();
}
void selection_sort_no_swap()
{
	// this code is not optimized, to fully reflect the idea of selection sort.
	begin();
	{
		int b[n];
		for (int i = 0; i < n; i++)
		{
			int k = 0;
			for (int j = 0; j < n; j++)
			{
				if(a[j] == MAX) continue;
				if (a[j] < a[k])
				{
					k = j;
				}
			}
			b[i] = a[k];
			a[k] = MAX;
		}
		memcpy(a, b, n*sizeof(int));
	}
	end();
}


void shell_sort()
{
	begin();
	{
		int gap = (n + 1) / 2;
		while (true)
		{
			int i = 0;
			int j = i + gap;
			while (j < n)
			{
				if (a[i] > a[j])
				{
					std::swap(a[i], a[j]);
				}
				i = i++;
				j = i + gap;
			}
			if (gap == 1)
			{
				break;
			}
			gap = (gap + 1) / 2;
		}
	}
	end();
}

void heap_sort_build_heap(int node, int heap_size);
void heap_sort()
{
	begin();
	{
		int heap_size = n - 1;// for easier implementing, we sort a[1]..a[n]
		a[0] = -1;
		for (int i = heap_size / 2; i >= 1; i--)
		{
			heap_sort_build_heap(i, heap_size);
		}
		
		while (heap_size > 1)
		{
			std::swap(a[1], a[heap_size]);
			heap_sort_build_heap(1, --heap_size);
		}
	}
	end();
}
void heap_sort_build_heap(int node, int heap_size)
{
	int left = node * 2;
	if (left > heap_size)
	{
		return;
	}
	int right = left + 1;
	int max_child;
	{
		max_child = left;
		if (right <= heap_size)
		{
			if (a[right] > a[left])
			{
				max_child = right;
			}
		}
	}
	if (a[node] < a[max_child])
	{
		std::swap(a[node], a[max_child]);
		heap_sort_build_heap(max_child, heap_size);
	}
}
void radix_sort()
{
	// too lazy, do it later
}

void bucket_sort()
{
	// still reading wiki
}

void merge_sort()
{
	// already familiar
}

void quick_sort()
{
	// already familiar
}

int main()
{
	printf("bubble_sort:\n");
	{
		bubble_sort();
	}
	printf("insertion_sort:\n");
	{
		//insertion_sort();
		insertion_sort_no_swap();
	}
	printf("selection_sort:\n");
	{
		//selection_sort();
		selection_sort_no_swap();
	}
	printf("shell_sort:\n");
	{
		shell_sort();
	}
	printf("heap_sort:\n");
	{
		heap_sort();
	}
	printf("radix_sort:\n");
	{
		radix_sort();
	}
	printf("bucket_sort:\n");
	{
		bucket_sort();
	}
	system("pause");
	return 0;
}