Лабораторные работы 1 и 2 / Veroyatnosti / msvc / Lab1

// Lab1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdio.h"
#include <stdlib.h>

long int n1 = 0,
n2 = 0,
n3 = 0,
n4 = 0,
n5 = 0,
n6 = 0,
n7 = 0,
n71 = 0,
n72 = 0,
n8 = 0,
n9 = 0,
n10 = 0,
n11 = 0;

void swap (float &p, float &q)
{
	float hold;
	hold = p;
	p = q;
	q = hold;

}


void quicksort(float x[],  int n)
{
	int left[20], right[20];
	int i,j,sp,mid;
	float pivot;

	left[1] = 1;
	right[1] = n;
	sp = 1;

	/*/////*/ n1++;

  while (sp>0)
	  {
	  	/*/////*/ n3++;
      if (left[sp] >= right[sp])
	  { sp = sp-1; /*/////*/ n4++; }
	  else
	  {
			/*/////*/ n5++;	
		  i = left[sp];
			j = right[sp];
			pivot = x[j];
			mid = (i+j) % 2;
			if ((j-i)>5)
			{
				/*/////*/ n6++;
				if (((x[mid]<pivot) && (x[mid]>x[i])) || ((x[mid]>pivot) && (x[mid]<x[i])))
				{
					/*/////*/ n71++;
					swap(x[mid],x[j]);
				}
			
				else
				{			
				/*/////*/ n7++;
				if (((x[i]<x[mid]) && (x[i]>pivot)) || ((x[i]>x[mid]) && (x[i]<pivot)))
					{
					/*/////*/ n72++;
					swap(x[i],x[j]);
					}
				}
			}
			pivot = x[j];
			while (i<j)
			{
				/*/////*/ n8++;
				while (x[i]<pivot)
				{ i = i+1; }
				j = j-1;
				while ((i<j) && (pivot<x[j]))
				{ j = j-1; }
				if (i<j)
				{ swap(x[i],x[j]); }
			}		// while
			/*/////*/ n9++;
			j = right[sp];   // pivot to i 
			swap(x[i],x[j]);
			if (i-left[sp]>=right[sp]-i)
			{   // put shorter part first 
				/*/////*/ n10++;
				left[sp+1] = left[sp];
				right[sp+1] = i-1;
				left[sp] = i+1;
			}
			else
			{
				/*/////*/ n11++;
				left[sp+1] = i+1;
				right[sp+1] = right[sp];
				right[sp] = i-1;
			}
			sp = sp+1;    // push stack
		}    // if 
	}   // while 
	/*/////*/ n2++;

}



int main()
{
	float array[102];
	int k,x;


for (x = 2; x <= 101; x++)
{
	for (k = 1; k <= x; k++)
	{
		array[k] = (float)(rand()%1000+1); 
	}

	//for (k = 1; k <= x; k++)		{ printf ("%f\n", array[k]); }

	//printf ("================\n");
	quicksort(array, x);
	//for (k = 1; k <= x; k++)		{ printf ("%f\n", array[k]); }
	//printf ("================\n");
	//printf ("================\n");
}
	printf ("================\n");
	printf ("n1 %d\n", n1);
	printf ("n2 %d\n", n2);
	printf ("n3 %d\n", n3);
	printf ("n4 %d\n", n4);
	printf ("n5 %d\n", n5);
	printf ("n6 %d\n", n6);
	printf ("n7 %d\n", n7);
	printf ("n71 %d\n", n71);
	printf ("n72 %d\n", n72);
	printf ("n8 %d\n", n8);
	printf ("n9 %d\n", n9);
	printf ("n10 %d\n", n10);
	printf ("n11 %d\n", n11);
	return 0;
}