امثلة لخوارزميات الترتيب بلغة السي

[garo 7]

بســم الله الـرحمــن الرحيــم

خوارزمية Bubble Sort

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


#define uint32 unsigned int

typedef int (*CMPFUN)(int, int);




void ArraySort(int This[], CMPFUN fun_ptr, uint32 ub)
{
  /* bubble sort */

  uint32 indx;
  uint32 indx2;
  int temp;
  int temp2;
  int flipped;

  if (ub <= 1)
	return;

  indx = 1; 
  do
  {
	flipped = 0;
	for (indx2 = ub - 1; indx2 >= indx; --indx2)
	{
	  temp = This[indx2];
	  temp2 = This[indx2 - 1];
	  if ((*fun_ptr)(temp2, temp) > 0)
	  {
		This[indx2 - 1] = temp;
		This[indx2] = temp2;
		flipped = 1;
	  }
	}
  } while ((++indx < ub) && flipped);
}

#define ARRAY_SIZE 14

int my_array[ARRAY_SIZE];

void fill_array()
{
  int indx;

  for (indx=0; indx < ARRAY_SIZE; ++indx)
  {
	my_array[indx] = rand();
  }
  /* my_array[ARRAY_SIZE - 1] = ARRAY_SIZE / 3; */
}

int cmpfun(int a, int b)
{
  if (a > b)
	return 1;
  else if (a < b)
	return -1;
  else
	return 0;
}

int main()
{
  int indx;
  int indx2;

  for (indx2 = 0; indx2 < 80000; ++indx2)
  { 
	fill_array();
	ArraySort(my_array, cmpfun, ARRAY_SIZE);
	for (indx=1; indx < ARRAY_SIZE; ++indx)
	{
	  if (my_array[indx - 1] > my_array[indx])
	  {
		printf("bad sort\n");
		return(1);
	  }
	}
  }

  return(0);
}

خوارزمية Selection Sort

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


#define uint32 unsigned int

typedef int (*CMPFUN)(int, int);




void ArraySort(int This[], CMPFUN fun_ptr, uint32 the_len)
{
  /* selection sort */

  uint32 indx;
  uint32 indx2;
  uint32 large_pos;
  int temp;
  int large;

  if (the_len <= 1)
	return;

  for (indx = the_len - 1; indx > 0; --indx)
  {
	/* find the largest number, then put it at the end of the array */
	large = This[0];
	large_pos = 0;

	for (indx2 = 1; indx2 <= indx; ++indx2)
	{
	  temp = This[indx2];
	  if ((*fun_ptr)(temp ,large) > 0)
	  {
		large = temp;
		large_pos = indx2;
	  }
	}
	This[large_pos] = This[indx];
	This[indx] = large;
  }
}

#define ARRAY_SIZE 14

int my_array[ARRAY_SIZE];

void fill_array()
{
  int indx;

  for (indx=0; indx < ARRAY_SIZE; ++indx)
  {
	my_array[indx] = rand();
  }
  /* my_array[ARRAY_SIZE - 1] = ARRAY_SIZE / 3; */
}

int cmpfun(int a, int b)
{
  if (a > b)
	return 1;
  else if (a < b)
	return -1;
  else
	return 0;
}

int main()
{
  int indx;
  int indx2;

  for (indx2 = 0; indx2 < 80000; ++indx2)
  { 
	fill_array();
	ArraySort(my_array, cmpfun, ARRAY_SIZE);
	for (indx=1; indx < ARRAY_SIZE; ++indx)
	{
	  if (my_array[indx - 1] > my_array[indx])
	  {
		printf("bad sort\n");
		return(1);
	  }
	}
  }

  return(0);
}

خوارزمية Insertion Sort

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


#define uint32 unsigned int

typedef int (*CMPFUN)(int, int);



void ArraySort(int This[], CMPFUN fun_ptr, uint32 the_len)
{
  /* insertion sort */

  uint32 indx;
  int cur_val;
  int prev_val;

  if (the_len <= 1)
	return;

  prev_val = This[0];

  for (indx = 1; indx < the_len; ++indx)
  {
	cur_val = This[indx];
	if ((*fun_ptr)(prev_val, cur_val) > 0)
	{
	  /* out of order: array[indx-1] > array[indx] */
	  uint32 indx2;
	  This[indx] = prev_val; /* move up the larger item first */

	  /* find the insertion point for the smaller item */
	  for (indx2 = indx - 1; indx2 > 0;)
	  {
		int temp_val = This[indx2 - 1];
		if ((*fun_ptr)(temp_val, cur_val) > 0)
		{
		  This[indx2--] = temp_val;
		  /* still out of order, move up 1 slot to make room */
		}
		else
		  break;
	  }
	  This[indx2] = cur_val; /* insert the smaller item right here */
	}
	else
	{
	  /* in order, advance to next element */
	  prev_val = cur_val;
	}
  }
}

