while(t<end)
{ for(f=end; ps1>=t; ps1--, ps2--)
if(*ps1>*ps2)
{ m=*ps1;
*ps1=*ps2;
*ps2=m;
f=ps2;
}
t=f;
ps1=end1;
ps2=end;
Пример программы:
#include "stdio.h"
void sort(char* str, int n)
{
char m; // Для обмена символов
char *end=str+n-1; // Указатель на конец массива
char *end1=str+n-2;
char *ps1=end1, *ps2=end; // Указатели на элементы
char *t=str; // Указатель на конец сортированных элементов
char *f; // Указатель на последний обмен. элемент
while(t<end)
{
for(f=end; ps1>=t; ps1--, ps2--)
if(*ps1>*ps2)
{
m=*ps1;
*ps1=*ps2;
*ps2=m;
f=ps2;
}
#ifdef DEBUG_SORT
printf("massive - %s, f=%i\n", str, f-str);
#endif
t=f;
ps1=end1;
ps2=end;
}
}
int check_sort(char* str, int n)
{
int i, f=1;
for(i=0; i<n-1; i++)
if(str[i]>str[i+1]) f=0;
return f;
}
int main()
{
char a[4][9] = {"87654321",
"12345678",
"21436587",
"16273845"};
int i;
for(i=0; i<4; i++)
{
printf("test %i\n", i);
printf("massive - %s\n", a[i]);
sort(a[i], 8);
printf("sort - %s\n", a[i]);
if(check_sort(a[i], 8)) printf("test passed\n\n");
else printf("test failed\n\n");
}
}
Парадигма «разделяй и властвуй»
Разделяй и властвуй (divide and conquer)— в информатике важная парадигма разработки алгоритмов. Основана на рекурсивном разбиении решаемой задачи на две (или более) подзадачи того же типа, но меньшего размера. Разбиения выполняются до тех пор, пока все подзадачи не окажутся элементарными.
