Модифицировать алгоритм быстрой сортировки - 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 );
            }
}

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

10   голосов , оценка 4.1 из 5