|
Сортировки
Задача: отсортировать массив
используя различные методы сортировок:
"Пузырьком",
"Отбора",
"Вставки",
"Шелла",
"Быстрая сортировка"
Решение:
----------------------- Файл L11.cpp
-----------------------
// Сортировка пузырьком
#ifndef __SORT_1_1
#define __SORT_1_1
template <class Stype> void bubble(Stype *item, int count){
register int a,b;
Stype t;
for(a=1;a<count;++a)
for(b=count-1;b>=a;--b){
if(item[b-1]>item[b]){
t=item[b-1];
item[b-1]=item[b];
item[b]=t;
}
}
}
#endif
----------------------- Файл L12.cpp
-----------------------
// Сортировка методом отбора
#ifndef __SORT_1_2
#define __SORT_1_2
template <class Stype> void select(Stype *item,int count){
register int a,b,c;
int exchange;
Stype t;
for(a=0;a<count-1;++a){
exchange = 0;
c=a;
t=item[a];
for(b=a+1;b<count;++b){
if(item[b]<t){
c=b;
t=item[b];
exchange=1;
}
}
if(exchange){
item[c]=item[a];
item[a]=t;
}
}
}
#endif
----------------------- Файл L13.cpp
-----------------------
// Сортировка методом вставки
#ifndef __SORT_1_3
#define __SORT_1_3
template <class Stype> void insert(Stype *item,int count){
register int a,b;
Stype t;
for(a=1;a<count;++a){
t=item[a];
for(b=a-1;b>=0&&t<item[b];b--)
item[b+1]=item[b];
item[b+1]=t;
}
}
#endif
----------------------- Файл L14.cpp
-----------------------
// Сортировка методом Шелла
#ifndef __SORT_1_4
#define __SORT_1_4
template <class Stype> void shell(Stype *item, int count){
register int i,j,gap,k;
Stype x;
char a[5]={9,5,3,2,1};
for(k=0;k<5;k++){
gap=a[k];
for(i=gap;i<count;++i){
x=item[i];
for(j=i-gap;x<item[j] && j>=0; j=j-gap)
item[j+gap]=item[j];
item[j+gap]=x;
}
}
}
#endif
----------------------- Файл L15.cpp
-----------------------
// Метод быстрой сортировки
#ifndef __SORT_1_5
#define __SORT_1_5
template <class Stype> void qs(Stype *item,int left,int right){
register int i,j;
Stype x,y;
i=left; j=right;
x=item[(left+right)/2];
do{
while(item[i]<x&&i<right)
i++;
while(x<item[j]&&j>left) j--;
if(i<=j){
y=item[i];
item[i]=item[j];
item[j]=y;
i++;y--;
}
}while(i<=j);
if(left<j) qs(item,left,j);
if(i<right) qs(item,i,right);
}
template <class Stype> void quick(Stype *item, int count){
qs(item,0,count-1);
}
#endif
----------------------- Файл L1.cpp
----------------------- (MAIN HERE)
#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include "l11.cpp" //Пузырьковая
#include "l12.cpp" //Отбора
#include "l13.cpp" //Вставки
#include "l14.cpp" //Шелла
#include "l15.cpp" //Быстрая сортировка
const char *so[5]={
"Пузырьком",
"Отбора",
"Вставки",
"Шелла",
"Быстрая сортировка"
};
int chooze(){
int i;
do{
printf("\nВыберите метод сортировки:\n"
"\t1 - %s\n"
"\t2 - %s\n"
"\t3 - %s\n"
"\t4 - %s\n"
"\t5 - %s\n?:"
,so[0],so[1],so[2],so[3],so[4]);
scanf("%d",&i);
}while(i<1||i>5);
return i;
}
void main(){
int *mas, // Сортируемый массив
n,i,aut,sp; char ch;
do{
clrscr();
printf("\nЧисло элементов: "); scanf("%d",&n);
printf("\nАвтозаполнение? (1-Да,0-Нет): "); scanf("%d",&aut);
mas = new int[n];
for(i=0;i<n;i++){
printf("Mas[%d]=",i);
if(aut){
mas[i]=rand(); printf("%d\t",mas[i]);
} else
scanf("%d",&mas[i]);
}
sp=chooze();
switch(sp){
case 1: bubble(mas,n); break;
case 2: select(mas,n); break;
case 3: insert(mas,n); break;
case 4: shell(mas,n); break;
case 5: quick(mas,n);
break;
};
printf("Отсортированный массив: \n");
for(i=0;i<n;i++){
printf("Mas[%d]=%d\t",i,mas[i]);
}
printf("\nИспользован способ: %s
\n",so[sp-1]);
delete [] mas;
printf("\nПродолжить (Y-да) ");
ch=getche();
}while(ch=='Y'||ch=='y');
clrscr();
printf("Bye");
}
[Top] [Home]
|