#define ARRAY_SIZE 14

int my_array[ARRAY_SIZE];

uint32 fill_array()
{
  int indx;
  uint32 checksum = 0; 
  for (indx=0; indx < ARRAY_SIZE; ++indx)
  {
	checksum += my_array[indx] = rand();
  }
  return checksum;
}

int cmpfun(int a, int b)
{
  if (a > b)
	return 1;
  else if (a < b)
	return -1;
  else
	return 0;
}

int main()
{
  int indx;
  int indx2;
  uint32 checksum1;
  uint32 checksum2;

  for (indx2 = 0; indx2 < 80000; ++indx2)
  {
	checksum1 = fill_array();
	ArraySort(my_array, cmpfun, ARRAY_SIZE);
	for (indx=1; indx < ARRAY_SIZE; ++indx)
	{
	  if (my_array[indx - 1] > my_array[indx])
	  {
		printf("bad sort\n");
		return(1);
	  }
	}
	checksum2 = 0;
	for (indx=0; indx < ARRAY_SIZE; ++indx)
	{
	  checksum2 += my_array[indx];
	}
	if (checksum1 != checksum2)
	{
	  printf("bad checksum %d %d\n", checksum1, checksum2);
	}
  }

  return(0);
}

خوارزمية Quicksort

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

#define INSERTION_SORT_BOUND 16 /* boundary point to use insertion sort */

#define uint32 unsigned int

typedef int (*CMPFUN)(int, int);

/* explain function
 * Description:
 *   fixarray::Qsort() is an internal subroutine that implements quick sort.
 *
 * Return Value: none
 */
void Qsort(int This[], CMPFUN fun_ptr, uint32 first, uint32 last)
{
  uint32 stack_pointer = 0;
  int first_stack[32];
  int last_stack[32];

  for (;;)
  {
	if (last - first <= INSERTION_SORT_BOUND)
	{
	  /* for small sort, use insertion sort */
	  uint32 indx;
	  int prev_val = This[first];
	  int cur_val;

	  for (indx = first + 1; indx <= last; ++indx)
	  {
		cur_val = This[indx];
		if ((*fun_ptr)(prev_val, cur_val) > 0)
		{
		  /* out of order: array[indx-1] > array[indx] */
		  uint32 indx2;
		  This[indx] = prev_val; /* move up the larger item first */

		  /* find the insertion point for the smaller item */
		  for (indx2 = indx - 1; indx2 > first; )
		  {
			int temp_val = This[indx2 - 1];
			if ((*fun_ptr)(temp_val, cur_val) > 0)
			{
			  This[indx2--] = temp_val;
			  /* still out of order, move up 1 slot to make room */
			}
			else
			  break;
		  }
		  This[indx2] = cur_val; /* insert the smaller item right here */
		}
		else
		{
		  /* in order, advance to next element */
		  prev_val = cur_val;
		}
	  }
	}
	else
	{
	  int pivot;

	  /* try quick sort */
	  {
		int temp;
		uint32 med = (first + last) >> 1;
		/* Choose pivot from first, last, and median position. */
		/* Sort the three elements. */
		temp = This[first];
		if ((*fun_ptr)(temp, This[last]) > 0)
		{
		  This[first] = This[last]; This[last] = temp;
		}
		temp = This[med];
		if ((*fun_ptr)(This[first], temp) > 0)
		{
		  This[med] = This[first]; This[first] = temp;
		}
		temp = This[last];
		if ((*fun_ptr)(This[med], temp) > 0)
		{
		  This[last] = This[med]; This[med] = temp;
		}
		pivot = This[med];
	  }
	  {
		uint32 up;
		{
	  uint32 down;
		  /* First and last element will be loop stopper. */
	  /* Split array into two partitions. */
	  down = first;
	  up = last;
	  for (;;)
	  {
		do
		{
		  ++down;
		} while ((*fun_ptr)(pivot, This[down]) > 0);

		do
		{
		  --up;
		} while ((*fun_ptr)(This[up], pivot) > 0);

		if (up > down)
		{
		  int temp;
		  /* interchange L[down] and L[up] */
		  temp = This[down]; This[down]= This[up]; This[up] = temp;
		}
		else
		  break;
	  }
	}
	{
	  uint32 len1; /* length of first segment */
	  uint32 len2; /* length of second segment */
	  len1 = up - first + 1;
	  len2 = last - up;
	  /* stack the partition that is larger */
	  if (len1 >= len2)
	  {
		first_stack[stack_pointer] = first;
		last_stack[stack_pointer++] = up;

		first = up + 1;
		/*  tail recursion elimination of
		 *  Qsort(This,fun_ptr,up + 1,last)
		 */
	  }
	  else
	  {
		first_stack[stack_pointer] = up + 1;
		last_stack[stack_pointer++] = last;

		last = up;
		/* tail recursion elimination of
		 * Qsort(This,fun_ptr,first,up)
		 */
	  }
	}
		continue;
	  }
	  /* end of quick sort */
	}
	if (stack_pointer > 0)
	{
	  /* Sort segment from stack. */
	  first = first_stack[--stack_pointer];
	  last = last_stack[stack_pointer];
	}
	else
	  break;
  } /* end for */
}


