/* функция сортировки возвращает указатель на начало
отсортированного списка */
SP1 *pocket(SP1 *q,int t) {
/* t - разрядность (максимальная длина числа) */
int i,j,k,m=1;
SP1 *r, *gg, *a[10], *b[10];
gg=q;
for(j=1;j<=t;j++) {
for(i=0;i<=9;i++) a=(b=NULL);
while(q!=NULL) {
k=((int)(q->val/m))%(int)10;
r=b[k];
if (a[k]==NULL) a[k]=q; else r->next=q;
r=b[k]=q;
q=q->next;
r->next=NULL;
}
for(i=0;i<=9;i++) if (a!=NULL) break;
q=a;
r=b;
for(k=i+1;k<=9;k++)
if(a[k]!=NULL) {
r->next=a[k];
r=b[k];
}
m=m*10;
}
return (gg);
}
/* Тестовая программа */
void main() {
int i;
SP1 *q, *r;
/* Это будем сортировать */
long a[14]={ 0,7,8,3,52,14,16,18,15,13,42,30,35,26 };
q=(SP1 *)malloc(sizeof(SP1));
q->val=a[0];
r=q;
for(i=1;i<14;i++) { /* формирование списка */
r->next=(SP1 *)malloc(sizeof(SP1));
r->next->val=a;
r=r->next;
}
r->next = NULL;
/* Список сформирован, q указывает на начало */
r=pocket(q,2); /* Запускаем сортировку */
printf("\nresult:\n"); /* печать результатов */
while (r!=NULL) {
printf(" %d",r->val);
r=r->next;
}
}
Распределяющая сортировка в C++.
Есть такая курсовая работа- Распределяющая сортировка
Разработать приложение для реализации и анализа распределяющей сортировки. Функции приложения:
– задание размера сортируемой матрицы (при заполнении);
– интерактивное заполнение матрицы для сортировки;
– сохранение несортированной матрицы в файл;
– загрузка несортированной матрицы из заранее записанного файла;
– реализация алгоритма;
– оценка алгоритма по времени выполнения для различного критерия инверсии;
– оценка алгоритма по количеству выполненных операций перестановки (рассчитать для каждого элемента матрицы).
Вот распределяющая сортировка списка , пробую ее использовать, но не как...
Разработать приложение для реализации и анализа распределяющей сортировки. Функции приложения:
– задание размера сортируемой матрицы (при заполнении);
– интерактивное заполнение матрицы для сортировки;
– сохранение несортированной матрицы в файл;
– загрузка несортированной матрицы из заранее записанного файла;
– реализация алгоритма;
– оценка алгоритма по времени выполнения для различного критерия инверсии;
– оценка алгоритма по количеству выполненных операций перестановки (рассчитать для каждого элемента матрицы).
Вот распределяющая сортировка списка , пробую ее использовать, но не как...
Код:
Потом Решил сделать так - задать матрицу , потом присвоить значения каждого элемента к массиву, сортировать . потом вывести отсторированную матрицу, н оу меян проблема , выводит слишком цифры длинные , не такие как ввел и я тайм оут...
Код:
/* распределяющая сортировка списка */
#include <stdlib.h>
#include <stdio.h>
#include <iostream.h>
#include <conio.h>
typedef struct SP1_ {
long val;
struct SP1_ *next;
} SP1;
/* функция сортировки возвращает указатель на начало отсортированного списка */
SP1 *pocket(SP1 *q,int t) {
/* t - разрядность (максимальная длина числа) */
int i,j,k,m=1;
SP1 *r, *gg, *a[10], *b[10];
gg=q;
for(j=1;j<=t;j++) {
for(i=0;i<=9;i++) a=(b=NULL);
while(q!=NULL) {
k=((int)(q->val/m))%(int)10;
r=b[k];
if (a[k]==NULL) a[k]=q; else r->next=q;
r=b[k]=q;
q=q->next;
r->next=NULL;
}
for(i=0;i<=9;i++) if (a!=NULL) break;
q=a;
r=b;
for(k=i+1;k<=9;k++)
if(a[k]!=NULL) {
r->next=a[k];
r=b[k];
}
m=m*10;
}
return (gg);
}
/* Тестовая программа */
void main() {
int i;
int ll[4][4];
int x,y;
SP1 *q, *r;
int a[16];
/* Это будем сортировать */
//a[14]={ 0,7,8,3,52,14,16,18,15,13,42,30,35,26 };
//МАТРИЦАААААААААААААААААА
cout<<"BBedi!\n";
{ for(x=0; x<4; x++)
for(y=0; y<4; y++)
cin>>ll[x][y];
}
for(int x=0; x<4;x++){ //Типа присваиваю матрицу к массиву
for(int y=0; y<4;y++){
int i=0;
ll[x][y]=a;
i++;}}
q=(SP1 *)malloc(sizeof(SP1));
q->val=a[0];
r=q;
for(i=1;i<14;i++) { /* формирование списка */
r->next=(SP1 *)malloc(sizeof(SP1));
r->next->val=a;
r=r->next;
}
r->next = NULL;
/* Список сформирован, q указывает на начало */
r=pocket(q,2); /* Запускаем сортировку */
printf("\nresult:\n"); /* печать результатов */
while (r!=NULL) {
printf(" %d",r->val);
r=r->next;
}
getch();
}
#include <stdlib.h>
#include <stdio.h>
#include <iostream.h>
#include <conio.h>
typedef struct SP1_ {
long val;
struct SP1_ *next;
} SP1;
/* функция сортировки возвращает указатель на начало отсортированного списка */
SP1 *pocket(SP1 *q,int t) {
/* t - разрядность (максимальная длина числа) */
int i,j,k,m=1;
SP1 *r, *gg, *a[10], *b[10];
gg=q;
for(j=1;j<=t;j++) {
for(i=0;i<=9;i++) a=(b=NULL);
while(q!=NULL) {
k=((int)(q->val/m))%(int)10;
r=b[k];
if (a[k]==NULL) a[k]=q; else r->next=q;
r=b[k]=q;
q=q->next;
r->next=NULL;
}
for(i=0;i<=9;i++) if (a!=NULL) break;
q=a;
r=b;
for(k=i+1;k<=9;k++)
if(a[k]!=NULL) {
r->next=a[k];
r=b[k];
}
m=m*10;
}
return (gg);
}
/* Тестовая программа */
void main() {
int i;
int ll[4][4];
int x,y;
SP1 *q, *r;
int a[16];
/* Это будем сортировать */
//a[14]={ 0,7,8,3,52,14,16,18,15,13,42,30,35,26 };
//МАТРИЦАААААААААААААААААА
cout<<"BBedi!\n";
{ for(x=0; x<4; x++)
for(y=0; y<4; y++)
cin>>ll[x][y];
}
for(int x=0; x<4;x++){ //Типа присваиваю матрицу к массиву
for(int y=0; y<4;y++){
int i=0;
ll[x][y]=a;
i++;}}
q=(SP1 *)malloc(sizeof(SP1));
q->val=a[0];
r=q;
for(i=1;i<14;i++) { /* формирование списка */
r->next=(SP1 *)malloc(sizeof(SP1));
r->next->val=a;
r=r->next;
}
r->next = NULL;
/* Список сформирован, q указывает на начало */
r=pocket(q,2); /* Запускаем сортировку */
printf("\nresult:\n"); /* печать результатов */
while (r!=NULL) {
printf(" %d",r->val);
r=r->next;
}
getch();
}
немного исправил , но все равно проблемы, нужно увеичитть диапазон сортировки
Код:
#include <stdlib.h>
#include <stdio.h>
#include <iostream.h>
#include <conio.h>
typedef struct SP1_
{
long val;
struct SP1_ *next;
} SP1;
/* функция сортировки возвращает указатель на начало отсортированного списка */
SP1 *pocket(SP1 *q,int t) {
/* t - разрядность (максимальная длина числа) */
int i,j,k,m=1;
SP1 *r, *gg, *a[10], *b[10];
gg=q;
for(j=1;j<=t;j++) {
for(i=0;i<=9;i++) a=(b=NULL);
while(q!=NULL) {
k=((int)(q->val/m))%(int)10;
r=b[k];
if (a[k]==NULL) a[k]=q; else r->next=q;
r=b[k]=q;
q=q->next;
r->next=NULL;
}
for(i=0;i<=9;i++) if (a!=NULL) break;
q=a;
r=b;
for(k=i+1;k<=9;k++)
if(a[k]!=NULL) {
r->next=a[k];
r=b[k];
}
m=m*10;
}
return (gg);
}
/* Тестовая программа */
void main() {
int i;
int ll[4][4];
int x,y;
SP1 *q, *r;
int a[16];
/* Это будем сортировать */
//a[14]={ 0,7,8,3,52,14,16,18,15,13,42,30,35,26 };
//МАТРИЦАААААААААААААААААА
cout<<"BBedi!\n";
{ for(x=0; x<4; x++)
for(y=0; y<4; y++)
cin>>ll[x][y];
}
for(int x=0,i=0; x<4;x++)
{ //Типа присваиваю матрицу к массиву
for(int y=0; y<4;y++)
{
a=ll[x][y];
i++;
}
}
q=(SP1 *) malloc(sizeof(SP1));
q->val=a[0];
r=q;
for(i=1;i<x*y;i++) { /* формирование списка */
r->next=(SP1 *) malloc(sizeof(SP1));
r->next->val=a;
r=r->next;
}
r->next = NULL;
/* Список сформирован, q указывает на начало */
r=pocket(q,2); /* Запускаем сортировку */
printf("\nresult :\n"); /* печать результатов */
while (r!=NULL) {
printf(" %d",r->val);
r=r->next;
}
getch();
}
#include <stdio.h>
#include <iostream.h>
#include <conio.h>
typedef struct SP1_
{
long val;
struct SP1_ *next;
} SP1;
/* функция сортировки возвращает указатель на начало отсортированного списка */
SP1 *pocket(SP1 *q,int t) {
/* t - разрядность (максимальная длина числа) */
int i,j,k,m=1;
SP1 *r, *gg, *a[10], *b[10];
gg=q;
for(j=1;j<=t;j++) {
for(i=0;i<=9;i++) a=(b=NULL);
while(q!=NULL) {
k=((int)(q->val/m))%(int)10;
r=b[k];
if (a[k]==NULL) a[k]=q; else r->next=q;
r=b[k]=q;
q=q->next;
r->next=NULL;
}
for(i=0;i<=9;i++) if (a!=NULL) break;
q=a;
r=b;
for(k=i+1;k<=9;k++)
if(a[k]!=NULL) {
r->next=a[k];
r=b[k];
}
m=m*10;
}
return (gg);
}
/* Тестовая программа */
void main() {
int i;
int ll[4][4];
int x,y;
SP1 *q, *r;
int a[16];
/* Это будем сортировать */
//a[14]={ 0,7,8,3,52,14,16,18,15,13,42,30,35,26 };
//МАТРИЦАААААААААААААААААА
cout<<"BBedi!\n";
{ for(x=0; x<4; x++)
for(y=0; y<4; y++)
cin>>ll[x][y];
}
for(int x=0,i=0; x<4;x++)
{ //Типа присваиваю матрицу к массиву
for(int y=0; y<4;y++)
{
a=ll[x][y];
i++;
}
}
q=(SP1 *) malloc(sizeof(SP1));
q->val=a[0];
r=q;
for(i=1;i<x*y;i++) { /* формирование списка */
r->next=(SP1 *) malloc(sizeof(SP1));
r->next->val=a;
r=r->next;
}
r->next = NULL;
/* Список сформирован, q указывает на начало */
r=pocket(q,2); /* Запускаем сортировку */
printf("\nresult :\n"); /* печать результатов */
while (r!=NULL) {
printf(" %d",r->val);
r=r->next;
}
getch();
}