VPF::Проблемы с быстрой сортировкой

6atoh

Дата 17.9.2006, 18:24 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 160
Регистрация: 15.9.2006
Где: Minsk

Репутация: нет
Всего: 4

Взял алгоритм быстрой сортировки с http://algolist.manual.ru/sort/quick_sort.php
Вот он собственно:

Код


template<class T>
void quickSortR(T* a, long N) {
// На входе - массив a[], a[N] - его последний элемент.

  long i = 0, j = N; // поставить указатели на исходные места
  T temp, p;

  p = a[ N>>1 ];// центральный элемент

  // процедура разделения
  do {
    while ( a[i] < p ) i++;
    while ( a[j] > p ) j--;

    if (i <= j) {
      temp = a[i]; a[i] = a[j]; a[j] = temp;
      i++; j--;
    }
  } while ( i<=j );


  // рекурсивные вызовы, если есть, что сортировать 
  if ( j > 0 ) quickSortR(a, j);
  if ( N > i ) quickSortR(a+i, N-i);
}

Так вот меня смущает строка:
if( N > i ) quickSortR(a+i, N-i);
что значит a+i, если a в моем случае - массив byte[]???

CaptainFlint

Дата 17.9.2006, 18:32 (ссылка)

(нет голосов)

Загрузка ...

Искатель сокровищ

Профиль
Группа: Участник
Сообщений: 393
Регистрация: 26.2.2003
Где: Москва

Репутация: нет
Всего: 23

Цитата(6atoh @ 17.9.2006, 19:24

)

что значит a+i, если a в моем случае - массив byte[]???

Имя массива является указателем на его начало. Т.е. литерал a является переменной, содержащей адрес ячейки a[0]. Соответственно, прибавляя к указателю число i, ты смещаешь этот указатель на i элементов, т.е. a+i будет являться указателем на ячейку a[i]

--------------------

Почему же, ё-моё, ты нигде не пишешь "ё"?
--------------------
Для тех, кто не знает: CaptainFlint - это бывший Константин. ;)

Kuvaldis

Дата 17.9.2006, 18:35 (ссылка)

(нет голосов)

Загрузка ...

механик-вредитель

Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

Репутация: 11
Всего: 61

6atoh,
В С/С++ имя массива - это указатель на первый элемент(его адрес)
Если мы к указателю прибавляем число i, то компилятор РЕАЛЬНО указывает на i-тый элемент массива независимо от его типа. Происходит это так: i * sizeof(тип_элементов_массива)

Т.е. a + i - это указатель (см. выше - имя массива)

P.S.
CaptainFlint - редиска, опередил меня smile

Это сообщение отредактировал(а) Kuvaldis - 17.9.2006, 18:37

--------------------

Помни - когда ты спишь, враг не дремлет
Спи чаще и дольше, изматывай врага бессоницей

maxim1000

Дата 17.9.2006, 21:28 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 17
Всего: 110

всё-таки, вопрос больше по C/C++, чем по алгоритму
так что туда и переношу...

--------------------

qqq

6atoh

Дата 18.9.2006, 02:02 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 160
Регистрация: 15.9.2006
Где: Minsk

Репутация: нет
Всего: 4

всем спасибо....видимо придется создавать похожую тему в .NET, т.к. именно там у меня возникла проблема

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »