السلام عليكم ورحمه الله وبركاتـــه .. :
بحثت في هذا المنتدى عن الـ Merge sort و Quick Sort .. ووجدت هالكوديــن ولكن كبيرييييين جداااااااااااااااااااا
هذا الـ quick sort
#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);
}وهذا الـ merge sort ولكنه كبير جدا ايضا
==============
[code]#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);
}============
ولكــن بالمقـابل بحثت في النــت .. ووجدت هــذا كـود الـ Merge sort بسسسيط جداا .. !!
ولكن ايــهم الصـح
void Merge(int *arr,int low,int high)
{
int *temp = new int[size];
int mid = (low+high)/2;
int i=low ,j=mid+1, k=low;
while(i<=mid && j<=high)
{
if(arr < arr[j])
temp[k++] = arr[i++];
else if(arr[j] < arr)
temp[k++] = arr[j++];
else
{
temp[k++] = arr[i++];
temp[k++] = arr[j++];
}
}
while(i<=mid)
temp[k++] = arr[i++];
while(j<=high)
temp[k++] = arr[j++];
for(i=low; i<=high; i++)
arr = temp;
delete temp;
}
void MergeSort(int *arr,int low,int high)
{
if(low < high)
{
int mid = (low+high)/2;
MergeSort(arr,low,mid);
MergeSort(arr,mid+1,high);
Merge(arr,low,high);
}
}ولكن لم اجد الـ quick sort واتمنى ان احد يعملي الداله quick sort ويشرحها ويشرح طريقة عملها
وشكرا.
واتمنى احد يقولي ايهـم الصـح وايـهم الخطاء .. !! واذا كان كلهم صح .. اتمنى احد يشرح لي المختصر .. "
