Сортировки

В лекциях 14 и 15

мы рассматривали более подробно различные способы сортировки. Здесь мы напоминаем некоторые из них и приводим пример программ.

Сортировка упорядочивает совокупность объектов в соответствии с заданным отношением порядка. Ключ сортировки - поле или группа полей элемента сортировки, которые используются при сравнении во время сортировки. Сортирующая последовательность - схема упорядочивания. Например, можно взять последовательность символов алфавита, задающую способ упорядочения строк этого алфавита.

Способ сортировки: сортировка по возрастанию, сортировки по убыванию. Методы сортировки:

метод прямого выбора;
метод пузырька;
метод по ключу;
сортировки слиянием;
сортировки Батчера.

Сортировка по возрастанию - это сортировка, при которой записи упорядочиваются по возрастанию значений ключевых полей.

Сортировка по убыванию - это сортировка, при которой записи упорядочиваются по убыванию значений ключевых полей.

Сортировка методом пузырька (пузырьковая сортировка) - способ сортировки, заключающийся в последовательной перестановке соседних элементов сортируемого массива.

Сортировка по ключу - это сортировка записей с упорядочением по значению указанного поля или группы полей.

Сортировка слиянием - это внешняя сортировка, при которой на первом этапе группы записей сортируются в оперативной памяти и записываются на несколько внешних носителей; на втором этапе упорядоченные группы сливаются с нескольких внешних носителей на один носитель данных. Носитель данных - материальный объект, предназначенный для хранения данных, или среда передачи данных.

Сортировка Батчера - это сортировка, внутренний алгоритм которой работает за время

Программа 5. Сортировка массива по возрастанию методом пузырька.

//Данные, которые нужно отсортировать, берутся из файла "massiv.txt", //результат записывается в массив int mas['K'] и выводится на экран // Алгоритм реализован на Turbo C++. #include <conio.h> #include <stdio.h> #define K 1000; //Размер массива

int mas['K']; int n; void puzirek()// функция сортирует массив по возрастанию методом пузырька { int i,j,t; for(i=0;i<n;i++) for(j=1;j<n-i;j++) if(mas[j]<mas[j-1]) { t=mas[j]; mas[j]=mas[j-1]; mas[j-1]=t; } }

int main() { clrscr(); FILE *filePointer=fopen("massiv.txt","r"); int i=0; while (!feof(filePointer)) { fscanf(filePointer,"%d",&mas[i]); i++; } n=i; puzirek(); for(i=0;i<n;i++) printf("%d ",mas[i]); //scanf("%d",&n); getch(); return 0; }

Программа 6. Пузырьковая сортировка и сортировка методом прямого выбора.

{Сортировка. Алгоритм реализован на языке программирования Turbo-Pascal} uses crt; var M, N : array[0..10] of integer; i:integer;

procedure Input; begin for i := 0 to 10 do begin writeln('Число'); readln(M[i]); {Ввод массива} end; end;

Procedure Sort1; {Пузырьковый метод сортировки} var q,i,x:integer; begin

for i:=10 downto 0 do begin for q:=0 to 10 do if M[q]<M[q+1] then begin x:=M[q]; M[q]:=M[q+1]; M[q+1]:=x end; end; end;

procedure Sort2; {Метод прямого выбора} var i,j,k,x:integer; begin for i:=0 to 9 do begin k:=i; x:=M[i]; for j:=i+1 to 10 do if M[j] >x then begin k:=j; x:=M[k]; end; M[k]:= M[i]; M[i]:=x; end; end;

{---------------------------------------------} begin clrscr; input; {Ввод исходного массива} writeln('Исходный массив'); for i:=0 to 10 do write(M[i],' '); {Вывод исходного массива} writeln; Sort1;{Сортировка массива методом пузырька} writeln ('Сортированный массив'); for i:=0 to 10 do write(M[i],' '); {Вывод отсортированного массива} input; {Ввод исходного массива} writeln('Исходный массив'); for i:=0 to 10 do write(M[i],' '); {Вывод исходного массива} writeln;

sort2; writeln ('Сортированный массив методом прямого выбора'); for i:=0 to 10 do write(M[i],' '); {Вывод отсортированного массива} readln; end.

Программа 7. Сестры.

//Две строки матрицы назовем сестрами, если совпадают //множества чисел, встречающихся в этих строках. Программа //определяет всех сестер матрицы, если они есть, //и выводит номера строк.

Алгоритм реализован на Turbo C++. //#include <graphics.h> #include <stdlib.h> //#include <string.h> #include <stdio.h> #include <conio.h> //#include <math.h> #include <dos.h> #include <values.h> #include <iostream.h>

const n=4,//кол-во строк m=4; //столбцов

int m1[n][m]; //исходный массив struct mas{int i,i1;}; //i-индекс сравниваемой строки с i1 строкой mas a[n*2]; // массив типа mas, где будут лежать сестры, пример) a[1].i и a[1].i1 - сестры

void main() {clrscr(); int i,j; randomize(); for( i=0;i<n;i++) for( j=0;j<m;j++) m1[i][j]=random(2); //случайным образом в массив заносим цифры

for(i=0;i<n;i++) {printf("\n %d) ",i); for(int j=0;j<m;j++) printf(" %d",m1[i][j]); //распечатываем этот массив } int min, p; //индекс минимального элемента после s-го элемента i-ой строки //сортировка строк массива по возрастанию for(i=0;i<n;i++)//i-сортировка i-ой строки { for(int s=0;s<m-1;s++) {min=m1[i][s+1]; for(int j=s;j<m;j++) if(m1[i][j]<=min){min=m1[i][j];p=j;} //запоминаем минимальный элемент в ряде после s-го элемента if(m1[i][s]>=min) {m1[i][p]=m1[i][s];m1[i][s]=min;} //меняем местами s-й и p-й элемент,если s-й>p-го(минимального) }

}

printf("\n"); for(i=0;i<n;i++) {printf("\n %d) ",i); for(int j=0;j<m;j++) printf(" %d",m1[i][j]); //выводим отсортированный массив } int s=0 //сколько элементов в i-й строке совпадают с эл-ми i1 строки, k=0; //сколько строк совпали int i1; for(i=0;i<n-1;i++) //верхняя строка i for( i1=i+1;i1<n;i1++) //нижняя строка i1 {s=0; for(int j=0;j<m;j++) //сравнение идет по j-му столбцу // ! ! if(m1[i][j]==m1[i1][j])s++; //если соответствующие элементы в //i-й и i1-й строки совпадают, то кол-во совпавших увеличивается на 1 if(s==m){a[k].i=i;a[k].i1=i1;k++;} //если все элементы i-й и i1-й строки совпали, то они сестры }

printf("\nСестры :"); for(i=0;i<k;i++) printf("\n %d и %d",a[i].i,a[i].i1); //распечатываем a[i].i-ю и a[i].i1-ю сестру getch(); }

Программа 8. Поиск узоров из простых чисел.

//Построить матрицу А(15 Х 15)таким образом: А(8,8)=1, затем //по спирали против часовой стрелки, //увеличивая значение очередного элемента на единицу //и выделяя все простые числа красным цветом, заполнить матрицу //Алгоритм реализован на Turbo C++.

#include <stdio.h> #include <conio.h>

void main(void) { clrscr(); int mas[15][15]; int n=1,x=6,y=6,k=1; int i,j; while(1){ mas[x][y]=k++; switch(n){ case 1: x++;break; case 2: y--;break; case 3: x--;break; case 4: y++;break; } if(x==15) break;

if(x==y && x<6) n=4; else if(x+y==12 && x<6) n=1; else if(x+y==12 && x>6) n=3; else if(x==y+1 && x>6) n=2;

}

for(i=0;i<15;i++) { for(j=0;j<15;j++) { textcolor(12); if(mas[j][i]>2) for(k=2;k<mas[j][i];k++) if(mas[j][i]%k==0) textcolor(15); cprintf("%3d ",mas[j][i]); } printf("\n"); }

getch(); }

Программа 9. Сортировка строк матрицы.

//Cортировка строк матрицы. В каждой строке подсчитывается сумма //простых чисел. Полученный вектор упорядочивается по возрастанию. //Строки матрицы переставляются по новому вектору. //Алгоритм реализован на Turbo C++. #include<stdio.h> #include<conio.h>

#define n 5

struct summa { int value; int idx; } sum,massum[n],a;

void main(void){ clrscr(); int mas1[n][n],mas[n][n]={{1,1,1,1,1}, {3,16,11,6,4}, {8,10,15,23,1}, {3,8,10,15,3}, {7,3,20,15,10}};

int i,j,k,flag;

for(i=0;i<n;i++){ sum.value=0; for(j=0;j<n;j++){ flag=0; if(mas[i][j]>2) for(k=2;k<mas[i][j];k++) if(mas[i][j]%k==0) flag=1; if(flag==0) sum.value=sum.value+mas[i][j]; } sum.idx=i; massum[i]=sum; }

for(i=0;i<n-1;i++) for(j=0;j<n-1-i;j++){ if (massum[j].value>massum[j+1].value){ a=massum[j]; massum[j]=massum[j+1]; massum[j+1]=a; } }

for(i=0;i<n;i++) for(j=0;j<n;j++) mas1[i][j]=mas[massum[i].idx][j];

for(i=0;i<n;i++){ for(j=0;j<n;j++) printf("%3d ",mas[i][j]); printf("\n"); }

printf("\n\n\n");

for(i=0;i<n;i++){ for(j=0;j<n;j++) printf("%3d ",mas1[i][j]); printf("\n"); } getch(); }

Содержание раздела