Консультации Портала - Консультация #190243

Задать вопрос Консультации Пользователи Форум

Задать вопрос экспертам

Консультация № 190243

07.12.2016, 10:40

0.00 руб.

0 2 1

Компьютеры Программирование

Здравствуйте! У меня возникли трудности с быстрой сортировкой.
Не совсем понимаю, что возвращает функция разделения. Индекс опорного элемента, который является медианой массива?
Медиана это когда среднеарифметическое слева от нее [медианы] меньше этого элемента, а справа - больше? Или среднеарифметические сравниваются не с элементом, а друг с другом?

Код:

int partHoare (int a[], int p, int r) {
    int x=a[p],i=p-1,j=r;
    while (1)
    {
        do  j--; while (a[j] > x);
        do  i++; while (a[i] < x);
        if  (i < j)   // надо ли после этого ещё сравнивать a[i]>a[j]?
            swap(&a[i], &a[j]);
        else 
            return j+1;
    }
}
void QuickSort (int a[], int start, int end) {
    int q;
    if (end-start<2) return;
    q = partHoare (a, start, end);
    QuickSort (a, start, q);
    QuickSort (a, q, end);
}

Обсуждение

давно

Лысков Игорь Витальевич

Посетитель
7438
7205

07.12.2016, 14:29

общий

это ответ

Здравствуйте, АнтонНР!
Во-первых, была ошибка в разбиении массива (ф-я partHoare). Должно быть:

Код:


       while (a[j] > x) j--;
       while (a[i] < x) i++;

Во-вторых, да, функция разделения возвращает индекс, относительно которого массив разбивается на две части,
в первой из которых сосредоточены меньшие значения, а во второй – большие.
Другими словами, "индекс опорного элемента, который является медианой массива"
Медиана - это элемент, разделяющий массив на меньшие (слева) и большие (справа) значения.
Откуда Вы взяли термин "среднеарифметическое"?

Код:

void swap(int* i1, int* i2)
{
	*i1 ^= *i2;
	*i2 ^= *i1;
	*i1 ^= *i2;
}

int partHoare (int a[], int p, int r) {
    int x=a[p],i=p-1,j=r;
    while (1)
    {
        while (a[j] > x) j--;
        while (a[i] < x) i++;
        if  (i < j)
            swap(&a[i], &a[j]);
        else 
            return j+1;
    }
}
void QuickSort (int a[], int start, int end) {
    int q;
    if (end-start<2) return;
    q = partHoare (a, start, end);
    QuickSort (a, start, q);
    QuickSort (a, q, end);
}

int main(int argc, char* argv[])
{
	int	a[8] = {9,6,3,4,10,8,2,7} ;

	QuickSort(a, 0, 7) ;

	return 0;
}

Об авторе:
"Если вы заметили, что вы на стороне большинства, —
это верный признак того, что пора меняться." Марк Твен

давно

АнтонНР

Посетитель
400592
10

08.12.2016, 01:52

общий

Адресаты:

С while'ми понял, спасибо.

В старом конспекте у меня была запись "Опорный элемент: стоящий посередине или случайный, лучше, если медиана (среднеарифм)", но сейчас я как-то и запутался в ней

Форма ответа

Отправка постов/ответов доступна только зарегистрированным и подтвержденным пользователям.

Если Вы уже зарегистрированы на Портале - войдите в систему, если Вы еще не регистрировались - пройдите простую процедуру регистрации.