14
, . , , , . . (, qsort () ), , . . .
:
- , ;
- , ;
- , .
, . .
. . , . "" "", "" - . . " " , "" , "". , "" . n-1 , , "" .
/* ( ) */
void sort_bubl(int *x, int n)
{
int i,j,buf;
/* '', */
for (i=0;i<n;i++)
/* '',
n-i- */
for (j=0;j<n-i-1;j++)
/* */
if (*(x+j)>*(x+j+1))
{buf=*(x+j); *(x+j)= *(x+j+1); *(x+j+1)=buf;}
}
, ( ) .
. : , i- , , , , i- . , , .
/* */
void sort_min (int *x, int n) {
|
|
|
int i,j,k,buf;
/* ,
*/
for (i=0;i<n-1;i++) {
/* , (i+1)-
*/
for (k=i, j=i+1; j<n; j++)
// k-
if (*(x+j)< *(x+k)) k=j;
//
buf=*(x+k); (x+k) = *(x+i); *(x+i)=buf;
}
}
, . , , , .
. Donald Lewis Shell 1959. , , , . (gap) , ( ).
. n/2, .. 1/2 , . gap . , . , gap .
. :
41, 53, 11, 37, 79, 19, 7, 61.
:
| (0,4), (1,5) | 1- | ||||||||
| (2,6), (3,7) | |||||||||
| (0,2),(1,3),(2,4),(3,5),(4,6),(5,7) | 2- | ||||||||
| (0,2),(1,3),(2,4),(3,5),(4,6),(5,7) | |||||||||
| (3- ). |
.
:
/* */
void sort_sh(int *x, int n)
{
int i, j; //
int buffer; //
int gap; //
int sorted; //
for (gap = n/2; gap > 0; gap /= 2) //
Do
{
sorted = 0;
for (i = 0, j = gap; j < n; i++, j++)
if (*(x+i) > *(x+j)) // gap
{ //
buff = *(x+j); *(x+j) = *(x+i); *(x+i) = buff;
sorted = 1; // ,
}
} while (sorted); //
}
void main ()
{
int x[]={2,5,9,1,4,3,8,7,6,0};
sort_sh(x,10);
}
. (Charles Antony Richard Hoare, 1962 .), (QuickSort) : , , , - . , . . .
|
|
|
. , i j, , , - . . , i j. , l r, - j i. ( i<r j>l), .
, : 13,3,23,19,7,53,29,17. , - , - . i , j . :
13 3 23 19 7 53 29 17
13 3 17 19 7 53 29 23
13 3 17 7 19 53 29 23
13 3 17 7 19 53 29 23
3 13 17 7 19 23 29 53
13 17 7
13 7 17
: 3 7 13 17 19 23 29 53
:
void main ()
{
void Hoare(int *, int, int); //
int x[10] = {7,2,4,0,3,1,9,6,8,5}; //
int n=10;
//......
Hoare(x,0,n-1); //
/* */
//......
}
/* */
void Hoare(int *x, int l, int r) // /
{
int i, j; //
int buffer; //
int sr = x[(l+r)/2]; //
i = 1;
j = r; //
Do
{
while (x[i] < sr) i++; //
while (x[j] > sr) j--; //
if (i <= j) //
{ //
buff = x[i]; x[i] = x[j]; x[j] = buff;
i++; j--; //
}
} while (i <= j); //
//
if (i < r) // -
Hoare(x,i,r); //
if (j>l) // -
Hoare(x,l,j); //
}
( ) .
:
srand((unsigned)time(NULL));
for (i=0;i<n; i++)
{
a[i] = rand()%10;
}
: , . :
1) .
2) ""
3)
4) .
.
*-. , - (+1/-1) .
#include <iostream>
using namespace std;
int array[100];
void Sort(int col)
{
int trash=0;
int f=1;
for (int i=1; (i<=col) && (f=1); i++)
{
f=-1;
//
for (int j=i; j<=col-i; j++)
{
//
if (array [j]>array [j+1])
{
// ,
trash=array[j];
//
array [j]=array [j+1];
array [j+1]=trash;
f=1;
}
}
//
for (int j=col-i-1; j>i; j--)
{
//
if (array [j]<array[j-1])
{
// ,
|
|
|
trash=array[j];
//
array [j]=array [j-1];
array [j-1]=trash;
f=1;
}
}
}
}
//
void Out(int col)
{
for (int i=1; i<=col; i++)
cout << array [i] <<" ";
cout << endl;
}
//
int main()
{
int col_el;
//
cout << " Enter length of array"<< endl;
cin >> col_el;
cout << " Enter array elements"<<endl;
for (int n=1; n<=col_el; n++)
{
cout <<n<<":" << "\t";
cin >> array[n];
}
//
Sort(col_el);
//
cout << "Result is:"<<endl;
Out(col_el);
cin >> col_el;
return 0;
}
void swap(int* x, int i, int j) {
int tmp;
tmp = x[i]; x[i] = x[j]; x[j] = tmp;
}
void ShakerSort(int* x) {
int last = n-1;
int left = 1, right = n-1;
/*
*/
do {
/* */
for (int j = right; j > 0; j--) {
if (x[j-1] > x[j]) {
swap(x, j-1, j);
last = j;
}
}
/*
*/
left = last + 1;
/* */
for (int j = 1; j <= right; j++) {
if (x[j-1] > x[j]) {
swap(x, j-1, j);
last = j;
}
}
/*
*/
right = last - 1;
} while (left < right);
}
#include"stdafx.h"
#include<conio.h>
#include<stdio.h>
void Out (int col_el);
void ShakerSort(int* x, int n);
void swap(int*, int, int);
int x[100];
int main()
{
int n;
//
puts(" Enter length of array");
scanf("%d", &n);
puts("input array:");
for (int i=1; i<=n; i++)
{
scanf("%d", &x[i]);
}
//
ShakerSort(x, n);
//
puts("rezult is:");
Out(n);
}
void swap(int* x, int i, int j)
{
int tmp;
tmp = x[i];
x[i] = x[j];
x[j] = tmp;
}
void ShakerSort(int* x, int n) {
int last = n-1;
int left = 1, right = n-1;
/*
*/
do {
/* */
for (int j = right; j > 0; j--) {
if (x[j-1] > x[j]) {
swap(x, j-1, j);
last = j;
}
}
/*
*/
left = last + 1;
/* */
for (int j = 1; j <= right; j++) {
if (x[j-1] > x[j]) {
swap(x, j-1, j);
last = j;
}
}
/*
*/
right = last - 1;
} while (left < right);
}
void Out(int n)
{
for (int i=1; i<=n; i++)
printf("%d ", x[i]);
getch();
}
#include "stdafx.h"
#include <conio.h>
#include <iostream>
int menu(void);
void sort_shel(int *, int);
void ShakerSort(int*, int);
void BubbleSort(int *, int);
void MinSort(int *,int);
void HoorSort(int *x,int n,int l,int r);
int x[100], i;
int main()
{
int n,l, r;
while(1)
{
switch (menu())
{
case 1: sort_shel(x,n); break;
case 2: BubbleSort(x,n); break;
|
|
|
case 3: puts("Vvedite dliny massiva:");
scanf("%d", &n);
for(int i=0;i<n; i++)
{
scanf("%d", &x[i]);
}
printf("Ishodnyi massiv:\n");
for(int i=0;i<n; i++)
{
printf("%d ", x[i]);
}
HoorSort(x,n,0,n-1);
break;
case 4: MinSort(x,n); break;
case 5: ShakerSort(x,n); break;
case 7:return 0;
default:printf("Neverniy vibor\n");
}
}
getch();
}
int menu()
{
int choice;
do
{
printf("\nMenu:\n");
printf("1.Metod Shela\n");
printf("2.Sortirovka puzyr'kom\n");
printf("3.Metod Hoara\n");
printf("4.Sortirovka vyborom naimen'shego elementa\n");
printf("5.Zadanije\n");
printf("7.end\n");
printf("Vash vibor?\n");
scanf("%d", &choice);
system("cls");
}
while (choice > 7);
return choice;
}
void sort_shel(int *x, int n)
{
int i, j; //
int buffer; //
int gap; //
int sorted;
puts("Vvedite dliny massiva:");
scanf("%d", &n);
for(int i=0;i<n; i++)
{
scanf("%d", &x[i]);
}
printf("Ishodnyi massiv:\n");
for(int i=0;i<n; i++)
{
printf("%d ", x[i]);
}
printf("\n");//
for(gap = n/2; gap > 0; gap /= 2) //
do
{
sorted = 0;
for(i = 0, j = gap; j < n; i++, j++)
if(*(x+i) > *(x+j)) // gap
{ //
buffer = *(x+j);
*(x+j) = *(x+i);
*(x+i) = buffer;
sorted = 1; // ,
}
}
while (sorted); //
puts("Massiv, otsortirovannyi metodom Shella:");
for(i=0; i<n; i++)
{
printf("%d ", x[i]);
}
}
void HoorSort(int *x,int n,int l,int r)
{
int srednii=x[(l+r)/2];
int i=l;
int j=r, t;
do
{ while(x[i]<srednii)
i++;
while(x[j]>srednii)
j--;
if(i<=j)
{
t=x[i];
x[i]=x[j];
x[j]=t;
i++;
j--;
}
}
while(i<=j);
if(i<r)
HoorSort(x,n,i,r);
if(j>l)
HoorSort(x,n,l,j);
}
void ShakerSort(int* x, int n)
{
int last = n-1, t;
int left = 1, right = n-1;
puts("Vvedite dliny massiva:");
scanf("%d", &n);
for(int i=0;i<n; i++)
{
scanf("%d", &x[i]);
}
printf("Ishodnyi massiv:\n");
for(int i=0;i<n; i++)
{
printf("%d ", x[i]);
}
do {
/* */
for (int j = right; j > 0; j--) {
if (*(x+j-1) > *(x+j))
{
t=*(x+j);
*(x+j)=*(x+j-1);
*(x+j-1)=t;
last = j;
}
}
/*
*/
left = last + 1;
/* */
for (int j = 1; j <= right; j++) {
if (*(x+j-1) > *(x+j)) {
t=*(x+j);
*(x+j)=*(x+j-1);
*(x+j-1)=t;
last = j;
}
}
/*
*/
right = last - 1;
} while (left < right);
for(i=0; i<=last; i++)
{
printf("%d ", x[i]);
}
}
void BubbleSort(int *x,int n)
{
int i, j, t;
puts("Vvedite dliny massiva:");
scanf("%d", &n);
for(int i=0;i<n; i++)
{
scanf("%d", &x[i]);
}
printf("Ishodnyi massiv:\n");
for(int i=0;i<n; i++)
{
printf("%d ", x[i]);
}
printf("\n");
for (i=0; i<n; i++)
for (j=n-1; j>i; j--)
if (*(x+j-1)>*(x+j))
{
t=*(x+j);
*(x+j)=*(x+j-1);
*(x+j-1)=t;
}
for(i=0; i<n; i++)
{
printf("%d ", x[i]);
}
}
void MinSort(int *x,int n)
{
int i,j,min, t;
puts("Vvedite dliny massiva:");
scanf("%d", &n);
for(int i=0;i<n; i++)
{
scanf("%d", &x[i]);
}
printf("Ishodnyi massiv:\n");
for(int i=0;i<n; i++)
{
printf("%d ", x[i]);
}
printf("\n");
for(i=0;i<n-1;i++)
{
min=x[i];
for(j=i+1;j<n;j++)
if(x[j]<min)
{
min=x[j];
t=x[j];
x[j]=x[i];
x[i]=t;
}
}
for(i=0; i<n; i++)
{
printf("%d ", x[i]);
}
}
