20.01.2017, 17:07 [+3 UTC]
в нашей команде: 1 762 чел. | участники онлайн: 6 (рекорд: 21)

:: РЕГИСТРАЦИЯ

:: консультации

:: задать вопрос

:: все разделы

:: правила

:: новости

:: участники

:: доска почёта

:: форум

:: блоги

:: поиск

:: статистика

:: наш журнал

:: наши встречи

:: наша галерея

:: отзывы о нас

:: поддержка

:: руководство

Версия системы:
7.40 (02.09.2016)

Общие новости:
31.12.2016, 18:43

Форум:
18.01.2017, 11:36

Последний вопрос:
20.01.2017, 14:11

Последний ответ:
20.01.2017, 16:54

Последняя рассылка:
20.01.2017, 16:15

Писем в очереди:
0

Мы в соцсетях:

Наша кнопка:

RFpro.ru - здесь вам помогут!

Отзывы о нас:
22.06.2011, 15:16 »
Ханинёв Пётр Валерьевич
Оптимальный вариант решения задачи. Подробные комментарии. [вопрос № 183693, ответ № 267810]
04.11.2011, 19:53 »
владимир
спасибо мастерам своего дела понятно и полезно

РАЗДЕЛ • С / С++

Создание программ на языках C и C++.

[администратор рассылки: Андрей Кузнецов aka Dr_Andrew (Старший модератор)]

Лучшие эксперты в этом разделе

Лысков Игорь Витальевич
Статус: Старший модератор
Рейтинг: 750
solowey
Статус: 5-й класс
Рейтинг: 220
Асмик Гаряка
Статус: Советник
Рейтинг: 182

Перейти к консультации №:
 

Консультация онлайн # 190243
Раздел: • С / С++
Автор вопроса: АнтонНР (Посетитель)
Отправлена: 07.12.2016, 10:40
Поступило ответов: 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);
}


Состояние: Консультация закрыта

Ответ # 274402 от Лысков Игорь Витальевич (Старший модератор)

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

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

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


Консультировал: Лысков Игорь Витальевич (Старший модератор)
Дата отправки: 07.12.2016, 14:29

Рейтинг ответа:

0

[подробно]

Сообщение
модераторам

Отправлять сообщения
модераторам могут
только участники портала.
ВОЙТИ НА ПОРТАЛ »
регистрация »

Мини-форум консультации № 190243
АнтонНР
Посетитель

ID: 400592

# 1

= общий = | 08.12.2016, 01:52 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер
Лысков Игорь Витальевич:

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

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

 

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

Яндекс Rambler's Top100

главная страница | поддержка | задать вопрос | интересные статьи

Время генерирования страницы: 0.14629 сек.

© 2001-2017, Портал RFPRO.RU, Россия
Авторское право: ООО "Мастер-Эксперт Про"
Калашников О.А.  |  Гладенюк А.Г.
Версия системы: 7.40 от 02.09.2016
Бесплатные консультации онлайн