Шейкерная сортировка одномерного массива - C (СИ)
Формулировка задачи:
Есть два массива. методом Шейкера отсортировать элементы первого массива, которых нет во втором. на языке Си.
пример:
3 5 7 8 2
3 7
результат после сортировки:
3 2 7 5 8
аааааа.....быстрее.....пожалуйста......осталось 20 минут!!!!!!!!! зачет или не зачет....срочно!!!!!
......заплачууу......20$ закинуу на киви или веб-мани
осталось 15 минут.....
Решение задачи: «Шейкерная сортировка одномерного массива»
textual
Листинг программы
#include <stdio.h> #include <stdlib.h> #include <time.h> int main(void) { const int size1 = 5; const int size2 = 2; int arr1[size1]; int arr2[size2]; srand(time(NULL)); for (int i = 0; i < size1; i++) arr1[i] = rand() % 100; for (int i = 0; i < size2; i++) arr2[i] = arr1[rand() % size1]; printf("a: "); for (int i = 0; i < size1; i++) printf ("%d ", arr1[i]); printf("\n"); printf("b: "); for (int i = 0; i < size2; i++) printf ("%d ", arr2[i]); printf("\n"); for (int left = 0, right = size1-1; left < right;) { for (int idx = left, l_idx = -1, r_idx = -1; idx <= right; idx++) { int i; for (i = 0; i < size2; i++) if (arr1[idx] == arr2[i]) break; if (i == size2) if (l_idx == -1) l_idx = idx; else r_idx = idx; if ( (l_idx != -1) && (r_idx != -1)) { if(arr1[r_idx] < arr1[l_idx]) { int tmp = arr1[l_idx]; arr1[l_idx] = arr1[r_idx]; arr1[r_idx] = tmp; idx = l_idx; } else { idx = r_idx; l_idx = r_idx; } r_idx = -1; } } right--; for (int idx = right, l_idx = -1, r_idx = -1; idx >= left; idx--) { int i; for (i = 0; i < size2; i++) if (arr1[idx] == arr2[i]) break; if (i == size2) if (r_idx == -1) r_idx = idx; else l_idx = idx; if ((l_idx != -1) && (r_idx != -1)) { if (arr1[l_idx] > arr1[r_idx]) { int tmp = arr1[l_idx]; arr1[l_idx] = arr1[r_idx]; arr1[r_idx] = tmp; idx = r_idx; } else { idx = l_idx; r_idx = l_idx; } l_idx = -1; } } left++; } printf("a: "); for (int i = 0; i < size1; i++) printf ("%d ", arr1[i]); printf("\n"); return 0; }
Объяснение кода листинга программы
Код реализует алгоритм Шейкерной сортировки для одномерного массива. Список действий:
- Инициализация переменных:
- объявление массивов arr1 и arr2;
- задание размера массивов size1 и size2;
- инициализация генератора случайных чисел srand(time(NULL));
- заполнение массива arr1 случайными числами от 0 до 99;
- заполнение массива arr2 элементами из arr1.
- Основной цикл сортировки:
- перебираем элементы массива arr1, начиная с первого и до предпоследнего;
- для каждого элемента:
- находим его пары в arr2, перебирая все элементы массива arr2;
- если пары нет, то элемент уже на своем месте;
- если пары есть, и пара находится правее текущего элемента, то меняем элементы местами;
- если пары есть, и пара находится левее текущего элемента, то меняем элементы местами и переворачиваем массив.
- Завершение сортировки:
- выводим отсортированный массив arr1.
Алгоритм называется
Шейкерная сортировка
, потому что онперетряхивает
массив, сравнивая пары соседних элементов.
- выводим отсортированный массив arr1.
Алгоритм называется
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д