Модифицировать алгоритм быстрой сортировки - C (СИ)
Формулировка задачи:
Сбивает с толку само условие: Дано масив A[n]. Модифицировать алгоритм быстрой сортировки для нахождения элемента с n/2 за величиной значением,
/*внимание*/
не упорядочивая массив. То есть, если есть массив: {7, 11, 3, 5, -8, 2}, в результате я должен получить либо 3 (если от минимального), либо 5 (если от максимального). Как понимаю, массив должен быть отсортирован лишь частично, а далее туплю Вот стандартный код...void quicksort(int* a, int first, int last) { int i = first, j = last, x = a[(first + last) / 2]; do { while (a[i] < x) i++; while (a[j] > x) j--; if(i <= j) { if (i < j){ int dod; dod=a[i]; a[i]=a[j]; a[j]=dod; } i++; j--; } } while (i <= j); if (i < last) quicksort(a, i, last); if (first < j) quicksort(a, first,j); }
Решение задачи: «Модифицировать алгоритм быстрой сортировки»
textual
Листинг программы
#include <stdio.h> #include <conio.h> #include <windows.h> #define KOLVO 9 int kilk_el (int mas1[]); int quicksort (int* , int, int, int); int kilk_ob_rec, kilk_por_rec; int main() { SetConsoleCP(1251); SetConsoleOutputCP(1251); int q1[100]; printf("Arr:\n"); int size = 0; size = kilk_el(q1); fflush(stdin); //system("cls"); int el; el = quicksort(q1, 0, size - 1, (size - 1) / 2); printf("\n\n"); printf ("%d",el); getch(); } int kilk_el(int mas1[]){ int * p1 = mas1; int i=0; int K=0; while(i<KOLVO){ if (scanf("%d",(p1 + i))==0) break; else mas1[K++]=mas1[i]; i++; } return i; } int quicksort(int* a, int first, int last, int mediana){ int smth = (first + last) / 2; int i = first, j = last, x = a[smth]; do { while (a[i] < x) i++; while (a[j] > x) j--; //smth = j; if(i <= j) { if (i < j){ int dod; dod=a[i]; a[i]=a[j]; a[j]=dod; if (a[j] == x) // сохраняю индекс начального элемента если он берет участие в обмене местами smth = j; else if (a[i] == x) smth = i; } i++; j--; } } while (i <= j); if (mediana == smth) return x; else if (mediana < smth){ if (smth % 2 == 0) /* если честно, не знаю зачем делаю проверку тут и далее на smth % 2, но зависимо от количества элементов массива границы будут или не будут включать поставленные элемент (на бумажке тестил) */ quicksort(a, first, smth , mediana); else quicksort(a, first - 1, smth , mediana); } else if (mediana > smth){ if (smth % 2 == 0) quicksort(a, smth, last, mediana ); else quicksort(a, smth + 1, last, mediana ); } }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д