void ArraySort(int This[], CMPFUN fun_ptr, uint32 the_len)
{
  Qsort(This, fun_ptr, 0, the_len - 1);
}

#define ARRAY_SIZE 250000

int my_array[ARRAY_SIZE];

uint32 fill_array()
{
  int indx;
  uint32 checksum = 0; 
  for (indx=0; indx < ARRAY_SIZE; ++indx)
  {
	checksum += my_array[indx] = rand();
  }
  return checksum;
}

int cmpfun(int a, int b)
{
  if (a > b)
	return 1;
  else if (a < b)
	return -1;
  else
	return 0;
}

int main()
{
  int indx;
  uint32 checksum1; 
  uint32 checksum2 = 0;
  checksum1 = fill_array();

  ArraySort(my_array, cmpfun, ARRAY_SIZE);

  for (indx=1; indx < ARRAY_SIZE; ++indx)
  {
	if (my_array[indx - 1] > my_array[indx])
	{
	  printf("bad sort\n");
	  return(1);
	}
  }

  for (indx=0; indx < ARRAY_SIZE; ++indx)
  {
	checksum2 += my_array[indx];
  }

  if (checksum1 != checksum2)
  {
	printf("bad checksum %d %d\n", checksum1, checksum2);
	return(1);
  }

  return(0);
}

خوارزمية Mergesort

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


#define uint32 unsigned int

typedef int (*CMPFUN)(int, int);



#define INSERTION_SORT_BOUND 8 /* boundary point to use insertion sort */

void ArraySort(int This[], CMPFUN fun_ptr, uint32 the_len)
{
  uint32 span;
  uint32 lb;
  uint32 ub;
  uint32 indx;
  uint32 indx2;

  if (the_len <= 1)
	return;

  span = INSERTION_SORT_BOUND;

  /* insertion sort the first pass */
  { 
	int prev_val;
	int cur_val;
	int temp_val;

	for (lb = 0; lb < the_len; lb += span)
	{
	  if ((ub = lb + span) > the_len) ub = the_len;

	  prev_val = This[lb];

	  for (indx = lb + 1; indx < ub; ++indx)
	  {
		cur_val = This[indx];

		if ((*fun_ptr)(prev_val, cur_val) > 0)
		{
		  /* out of order: array[indx-1] > array[indx] */
		  This[indx] = prev_val; /* move up the larger item first */

		  /* find the insertion point for the smaller item */
		  for (indx2 = indx - 1; indx2 > lb;)
		  {
			temp_val = This[indx2 - 1];
			if ((*fun_ptr)(temp_val, cur_val) > 0)
			{
			  This[indx2--] = temp_val;
			  /* still out of order, move up 1 slot to make room */
			}
			else
			  break;
		  }
		  This[indx2] = cur_val; /* insert the smaller item right here */
		}
		else
		{
		  /* in order, advance to next element */
		  prev_val = cur_val;
		}
	  }
	}
  }

  /* second pass merge sort */
  {
	uint32 median;
	int* aux;

	aux = (int*) malloc(sizeof(int) * the_len / 2);

	while (span < the_len)
	{
	  /* median is the start of second file */
	  for (median = span; median < the_len;)
	  {
		indx2 = median - 1;
		if ((*fun_ptr)(This[indx2], This[median]) > 0)
		{
		  /* the two files are not yet sorted */
		  if ((ub = median + span) > the_len)
		  {
			ub = the_len;
		  }

		  /* skip over the already sorted largest elements */
		  while ((*fun_ptr)(This[--ub], This[indx2]) >= 0)
		  {
		  }

		  /* copy second file into buffer */
		  for (indx = 0; indx2 < ub; ++indx)
		  {
			*(aux + indx) = This[++indx2];
		  }
		  --indx;
		  indx2 = median - 1;
		  lb = median - span;
		  /* merge two files into one */
		  for (;;)
		  {
			if ((*fun_ptr)(*(aux + indx), This[indx2]) >= 0)
			{
			  This[ub--] = *(aux + indx);
			  if (indx > 0) --indx;
			  else
			  {
				/* second file exhausted */
				for (;;)
				{
				  This[ub--] = This[indx2];
				  if (indx2 > lb) --indx2;
				  else goto mydone; /* done */
				}
			  }
			}
			else
			{
			  This[ub--] = This[indx2];
			  if (indx2 > lb) --indx2;
			  else
			  {
				/* first file exhausted */
				for (;;)
				{
				  This[ub--] = *(aux + indx);
				  if (indx > 0) --indx;
				  else goto mydone; /* done */
				}
			  }
			}
		  }
		}
		mydone:
		median += span + span;
	  }
	  span += span;
	}

	free(aux);
  } 
}

#define ARRAY_SIZE 250000

int my_array[ARRAY_SIZE];

uint32 fill_array()
{
  int indx;
  uint32 sum = 0;

  for (indx=0; indx < ARRAY_SIZE; ++indx)
  {
	sum += my_array[indx] = rand();
  }
  return sum;
}

int cmpfun(int a, int b)
{
  if (a > b)
	return 1;
  else if (a < b)
	return -1;
  else
	return 0;
}

int main()
{
  int indx;
  uint32 checksum, checksum2;

  checksum = fill_array();

  ArraySort(my_array, cmpfun, ARRAY_SIZE);

  checksum2 = my_array[0];

  for (indx=1; indx < ARRAY_SIZE; ++indx)
  {
	checksum2 += my_array[indx];
	if (my_array[indx - 1] > my_array[indx])
	{
	  printf("bad sort\n");
	  return(1);
	}
  }

  if (checksum != checksum2)
  {
	printf("bad checksum %d %d\n", checksum, checksum2);
	return(1);
  }
  return(0);
}

خوارزمية Heapsort

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


#define uint32 unsigned int

typedef int (*CMPFUN)(int, int);


void ArraySort(int This[], CMPFUN fun_ptr, uint32 the_len)
{
  /* heap sort */

  uint32 half;
  uint32 parent;

  if (the_len <= 1)
	return;

  half = the_len >> 1;
  for (parent = half; parent >= 1; --parent)
  {
	int temp;
	int level = 0;
	uint32 child;

	child = parent;
	/* bottom-up downheap */

	/* leaf-search for largest child path */
	while (child <= half)
	{
	  ++level;
	  child += child;
	  if ((child < the_len) &&
		  ((*fun_ptr)(This[child], This[child - 1]) > 0))
		++child;
	}
	/* bottom-up-search for rotation point */
	temp = This[parent - 1];
	for (;;)
	{
	  if (parent == child)
		break;
	  if ((*fun_ptr)(temp, This[child - 1]) <= 0)
		break;
	  child >>= 1;
	  --level;
	}
	/* rotate nodes from parent to rotation point */
	for (;level > 0; --level)
	{
	  This[(child >> level) - 1] =
		This[(child >> (level - 1)) - 1];
	}
	This[child - 1] = temp;
  }

  --the_len;
  do
  {
	int temp;
	int level = 0;
	uint32 child;

	/* move max element to back of array */
	temp = This[the_len];
	This[the_len] = This[0];
	This[0] = temp;

	child = parent = 1;
	half = the_len >> 1;

	/* bottom-up downheap */

	/* leaf-search for largest child path */
	while (child <= half)
	{
	  ++level;
	  child += child;
	  if ((child < the_len) &&
		  ((*fun_ptr)(This[child], This[child - 1]) > 0))
		++child;
	}
	/* bottom-up-search for rotation point */
	for (;;)
	{
	  if (parent == child)
		break;
	  if ((*fun_ptr)(temp, This[child - 1]) <= 0)
		break;
	  child >>= 1;
	  --level;
	}
	/* rotate nodes from parent to rotation point */
	for (;level > 0; --level)
	{
	  This[(child >> level) - 1] =
		This[(child >> (level - 1)) - 1];
	}
	This[child - 1] = temp;
  } while (--the_len >= 1);
}


#define ARRAY_SIZE 250000

int my_array[ARRAY_SIZE];

void fill_array()
{
  int indx;

  for (indx=0; indx < ARRAY_SIZE; ++indx)
  {
	my_array[indx] = rand();
  }
}

int cmpfun(int a, int b)
{
  if (a > b)
	return 1;
  else if (a < b)
	return -1;
  else
	return 0;
}

int main()
{
  int indx;

  fill_array();

  ArraySort(my_array, cmpfun, ARRAY_SIZE);

  for (indx=1; indx < ARRAY_SIZE; ++indx)
  {
	if (my_array[indx - 1] > my_array[indx])
	{
	  printf("bad sort\n");
	  return(1);
	}
  }

  return(0);
}

خوارزمية Shellsort

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


#define uint32 unsigned int

typedef int (*CMPFUN)(int, int);


/* Calculated from the combinations of  9 * (4^n - 2^n) + 1,
 * and  4^n - 3 * 2^n + 1
 */
uint32 hop_array[] =
{
1,
5,
19,
41,
109,
209,
505,
929,
2161,
3905,
8929,
16001,
36289,
64769,
146305,
260609,
587521,
1045505,
2354689,
4188161,
9427969,
16764929,
37730305,
67084289,
150958081,
268386305,
603906049,
1073643521,
2415771649,
0xffffffff }; 


void ArraySort(int This[], CMPFUN fun_ptr, uint32 the_len)
{
  /* shell sort */

  int level;

  for (level = 0; the_len > hop_array[level]; ++level);

  do
  {
	uint32 dist;
	uint32 indx;

	dist = hop_array[--level];
	for (indx = dist; indx < the_len; ++indx)
	{
	  int cur_val;
	  uint32 indx2;

	  cur_val = This[indx];
	  indx2 = indx;
	  do
	  {
		int early_val;
		early_val = This[indx2 - dist];
		if ((*fun_ptr)(early_val, cur_val) <= 0)
		  break;
		This[indx2] = early_val;
		indx2 -= dist;
	  } while (indx2 >= dist);
	  This[indx2] = cur_val;
	}
  } while (level >= 1);
}


#define ARRAY_SIZE 250000

int my_array[ARRAY_SIZE];

uint32 fill_array()
{
  int indx;
  uint32 checksum = 0;
  for (indx=0; indx < ARRAY_SIZE; ++indx)
  {
	checksum += my_array[indx] = rand();
  }
  return checksum;
}

int cmpfun(int a, int b)
{
  if (a > b)
	return 1;
  else if (a < b)
	return -1;
  else
	return 0;
}

int main()
{
  int indx;
  uint32 sum1;
  uint32 sum2;

  sum1 = fill_array();

  ArraySort(my_array, cmpfun, ARRAY_SIZE);

  for (indx=1; indx < ARRAY_SIZE; ++indx)
  {
	if (my_array[indx - 1] > my_array[indx])
	{
	  printf("bad sort\n");
	  return(1);
	}
  }
  for (indx = 0; indx < ARRAY_SIZE; ++indx)
  {
	sum2 += my_array[indx];
  }
  if (sum1 != sum2)
  {
	printf("bad checksum\n");
	return(1);
  }
  return(0);
}

خوارزمية Combo Sort

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


#define uint32 unsigned int

typedef int (*CMPFUN)(int, int);


