Сортировка : реализация

по отношению к критерию сортировки
Гибкость по отношению к базовому типу
Примеры

отношению к критерию сортировки
Гибкость по отношению к базовому типу
Примеры

A[N], i, j, c;
// заполнить массив
// вывести

исходный массив
for (i=0; i for (j=N-2; j>= i; j--)
if ( A[j] > A[j+1] ) {
с = A[j];
A[j] = A[j+1];
A[j+1] = с;
}
}
// вывести итоговый массив
}

Пузырьковая сортировка

A[N], int B[2*N], i, j, c;
// заполнить массивы A,B

// вывести массивы A,B
for (i=0; i for (j=N-2; j>= i; j--)
if ( A[j] > A[j+1] ) {
с = A[j];
A[j] = A[j+1];
A[j+1] = с;
}
}
// ???????????????????
// вывести массивы A,B
}

Как запрограммировать сортировку массивов A и B?

Как отсортировать 2, 3,… массива?

A[N], int B[2*N], i, j, c;
// заполнить массивы A,B

// вывести массивы A,B
// сортировать A
for (i=0; i for (j=N-2; j>= i; j--)
if ( A[j] > A[j+1] ) {
с = A[j];
A[j] = A[j+1];
A[j+1] = с;
}
}
// сортировать B
for (i=0; i<2*N-1; i++){
for (j=2*N-2; j>=i; j--)
if ( B[j] > B[j+1] ) {
с = B[j];
B[j] = B[j+1];
B[j+1] = с;
}
}
// вывести массивы A,B
}

Как запрограммировать сортировку массивов A и B?

Как отсортировать 2, 3,… массива?

Простое решение: сдублировать фрагмент кода, сортирующего A

n) {
int i, j, c;
for (i=0; i

for (j=n-2; j>= i; j--)
if ( a[j] > a[j+1] ) {
с = a[j];
a[j] = a[j+1];
a[j+1] = с;
}
}
void main() {
const int N = 10;
int A[N], int B[2*N];
// заполнить массивы A,B
// вывести массивы A,B // сортировать A,B
bubble_sort(A,N);
bubble_sort(B,2*N);
// вывести массивы A,B
}

Как отсортировать 2, 3,… массива?

Хорошее решение: описать процедуру сортировки и вызвать ее для A и B

n) {
int i, j, c;
for (i=0; i

for (j=n-2; j>= i; j--)
if ( a[j] > a[j+1] ) {
с = a[j];
a[j] = a[j+1];
a[j+1] = с;
}
}
void main() {
const int N = 10;
int A[N], int B[2*N];
// заполнить массивы A,B
// вывести массивы A,B // сортировать A,B
bubble_sort(A,N);
bubble_sort(B,2*N);
// вывести массивы A,B
}

Как сделать гибкой процедуру сортировки?

Хорошее решение: сделать критерий сортировки одним из параметров процедуры сортировки

Как устранить зависимость от критерия сортировки?

y){
return x>y;
}

// процедура сравнения «x < y»
int is_less(int

x, int y){
return x}

// процедура сортировки массива
void bubble_sort(int *a, int n,
int (*cmp)(int x, int y))
{
int i, j, c;
for (i=0; i for (j=n-2; j>=i; j--)
if ( cmp(a[j],a[j+1]) ) {
с = a[j];
a[j] = a[j+1];
a[j+1] = с;
}
}
}

Как сделать гибкой процедуру сортировки?

void main() {
const int N = 10;
int A[N], int B[2*N];
// заполнить массивы A,B
// вывести массивы A,B // сортировать A по возрастанию
bubble_sort(A,N,is_greater);
// сортировать B по убыванию
bubble_sort(B,2*N,is_less);
// вывести массивы A,B
}

Разные критерии сортировки

Единая процедура сортировки, инвариантная к критерию

y){
return x>y;
}

// процедура сравнения «x < y»
int is_less(int

x, int y){
return x}

// процедура сортировки массива
void bubble_sort(int *a, int n,
int (*cmp)(int x, int y))
{
int i, j, c;
for (i=0; i for (j=n-2; j>=i; j--)
if ( cmp(a[j],a[j+1]) ) {
с = a[j];
a[j] = a[j+1];
a[j+1] = с;
}
}
}

Как сделать гибкой процедуру сортировки?

void main() {
const int N = 10;
int A[N], int B[2*N];
// заполнить массивы A,B
// вывести массивы A,B // сортировать A по возрастанию
bubble_sort(A,N,is_greater);
// сортировать B по убыванию
bubble_sort(B,2*N,is_less);
// вывести массивы A,B
}

Как устранить зависимость от базового типа?

Решение:
Сделать универсальным сравнение
Сделать универсальной перестановку

const void *y, int sz)

{
char t[MAXSIZE];
memcpy(t,x,sz);
memcpy(x,y,sz);
memcpy(y,t,sz);
}

// процедура сортировки массива
void bubble_sort(void *a, int n, int size, int (*cmp)(const void *x, const void *y)) {
int i, j, c;
for (i=0; i for (j=n-2; j>=i; j--)
if ( cmp(&a[j],&a[j+1]) )
swap(&a[j],&a[j+1],size);
}

Как сделать гибкой процедуру сортировки?

// процедура сравнения «x < y»
int is_less_i(const void *x, const void *y) {
return *(int*)x < *(int*) y;
}
// процедура сравнения «x < y»
int is_more_f(const void *x, const void *y) {
return *(float*)x > *(float*) y;
}

void main() {
const int N = 10;
int A[N], float B[2*N];
// заполнить массивы A,B
// вывести массивы A,B // сортировать A по убыванию
bubble_sort(A,N,sizeof(int), is_less_i);
// сортировать B по возрастанию
bubble_sort(B,2*N,sizeof(float),
is_more_f);
// вывести массивы A,B
}

memcpy() из string.h копирует область памяти указанного размера

Для перестановки надо знать адреса элементов и их размер

Процедура сравнения «знает» какого типа элементы и умеет их сравнивать, получив адреса

При вызове процедуры сортировки надо указать размер базового типа и подходящий критерий

const void *y, int sz)

{...}

// процедура сортировки массива
void bubble_sort(void *a, int n, int size, int (*cmp)(const void *x, const void *y))
{...}

typedef struct point_t {
float x,y;
} Point;

// процедура сравнения a.x < b.x
int cmp_by_x(const void *a, const void *b) {
return ((Point*)a)->x < ((Point*)b)->x;
}

Как сделать гибкой процедуру сортировки?

// процедура сравнения a.x < b.x
int cmp_by_y(const void *a, const void *b) {
return ((Point*)a)->y > ((Point*)b)->y;
}

void main() {
const int N = 10;
Point A[N];
// заполнить массив A
// вывести массивы A // сортировать A по убыванию x
bubble_sort(A,N,sizeof(Point), cmp_by_x);
// сортировать A по возрастанию y
// вывести массив A
bubble_sort(A,N,sizeof(Point),
cmp_by_y);
// вывести массив A
}

Пользовательский тип «Точка»

Процедура сравнения элементов типа «Точка»

Сортировка массива точек по убыванию абсцисс

Сортировка массива точек по возрастанию ординат

критерию сортировки
к типу сортируемых данных

Пользователю процедуры сортировки необходимо
определять процедуры сравнения

элементов нужных типов
при вызове процедуры сортировки явно указывать
нужный критерий сортировки
размер элементов массива

Примером реализации «гибкой» схемы являются стандартные функции qsort, bsearch, lsearch

массива
Гибкость по отношению к критерию сортировки
Гибкость по отношению к базовому

типу
Примеры