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

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

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

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

31.08.2012, 21:25. Просмотров 544. Ответов 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++
Каждому элементу массива а соответствует значение массива b то есть a b 1-5 2-3 5-2 3-1 4-4 если сортировать массив b по...

Быстрая сортировка - C++
Здравствуйте уважаемые форумчане киберфорума. Имеется проблеммка с задачкой, могли бы вы помочь мне ее решить? Имеем двумерный...

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

Быстрая сортировка - C++
нормальный код? а то третий день парюсь, вроде сейчас получилось void quicksort (int *a, int start, int end) { int point = partition...

Быстрая сортировка - C++
Здорова господа! Есть задачка: дан алгоритм быстрой сортировки. ну вообщем я ее cделал но ток без указателей. А задачка находиться в...

Быстрая сортировка - C++
Есть три файла: Функция: #ifndef QUICK #define QUICK #include &lt;vector&gt; using namespace std; template&lt;class...

Быстрая сортировка - C++
Помоги мне ответить на вопросы,большая просьба,заранее спасибо Быстрая сортировка #include &lt;iostream&gt; using namespace std; ...

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

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

Быстрая сортировка - C++
void quickSortR(int *first,int *last) { // На входе - массив a, a - его последний элемент. int *i = first, *j = last; ...

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

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


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

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

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

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