void HelperHeapSort(int This[], CMPFUN fun_ptr, uint32 first, uint32 the_len)
{
  /* heap sort */

  uint32 half;
  uint32 parent;

  if (the_len <= 1)
	return;

  half = the_len >> 1;
  for (parent = half; parent >= 1; --parent)
  {
	int temp;
	int level = 0;
	uint32 child;

	child = parent;
	/* bottom-up downheap */

	/* leaf-search for largest child path */
	while (child <= half)
	{
	  ++level;
	  child += child;
	  if ((child < the_len) &&
		  ((*fun_ptr)(This[first + child], This[first + child - 1]) > 0))
		++child;
	}
	/* bottom-up-search for rotation point */
	temp = This[first + parent - 1];
	for (;;)
	{
	  if (parent == child)
		break;
	  if ((*fun_ptr)(temp, This[first + child - 1]) <= 0)
		break;
	  child >>= 1;
	  --level;
	}
	/* rotate nodes from parent to rotation point */
	for (;level > 0; --level)
	{
	  This[first + (child >> level) - 1] =
		This[first + (child >> (level - 1)) - 1];
	}
	This[first + child - 1] = temp;
  }

  --the_len;
  do
  {
	int temp;
	int level = 0;
	uint32 child;

	/* move max element to back of array */
	temp = This[first + the_len];
	This[first + the_len] = This[first];
	This[first] = temp;

	child = parent = 1;
	half = the_len >> 1;

	/* bottom-up downheap */

	/* leaf-search for largest child path */
	while (child <= half)
	{
	  ++level;
	  child += child;
	  if ((child < the_len) &&
		  ((*fun_ptr)(This[first + child], This[first + child - 1]) > 0))
		++child;
	}
	/* bottom-up-search for rotation point */
	for (;;)
	{
	  if (parent == child)
		break;
	  if ((*fun_ptr)(temp, This[first + child - 1]) <= 0)
		break;
	  child >>= 1;
	  --level;
	}
	/* rotate nodes from parent to rotation point */
	for (;level > 0; --level)
	{
	  This[first + (child >> level) - 1] =
		This[first + (child >> (level - 1)) - 1];
	}
	This[first + child - 1] = temp;
  } while (--the_len >= 1);
}


#define INSERTION_SORT_BOUND 16 /* boundary point to use insertion sort */

/* explain function
 * Description:
 *   fixarray::Qsort() is an internal subroutine that implements quick sort.
 *
 * Return Value: none
 */
void Qsort(int This[], CMPFUN fun_ptr, uint32 first, uint32 last)
{
  uint32 stack_pointer = 0;
  int first_stack[32];
  int last_stack[32];

  for (;;)
  {
	if (last - first <= INSERTION_SORT_BOUND)
	{
	  /* for small sort, use insertion sort */
	  uint32 indx;
	  int prev_val = This[first];
	  int cur_val;

	  for (indx = first + 1; indx <= last; ++indx)
	  {
		cur_val = This[indx];
		if ((*fun_ptr)(prev_val, cur_val) > 0)
		{
		  uint32 indx2;
		  /* out of order */
		  This[indx] = prev_val;

		  for (indx2 = indx - 1; indx2 > first; --indx2)
		  {
			int temp_val = This[indx2 - 1];
			if ((*fun_ptr)(temp_val, cur_val) > 0)
			{
			  This[indx2] = temp_val;
			}
			else
			  break;
		  }
		  This[indx2] = cur_val;
		}
		else
		{
		  /* in order, advance to next element */
		  prev_val = cur_val;
		}
	  }
	}
	else
	{
	  int pivot;

	  /* try quick sort */
	  {
	int temp;
	uint32 med = (first + last) >> 1;
		/* Choose pivot from first, last, and median position. */
		/* Sort the three elements. */
		temp = This[first];
		if ((*fun_ptr)(temp, This[last]) > 0)
		{
		  This[first] = This[last]; This[last] = temp;
		}
		temp = This[med];
		if ((*fun_ptr)(This[first], temp) > 0)
		{
		  This[med] = This[first]; This[first] = temp;
		}
		temp = This[last];
		if ((*fun_ptr)(This[med], temp) > 0)
		{
		  This[last] = This[med]; This[med] = temp;
		}
		pivot = This[med];
	  }
	  {
		uint32 up;
		{
		  uint32 down;
		  /* First and last element will be loop stopper. */
		  /* Split array into two partitions. */
		  down = first;
		  up = last;
		  for (;;)
	  {
		do
		{
		  ++down;
		} while ((*fun_ptr)(pivot, This[down]) > 0);

		do
		{
			  --up;
			} while ((*fun_ptr)(This[up], pivot) > 0);

		if (up > down)
		{
		  int temp;
			  /* interchange L[down] and L[up] */
			  temp = This[down]; This[down]= This[up]; This[up] = temp;
		}
		else
		  break;
	  }
	}
		{
		  uint32 len1; /* length of first segment */
		  uint32 len2; /* length of second segment */
		  len1 = up - first + 1;
		  len2 = last - up;
		  if (len1 >= len2)
		  {
			if ((len1 >> 5) > len2)
			{
			  /* badly balanced partitions, heap sort first segment */
			  HelperHeapSort(This, fun_ptr, first, len1);
			}
			else
			{
			  first_stack[stack_pointer] = first; /* stack first segment */
			  last_stack[stack_pointer++] = up;
			} 
			first = up + 1;
			/*  tail recursion elimination of
			 *  Qsort(This,fun_ptr,up + 1,last)
			 */
		  }
		  else
		  {
			if ((len2 >> 5) > len1)
			{
			  /* badly balanced partitions, heap sort second segment */
			  HelperHeapSort(This, fun_ptr, up + 1, len2);
			}
			else
			{
			  first_stack[stack_pointer] = up + 1; /* stack second segment */
			  last_stack[stack_pointer++] = last;
			}
			last = up;
			/* tail recursion elimination of
			 * Qsort(This,fun_ptr,first,up)
			 */
		  }
		}
		continue;
	  }
	  /* end of quick sort */
	}
	if (stack_pointer > 0)
	{
	  /* Sort segment from stack. */
	  first = first_stack[--stack_pointer];
	  last = last_stack[stack_pointer];
	}
	else
	  break;
  } /* end for */
}


