почему в 71 строке применяется функция swap? можешь пошагово пояснить алгоритм…
- User
почему в 71 строке применяется функция swap? можешь пошагово пояснить алгоритм сортировки? #include <stdio.h> #define NMAX 10
int input(int *n, int *a); int quick_sort(int *l, int *r, int *a); int heap_sort(int *n, int *a); void output(int *n, int *a); void swap_values(int *l, int *r); int split();
int main() { int n, data[NMAX];
if (input(&n, data) != 1) { quick_sort(data, &n, data); output(&n, data); heap_sort(&n, data); output(&n, data); } else printf("n/a"); return 0;}
int input(int *n, int *a) { char extra; int res = 1;
if ((scanf("%d%c", n, &extra) == 2) && (extra == '\n') && (0 < *n <= NMAX)) { for (int* p = a; p - a < *n; p++) { if (scanf("%d", p) != 1) { break; } // if (p - a < *n - 1) { // } else if (scanf("%d%c", p, &extra) == 2 && (extra == '\n')) { // res = 0; // } } res = 0; } return res;}
int quick_sort(int *start_i, int *end_i, int *a) { // сортировка массива и его частей if (*start_i > *end_i) { // начальный эл-т больше конечного? int index = split(start_i, end_i, a); // узнать индекс ???????эл-та, от которого разделить на левуюи прав части, (попутно поменяв соседние эл-ты местами)
quickSort(a, start_i, index - 1); // quickSort(a, index + 1, end_i); // }}
int split( int start_i, int end_i, int* a) { int point_i = start_i; // индекс, от которого отсчет++ цикла int pivot_val = a[end_i]; // с чем сравниваются элементы с индекмо объявленном выше for (int* i = start_i; i <= end_i; i++) { // индексы начала и конца остаются неищменными, их значения меняются местами по возрастсанию if (*i > pivot_val) { // пивот - значение послежнего элемента, "опорное" в сравнении с другими эл-тами swap(start_i, end_i); point_i++; // тот индекс, который понадобится в рекурсии } } swap(&a[end_i], &a[point_i]); // адреса передаютс,
return point_i;}
void swap_values(int *l, int *r) { int temp_val = *l; *l = *r; *r = temp_val; }
int heap_sort(int *n, int *a) {
}
void output(int *n, int *a) {
- Assistant
Ниже ‒ развёрнутый раз-бор того, что происходит в функции split(…) и зачем там вызывается swap (у вас она названа swap_values, а в теле split вы вызываете «swap» – это просто опечатка).
-
О чём вообще речь
Быстрая сортировка (Quick-sort) делит массив на две части относительно «опорного» (pivot) элемента:
• всё, что меньше pivot, переносится влево;
• всё, что не меньше pivot, идёт вправо.
После такого «разбиения» (partition) pivot оказывается на своём окончательном месте, а две получившиеся половинки сортируются рекурсивно тем же способом. -
Сигнатура split
(я сразу покажу более классический вариант: границы задаём НЕ значениями, а указателями/индексами)
// start_i – индекс (или указатель) первого элемента подмассива // end_i – индекс (или указатель) последнего элемента // a – сам массив int split(int start_i, int end_i, int *a) { int pivot_val = a[end_i]; // опорный элемент — берём последний int point_i = start_i; // граница «меньших» элементов- Цикл прохода по подмассиву
for (int i = start_i; i < end_i; i++) { if (a[i] < pivot_val) { // элемент должен уйти «влево» swap_values(&a[i], &a[point_i]); // <-- то самое действие point_i++; // сдвигаем границу } }Зачем здесь swap_values?
• a[i] содержит элемент, который оказался меньше pivot.
• point_i указывает на первую позицию, где ещё не стоит «маленький» элемент.
• Меняем их местами, тем самым отправляя «маленький» элемент в левую зону, а то, что в point_i было, перемещаем вправо (в непроверенную часть).
Именно так формируется инвариант:
[start_i .. point_i-1]— все < pivot,
[point_i .. i]— ещё не классифицированы.- Финальный обмен
swap_values(&a[point_i], &a[end_i]); // ставим pivot на своё место return point_i; // индекс, где теперь лежит pivot }Теперь в позиции point_i лежит pivot; всё левее pivot < него, всё правее ≥ него.
- Быстрая сортировка целиком
void quick_sort(int l, int r, int *a) { // l, r — индексы if (l < r) { int m = split(l, r, a); // 1. разбиение quick_sort(l, m-1, a); // 2. сортируем левую часть quick_sort(m+1, r, a); // 3. сортируем правую часть } }-
Что у вас надо поправить
• Условие в quick_sort написано какif (*start_i > *end_i)— нужноif (start_i < end_i)(сравниваем индексы, а не значения).
• В split параметры объявлены какint start_i/int end_i, но ниже вы используете их как указатели (int *i = start_i). Либо работаем с индексами, либо с указателями; не смешиваем.
• Имя функции обмена должно совпадать: либо вездеswap_values, либоswap.
• ВместоquickSortвызывайте свою же функциюquick_sort. -
Пошаговый пример (масcив 6 элементов)
Исходное: 7 2 9 4 3 6, pivot = 6
point_i = 0
i=0: 7<6? нет → ничего
i=1: 2<6? да → swap(2,7) → 2 7 9 4 3 6, point_i=1
i=2: 9<6? нет
i=3: 4<6? да → swap(4,7) → 2 4 9 7 3 6, point_i=2
i=4: 3<6? да → swap(3,9) → 2 4 3 7 9 6, point_i=3
Финальный swap с pivot: swap(7,6) → 2 4 3 6 9 7
pivot (6) на позиции 3 — слева 2 4 3 (<6), справа 9 7 (≥6).
Дальше рекурсивно сортируем 2 4 3 и 9 7.- Итог
Функция swap внутри split необходима для фактического переставления элементов, чтобы левый сегмент содержал только те значения, которые меньше опорного. Без обмена массив визуально не менялся бы, и алгоритм терял бы основной смысл.
Надеюсь, теперь понятно, почему в «71 строке» вызывается swap и как именно работает быстрая сортировка. Если нужно помочь привести код к полностью рабочему виду — дайте знать!
-
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.