24.09.2017, 07:48 [+3 UTC]
в нашей команде: 2 128 чел. | участники онлайн: 4 (рекорд: 21)

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

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

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

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

:: правила

:: новости

:: участники

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

:: форум

:: блоги

:: поиск

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

:: наш журнал

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

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

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

:: поддержка

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

Версия системы:
7.41 (25.02.2017)

Общие новости:
23.02.2017, 09:51

Форум:
23.09.2017, 18:51

Последний вопрос:
23.09.2017, 14:31

Последний ответ:
23.09.2017, 08:43

Последняя рассылка:
23.09.2017, 22:45

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

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

Наша кнопка:

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

Отзывы о нас:
19.03.2010, 09:03 »
Delph
Вроде всё просто... но не зря же всё гениальное считают простым. Если ответите на уточняющий вопрос в минифоруме, получите оплату. [вопрос № 177328, ответ № 260218]
28.09.2009, 18:03 »
AkaProc
Огромное спасибо! В Mozilla Firefox все отлично показывает! [вопрос № 172676, ответ № 254800]
17.12.2009, 16:52 »
Николай // Programmator
Выбрал ON, все работает. Спасибо Вам! [вопрос № 175355, ответ № 257846]

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

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

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

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

Лысков Игорь Витальевич
Статус: Старший модератор
Рейтинг: 239
solowey
Статус: 6-й класс
Рейтинг: 82
Хватов Сергей
Статус: Академик
Рейтинг: 71

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

Консультация онлайн # 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.13567 сек.

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