void ArraySort(int This[], CMPFUN fun_ptr, uint32 the_len)
{
  Qsort(This, fun_ptr, 0, the_len - 1);
}

#define ARRAY_SIZE 250000

int my_array[ARRAY_SIZE];

void fill_array()
{
  int indx;

  for (indx=0; indx < ARRAY_SIZE; ++indx)
  {
	my_array[indx] = rand();
  }
}

int cmpfun(int a, int b)
{
  if (a > b)
	return 1;
  else if (a < b)
	return -1;
  else
	return 0;
}

int main()
{
  int indx;

  fill_array();

  ArraySort(my_array, cmpfun, ARRAY_SIZE);

  for (indx=1; indx < ARRAY_SIZE; ++indx)
  {
	if (my_array[indx - 1] > my_array[indx])
	{
	  printf("bad sort\n");
	  return(1);
	}
  }

  return(0);
}

[time1 13]

الله يعطيك العافيه اخي الحبيب garo , هذا مانحتاجه بالقسم .

سأقوم قريبا بوضعها مع مجموعة اخرى في موضوع دروس الاعضاء .

تحياتي لك .. :happy:

[Islamic_Empire 0]

أخي العزيز لا أدري لماذا اكوادك بهذا الطول

مثلا كود ال Bubble Sort هو :

void BubbleSort(Type array[],int size)
{
 int i;
 bool change = true;
while(change)
{
	 change = false;
   for(i=0; i < size - 1; i++)
   {
  if(array[i] > array[i+1])
  {
  swap((array[i],array[i+1]);
  change=true;
  }
   }
}
}

وكذللك الحال بالنسبة للخوارزميات الأخرى فهل كودك اكثر دقة أما ثد أخطأت في برمجة الخوارزمية

تم تعديل 7 Nov 2008 بواسطه Islamic_Empire

[garo 7]

أخي العزيز لا أدري لماذا اكوادك بهذا الطول

مرحبا اخي Islamic_Empire

هذه الامثلة تحتوي علي دالة الخوارزمية ودوال اخري مثل main لذلك تجد انها اطول بكثير

شكرا اخي time1

[commando161 11]

• Linear Search Algorithm
  
• Bubble Sort Algorithm
  
• Binary Search Algorithm
  

[garo 7]

• Linear Search Algorithm
  
• Bubble Sort Algorithm
  
• Binary Search Algorithm
  

هذه ثلاثة فقط وقد اكملت الباقي الي ثمانية

[commando161 11]

أنا كنت أقصد أخى garo ان تطلع عليهم , لعلهم يفيدوك ,,

وفقكم الله ,,,

[garo 7]

وانا لم اقصد اي شي مما قلت، بل قصدت طرح الخوارزميات الخاصة بالترتيب التي كتب عنها من قبل او لم يكتب في موضوع واحد شامل

شكرا اخي Omar Eladel

اتمني لك التوفيق

[اسراء شلبى 111]

جزاك الله كل خير

[khaled26 0]

جزاك الله كل خير