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

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

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

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

31.08.2012, 21:25. Просмотров 500. Ответов 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 ?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
31.08.2012, 21:25     Быстрая сортировка
Посмотрите здесь:

Быстрая сортировка C++
Быстрая сортировка C++
C/C++ FAQ :: Быстрая сортировка (сортировка Хоара) C++
Быстрая сортировка(сортировка Хоара). Отсортировать фрагмент массива C++
C++ Быстрая сортировка
Быстрая сортировка C++
C++ Быстрая сортировка
Быстрая сортировка (сортировка Хоара) для связных списков C++
C++ Быстрая сортировка
Быстрая сортировка (сортировка методом Хоара) C++
C++ Сортировка Хоара / Быстрая сортировка
C++ Сортировка расчёской и быстрая сортировка

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

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

Например: QuickSort( Ar + 1, N - 1 ) - сортируем все, что находится после первого элемента
Nick Alte
Эксперт С++
1599 / 991 / 117
Регистрация: 27.09.2009
Сообщений: 1,910
Завершенные тесты: 1
31.08.2012, 22:18     Быстрая сортировка #5
Массив передаётся в функцию в виде указателя на начало и длины. В процессе работы он делится на 2 части, к которым эта функция применяется рекурсивно. Если в первой половине i элементов, то её начало - Arr (очевидно, совпадает с началом целого массива), а длина i. Начало второй части Arr+i, её длина N-i (длина целого массива за вычетом длины первой части).
Yandex
Объявления
31.08.2012, 22:18     Быстрая сортировка
Ответ Создать тему
Опции темы

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