#include "stdafx.h"
#include <conio.h>
#include <math.h>
#include <stdlib.h>

int diff_numbers(int *a,int n)
//How many different numbers in a sorted array
{
	int diff=0;
	for(int i=0 ; i<n ; )
	{
		diff++;
		int tmp=a[i];
		i++;
		while(i<n && a[i]==tmp) i++;//move to next a[i]!=tmp
	}
	return diff;
}

void	populate_table(int * b, int n, int* numbers, int *counters)
//Counters[i] to count numbers[i] appearences in sorted array b
//Length of arrays numbers and counters fits number of different numbers in b
{
	int diff=0;
	for(int i=0 ; i<n ; )
	{
		numbers[diff]=b[i];
		counters[diff]=1;
		i++;
		while(i<n && b[i]==numbers[diff]){ i++; counters[diff]++;}
		diff++;
	}
}

int * binary_search_l(int *arr, int len, int key)
//Search key in sorted (small to big) arr
//Return address if found otherwise NULL
{
	if(len<=0)return NULL;
	int l=0,r=len-1;      //  xxxxxxxxxxxxxxxxxxxx
	while(l<=r)          //   l        m         r
	{
		int m=(l+r)/2; // "cut the world"
		if(arr[m]==key) return arr+m;
		if(key<arr[m]) r=m-1;  //take left part
		else l=m+1; // take right part
	}
	return NULL;
}

bool test_sorted(int *a,int n)
//True if a sorted correctly
{
	for(int i=0 ; i<n-1 ; i++)
		if(a[i]>a[i+1]) return false;
	return true;
}

bool	test_permutation(int *a,int n,int *numbers,int *counters,int diff)
//True if all numbers in presorted array do appear in the sorted array
{
	for(int i=0 ; i<n ; i++) //on all numbers in original array
	{
		int *tmp; //will hold address in numbers,[tmp-numbers]=index 
		if((tmp=binary_search_l(numbers, diff, a[i]))!=NULL)
		{
			if(counters[tmp-numbers]==0) return false;//all found already
			else counters[tmp-numbers]--;
		}
		else return false;
	}
	for(int i=0 ; i<diff ; i++)//all counters zeroed?
		if(counters[i]!=0) return false;
	return true;
}

void shell_sort( int *arr, int length)
//Shell sort
{
	int gap=length/2;

	while(gap!=0)
	{
    int s_f=1;
    while(s_f==1) // repeat any cycle until no swaps done
		{
	    s_f=0;
	    for(int i=0 ; i+gap<length ; i++)
			{
		    if(arr[i]>arr[i+gap])
				{
			    int tmp=arr[i];
			    arr[i]=arr[i+gap];
			    arr[i+gap]=tmp;
			    s_f=1;
				}
			}
		}
	  gap=gap/2;
	}
}

const int N=10000;

void main(void)
{
	int a[N],b[N];
	for(int i=0 ; i<N ; i++) a[i]=b[i]=rand()%21-10;

	shell_sort(b,N);

	if(!test_sorted(b,N))
	{
		printf("Sorting error!\n");
		getch();
		return;
	}

	int diff=diff_numbers(b,N); 

	int * numbers=new int [diff]; //was not in project requirments
	int * counters=new int [diff];

	populate_table(b,N,numbers,counters);

	printf("\nnumbers counters\n\n");
	int min_numbers=numbers[0];
	int min_counters=counters[0];
	int max_numbers=numbers[0];
	int max_counters=counters[0];
	for(int i=0 ; i<diff ; i++) 
	{
		printf("%-6d %4d\n",numbers[i],counters[i]);
		if(counters[i]<min_counters)
		{
			min_counters=counters[i];
			min_numbers=numbers[i];
		}
		else if(counters[i]>max_counters)
		{
			max_counters=counters[i];
			max_numbers=numbers[i];
		}
	}

	printf("\nIn the array:\n");
	printf("The number %d appears the least number of times with %d appearances\n", min_numbers, min_counters);
	printf("The number %d appears the most  number of times with %d appearances\n", max_numbers, max_counters);


	printf("\n");

	if(test_permutation(a,N,numbers,counters,diff)) printf("\nOK");
	else printf("\nNot OK");


	_getch();
}
/*
numbers counters

-10     462
-9      469
-8      466
-7      470
-6      498
-5      456
-4      476
-3      465
-2      474
-1      535
0       505
1       474
2       458
3       483
4       471
5       458
6       463
7       488
8       492
9       448
10      489

In the array:
The number 9 appears the least number of times with 448 appearances
The number -1 appears the most  number of times with 535 appearances


OK
*/