VPF::[C] Сортировка Фон-Неймана - Форум программистов

tux32

Дата 18.11.2007, 05:07 (ссылка)

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

Загрузка ...

Новичок

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

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

Помогите пожалуйста реализовать на Си алгоритм сортировки Фон-Неймана. Требуется отсортировать неупорядоченный целочисленный массив smile

Puoar

Дата 18.11.2007, 07:14 (ссылка)

(голосов:2)

Загрузка ...

Новичок

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

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

Код


#include<iostream.h>


/**
* слияние упорядоченных частей массива в буфер temp
* a     -- сортируемый массив
* lb    -- левая граница
* split -- индекс, по которому делится массив
* rb    -- правая граница
**/
void merge( int *a, int lb, int split, int rb )
 {

  int pos1, pos2, pos3, *temp;  

  pos1 = lb;
  pos2 = split+1;
  pos3 = 0;

  temp = new int[ (rb-lb)+1 ];

  while( pos1 <= split && pos2 <= rb )
   {
   if( a[ pos1 ] < a[ pos2 ] )
    {
    temp[pos3++] = a[pos1++];
    }
   else
    {
    temp[ pos3++ ] = a[ pos2++ ];
    }
   }
 
  while( pos2 <= rb )
   {
   temp[ pos3++ ] = a[ pos2++ ];
   }

  while( pos1 <= split )
   {
   temp[ pos3++ ] = a[ pos1++ ];
   }

  for( pos3 = 0; pos3 < rb-lb+1; pos3++ )
   {
   a[lb+pos3] = temp[pos3];
   }

  delete [] temp;
}


void mergeSort( int *a, int lb, int rb )
 { 
  int split;
  if( lb < rb )                     // если есть более 1 элемента происходит деление
   { 
   split = (lb + rb)/2;             // делим массив
   mergeSort( a, lb, split );       // сортировать левую половину 
   mergeSort( a, split+1, rb );     // сортировать правую половину 
   merge( a, lb, split, rb );       // слить результаты в общий массив
   }
 }


int main()
{
int mass[]={ 1, -20, 8, 9, 0, 2, 7, 3, 10 };

mergeSort( mass, 0, 9 );

for( int i=0; i<9; i++ )
 {
 cout << mass[ i ] << " ";
 }


return 0;
}

tux32

Дата 18.11.2007, 14:53 (ссылка)

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

Загрузка ...

Новичок

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

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

Puoar, спасибо огромный smile

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