Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
OdessaNA
19 / 19 / 0
Регистрация: 10.01.2011
Сообщений: 241
#1

Быстрая сортировка - C++

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

Друзья, здравствуйте!
Как работает быстрая сортировка - у меня практически вопросов нет:
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
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
31.08.2012, 21:25
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Быстрая сортировка (C++):

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

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

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

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

Сортировка Хоара / Быстрая сортировка - C++
Доброго времени суток. Написал реализацию алгоритма быстрой сортировки. void SortHhoar(int *arr,int f,int l)//Хоара { int mid = (f...

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

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

Например: QuickSort( Ar + 1, N - 1 ) - сортируем все, что находится после первого элемента
1
Nick Alte
Эксперт С++
1638 / 1010 / 119
Регистрация: 27.09.2009
Сообщений: 1,945
Завершенные тесты: 1
31.08.2012, 22:18 #5
Массив передаётся в функцию в виде указателя на начало и длины. В процессе работы он делится на 2 части, к которым эта функция применяется рекурсивно. Если в первой половине i элементов, то её начало - Arr (очевидно, совпадает с началом целого массива), а длина i. Начало второй части Arr+i, её длина N-i (длина целого массива за вычетом длины первой части).
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.08.2012, 22:18
Привет! Вот еще темы с ответами:

Быстрая сортировка - C++
Читал о быстрой сортировки смысл понятен но не могу понять некоторые моменты. Каким образом работают два последних условия? Они работают...

Быстрая сортировка - C++
Помогите пожалуйста, при использовании алгоритма быстрой сортировки, конечный массив получается не отсортированным, хотя все операции...

Быстрая сортировка - C++
Задача: пользователь задает количество элементов массива (макс. - 500 000), вводит их, затем задает количество запросов (макс. - 10000) и...

Быстрая сортировка - C++
Дошёл до темы быстрой сортировки, набрал код, начал компилировать. Что-то странно, всё написано правильно, уже проверял, 8 раз, программа...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
31.08.2012, 22:18
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru