Сортировка векторов методами: пузырька, Хоара, Шейкерная сортировка - C (СИ)
Формулировка задачи:
Сортировка векторов методами: пузырька, Хоараб, Шейкерная сортировка
Каждый отдельный алгоритм должен быть оформлен в виде функции, обращение к которым осуществляется из функции main()
Я сделала функции для пузырька и шейкерной сортировок, а вот сортировку Хоара не могу, помогите пожалуйста
#include <stdio.h>
#include <conio.h>
#include <math.h>
#include <time.h>
void vorm_vector(int nn, int vect_max, int vect_min, int vect[nn]);
void bubble_sort (int nn, int vector[nn]);
void sheiker_sort(int nn, int vector[nn]);
int main()
{
int i, vector_min, vector_max, n ;
printf("\n**** please enter ****");
printf("\n");
printf("\n min=");
scanf("%d", &vector_min);
printf("\n max=");
scanf("%d", &vector_max);
printf("\n n=");
scanf("%d", &n);
printf("\n");
int vector[n];
vorm_vector(n, vector_max, vector_min, vector);
printf("\nOriginal vector:\n");
for(i = 0; i < n; i++)
printf(" %4d", vector[i]);
printf("\n");
bubble_sort (n, vector);
printf("\nBubble sort:\n");
for(i = 0; i<n; i++)
printf(" %4d", vector[i]);
printf("\n");
sheiker_sort (n, vector);
printf("\nSheiker sort:\n");
for(i = 0; i<n; i++)
printf(" %4d", vector[i]);
printf("\n");
return 0;
}
void vorm_vector(int nn, int vect_max, int vect_min, int vect[nn])
{
int i, m;
time_t t; // текущее время для инициализации
// генератора случайных чисел
srand((unsigned) time(&t)); // инициализация генератора
// случайных чисел
m = vect_max-vect_min + 1;
// получение случайного числа в диапазоне
// от vector_min до vector_max
for (i=0; i<nn; i++)
vect[i]=rand()% m + vect_min;
}
// 2. Сортировка пузырьком
void bubble_sort(int nn, int vect[nn])
{
int i, m, temp;
for (m=nn-2; m>=0 ;m--)
for (i=0; i<=m ;i++)
if (vect[i] > vect[i+1])
{
temp = vect[i];
vect[i] = vect[i+1];
vect[i+1]= temp;
}
}
// 3. Шейкерная сортировка
void sheiker_sort(int nn, int vect[nn])
{
int l, r, i, k, temp;
k = l = 0;
r = nn - 2;
while(l <= r)
{
for(i = l; i <= r; i++)
if (vect[i] > vect[i+1])
{
temp = vect[i];
vect[i] = vect[i+1];
vect[i+1] = temp;
k = i;
}
r = k - 1;
for(i = r; i >= l; i--)
if (vect[i] > vect[i+1])
{
temp = vect[i];
vect[i] = vect[i+1];
vect[i+1] = temp;
k = i;
}
l = k + 1;
}
}
[size="1"][color="grey"][I]Добавлено через 3 минуты[/I][/color][/size]
Это сортировка Хоара
#include <stdio.h>
#include <math.h>
#include <conio.h>
#include <locale.h>
#define N 256
int a[N];
void qsort(int l, int r)
{
int w,x,i,j;
i=l;
j=r;
x=a[(l+r)/2];
while (i<=j)
{
while (a[i]<x) i++;
while (x<a[j]) j--;
if (i<=j)
{
w=a[i]; a[i]=a[j]; a[j]=w;
i++; j--;
}
}
if (l<j) qsort(l,j);
if (i<r) qsort(i,r);
}
void main()
{
int i,n;
srand((unsigned) time(NULL));
printf("Enter N: "); scanf("%d", &n);
for (i=0; i<n; i++)
{
a[i]=1+rand()%n;
printf("%d ", a[i]);
}
printf("\n");
qsort(0,n-1);
for (i=0; i<n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}Решение задачи: «Сортировка векторов методами: пузырька, Хоара, Шейкерная сортировка»
textual
Листинг программы
#include <stdio.h>
#define N 10
int a[N] = {5,2,6,0,11,7,6,7,4,2};
int sort(int *a, int last)
{
int t=0;
for (int i=0; i<last; i++)
{
if (a[i] > a[last])
{
t=a[i];
a[i] = a[last];
a[last] = t;
}
}
if (last > 1)
{
last--;
sort(a,last);
}
else return 0;
}
int main()
{
sort(a,N-1);
for (int i=0; i<N; i++) printf ("%d ",a[i]);
return 0;
}
Объяснение кода листинга программы
- Подключение стандартной библиотеки для работы с консолью (stdio.h).
- Определение массива a с фиксированным размером N = 10 и инициализация его значениями.
- Объявление функции sort, которая принимает указатель на массив и индекс последнего элемента для сортировки.
- Передача в функцию sort указателя на массив a и значение N-1 (так как последний элемент не нужно сортировать).
- Вывод отсортированного массива в консоль.
- Возврат 0 функцией main, что означает корректное завершение работы программы.