Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
19 / 19 / 6
Регистрация: 10.01.2011
Сообщений: 241
1

Быстрая сортировка

31.08.2012, 21:25. Показов 820. Ответов 4
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Друзья, здравствуйте!
Как работает быстрая сортировка - у меня практически вопросов нет:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
const int n=10;
template <class T>
void QuickSort (T Ar[], long N)
{
    long i=0, j=N;
    T  temp, p;
    p=Ar[N/2];
    do
    {
        while(Ar[i]<p) i++;
        while (Ar[j]>p) j--;
        if(i<=j)
        {
            temp = Ar[i];
            Ar[i]=Ar[j];
            Ar[j]=temp;
            i++;
            j--;
        }
    }while(i<=j);
    if(j>0) QuickSort(Ar, j);
    if(N>i) QuickSort(Ar+i, N-i);
}
void main()
{
    srand((int)time(NULL));
    int Ar[n];
    for(int i=0; i<n; ++i)
    {
        Ar[i]=rand()%100;
        cout<<Ar[i]<<' ';
    }
    cout<<endl;
    QuickSort(Ar, n-1);
    for(int i=0; i<n; ++i)
    {
        cout<<Ar[i]<<' ';
    }
    cout<<endl;
    system("pause");
}
Не могу разобраться с рекурсией, а именно с этой строчкой if(N>i) QuickSort(Ar+i, N-i) - для чего к всему массиву (и как) прибавляется i ? И для чего от N отнимается i ?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
31.08.2012, 21:25
Ответы с готовыми решениями:

Быстрая сортировка (сортировка Хоара) для связных списков
есть у кого готовый алгоритм? или подскажите как реализовать

Быстрая сортировка(сортировка Хоара). Отсортировать фрагмент массива
Мне нужно отсортировать фрагмент массива, расположенный между первым и последним отрицательным...

Сортировка Слиянием vs Быстрая Сортировка - что лучше
Народ, помогите разобраться какой из методов сортировки лучше &quot;Сортировка Слиянием&quot; или &quot;Быстрая...

Быстрая сортировка (сортировка методом Хоара)
Ввести массив x1,x2,...,x20 в диапазоне . Требуется расположить отрицательные элементы в порядке...

4
Twilight Parasite
154 / 150 / 7
Регистрация: 21.07.2011
Сообщений: 908
31.08.2012, 21:30 2
OdessaNA, В Педивикию!
0
19 / 19 / 6
Регистрация: 10.01.2011
Сообщений: 241
31.08.2012, 22:05  [ТС] 3
Invader_Zim, ... а зачем вообще тогда нужен форум??? Ведь на все вопросы можно найти ответ в учебниках, справочниках, преподавателя и т.д..
0
Эксперт С++
4985 / 3092 / 456
Регистрация: 10.11.2010
Сообщений: 11,169
Записей в блоге: 10
31.08.2012, 22:16 4
Ar+i - сдвигает указатель массива, как бы отделяя определенный участок
N-i - задает размер этого участка, поскольку он обязательно будет меньше N, от него отнимается i.

Например: QuickSort( Ar + 1, N - 1 ) - сортируем все, что находится после первого элемента
1
Эксперт С++
1674 / 1046 / 174
Регистрация: 27.09.2009
Сообщений: 1,945
31.08.2012, 22:18 5
Массив передаётся в функцию в виде указателя на начало и длины. В процессе работы он делится на 2 части, к которым эта функция применяется рекурсивно. Если в первой половине i элементов, то её начало - Arr (очевидно, совпадает с началом целого массива), а длина i. Начало второй части Arr+i, её длина N-i (длина целого массива за вычетом длины первой части).
1
31.08.2012, 22:18
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
31.08.2012, 22:18
Помогаю со студенческими работами здесь

C/C++ FAQ :: Быстрая сортировка (сортировка Хоара)
Вопрос, скорее академический, по мотивам реализации. Вот в faq приведена реализация этого метода...

Сортировка Хоара / Быстрая сортировка
Доброго времени суток. Написал реализацию алгоритма быстрой сортировки. void SortHhoar(int...

Сортировка расчёской и быстрая сортировка
В файле in.txt записана последовательность целых чисел. Заданными методами отсортировать числа и...

Быстрая сортировка
Помогите, пожалуйста! Не понимаю почему, но при использовании быстрой сортировки программа выдаёт...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru