Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 14.07.2010, 21:16
Новичок

Отправить личное сообщение для Stopafilm Посмотреть профиль Найти все сообщения от Stopafilm
 
Регистрация: 14.07.2010
Сообщений: 2

Вопросы насчёт быстрой сортировки
Здравствуйте. Объясните, пожалуйста. Есть алгоритм быстрой сортировки:
Код:
int shag=1;

void quickSort(int arr[], int left, int right, char v) {

            cout <<"--------" <<shag <<"-------" <<endl;

      if(v=='a') {cout <<"       Вариант №1"  <<endl; shag++;}
      else       {cout <<"        Вариант №2" <<endl; shag++;}
      cout <<"                                    left: " <<left <<endl;
      cout <<"                                    right: " <<right <<endl;

      int i = left, j = right;

      int tmp;

      int pivot = arr[(left + right) / 2];
      cout  <<endl <<"pivot: " <<pivot <<' ' <<endl;



      while (i <= j) {

            while (arr[i] < pivot)

                  i++;

            while (arr[j] > pivot)

                  j--;

            if (i <= j) {

                  tmp = arr[i];

                  arr[i] = arr[j];

                  arr[j] = tmp;

                  i++;

                  j--;
                 cout <<"               a[i]: "  <<arr[i] <<endl;
                 cout <<"               a[j]: "  <<arr[j] <<endl;
            }

      };

        cout <<"j: " <<j <<' ' <<endl;
        cout <<"i: " <<i <<' ' <<endl;




      if (left < j)

          quickSort(arr, left, j, 'a');


      if (i < right)

          quickSort(arr, i, right , 'b');

}


int main()
{
int z[]={1, 2, 3, 5, 7, 7, 12, 26, 14};
quickSort(z,0,8,'a');
}
В нём непонятно 2 вещи:
1)Почему срабатывает рекурсивно второй вариант (шаг 4), если значение i=1 (i<right);
2)Откуда значения: left: 3 и right: 4 (шаг 4).
P.S. Массив сортируется правильно.

Последний раз редактировалось Stopafilm, 31.07.2010 в 14:55.
  #2  
Старый 17.07.2010, 06:51
lord Kelvin

 
Сообщений: n/a

#include <stdio.h>
На третьем шаге у тебя прерывается одна из веток рекурсии - не срабатывает ни if( left < j ), ни if( i < right ).
Четвертый шаг это срабатывание условия i < right на втором шаге.
Код:
#include <stdio.h>
#include <conio.h>

void quickSort( int *arr, int left, int right, char v )
{
    static int step = 1;
    printf( "--------%d-------\r\n( case %d )", step++, 1 + ( v != 'a' ) );

    int i = left, j = right, pivot = arr[ ( left + right ) / 2 ];
    printf( "left: %d, right: %d, pivot: %d\r\n", left, right, pivot );

    while( i <= j )
    {
        while( arr[ i ] < pivot )
            i++;
        while( arr[ j ] > pivot )
            j--;

        if( i <= j )
        {
            int tmp = arr[ i ];
            arr[ i ] = arr[ j ], arr[ j ] = tmp;
            printf( "a[ i ]: %d, a[ j ]: %d, i: %d, j: %d\r\n", arr[ i ], arr[ j ], i, j );
            i++, j--;
        }
    }

    if( left < j )
        quickSort( arr, left, j, 'a' );

    if( i < right )
        quickSort( arr, i, right , 'b' );
}

int main()
{
    int z[] = { 1, 2, 3, 5, 7, 7, 12, 26, 14 };
    quickSort( z, 0, 8, 'a' );

    printf( "\r\nz[] = { %d", z[ 0 ] );
    for( int i = 0; i < sizeof( z ) / sizeof( *z ); i++ )
        printf( ", %d", z[ i ] );
    printf( " };\r\n" );
    _getch();
}
  #3  
Старый 17.07.2010, 11:14
Новичок

Отправить личное сообщение для Stopafilm Посмотреть профиль Найти все сообщения от Stopafilm
 
Регистрация: 14.07.2010
Сообщений: 2

Спасибо .

Последний раз редактировалось Stopafilm, 01.08.2010 в 21:11.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Общие вопросы по работе с массивами на Delphi CryVIC Ltd. Реализация, исходники, языки 20 11.01.2010 23:22
Сортировки гость Сортировка и поиск 2 28.11.2009 07:34
задача с быстрой сортировкой гость Сортировка и поиск 2 16.11.2008 21:09
как насчет Rss?.. Sapfeer Замечания о работе сайта 1 13.06.2007 14:18