VPF::Сортировка двоичной вставкой.

iDeus

Дата 3.12.2008, 13:10 (ссылка)

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

Загрузка ...

Deus vult

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

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

Доброго времени суток, уважаемые знатоки.

Необходима Ваша помощь в реализации метода сортировки.

При решении задачи:

Провести сравнительный анализ эффективности следующих методов сортировки:
1)    линейный выбор с обменом, челночная сортировка, двоичная вставка;
2)    сортировка Шелла, центрированная вставка;
3)    стандартный обмен, быстрая сортировка, линейная вставка.
Предлагаемый тест: сортировка целочисленного массива размера n, элементы которого - случайные величины, распределенные в интервале (0, N-1).

возникла проблема. Не получается найти более менее вменяемого объяснения принципов сортировки двоичной вставкой, и примеров реализации.

Первый сегмент, в котором необходимо так же реализовать метод двоичной вставки я решил так:

Код


/**/
_1: system("cls");
  reset(A,A_backup,n);    
  printf("Линейный выбор с обменом.\n-------------------\nИсходный массив:\n");
  show(A,n);
/**/ 
  j=0;
  index=-1;
  koof[0]=0;
  perest[0]=0;
  for(j=0;j!=n;j++)
    {
      min_=16000;
      for(int i=j;i<n;i++)
        {
          if(A[i]<min_)
            {
              min_=A[i];
              index=i;
            }
          koof[0]++;  
        }
      if(index!=-1)
        {  
          buf=A[j];
          A[j]=A[index];
          A[index]=buf; 
          perest[0]++;
        } 
    }
  printf("Отсортированный массив:\n");  
  show(A,n);
  printf("\nПроверок - %d  Перестановок - %d\n",koof[0],perest[0]);
/**/
  reset(A,A_backup,n);                    //восстановление массива
  printf("\nЧелночная сортировка.\n-------------------\nИсходный массив:\n");
  show(A,n);
/**/
  koof[1]=0;
  perest[1]=0;
  k=n-1;
  // границы неотсортированной части массива
  niz=1;
  verh=n-1; 
  do
    {                       
      for (j=niz;j<=verh;j++)
        {
          koof[1]++;
          if (A[j-1]>A[j])
            {
              swap(A,j-1,j);
              perest[1]++;
              k=j;                       
            }
        }
      verh=k-1;         
        for (j=verh;j>=niz;j--)
        {
          koof[1]++;
          if (A[j-1]>A[j])
            {
              swap(A,j-1,j);
              perest[1]++;
              k=j;
            }
        }
      niz=k+1;
    } while (niz<verh); // если низ и верх встретятся - сортировка закончена
  printf("Отсортированный массив:\n");   
  show(A,n);
  printf("\nПроверок - %d  Перестановок - %d\n",koof[1],perest[1]);
/**/
  reset(A,A_backup,n);                    //восстановление массива
  printf("\nДвоичная вставка.\n-------------------\nИсходный массив:\n");
  show(A,n);
/**/
  koof[2]=0;
  perest[2]=0;
  //
  //   двоичная вставка
  //   двоичная вставка
  //   двоичная вставка
  //   двоичная вставка
  //
  //
  printf("Отсортированный массив:\n");   
  show(A,n);
  printf("\nПроверок - %d  Перестановок - %d\n",koof[2],perest[2]);
  getch();
  goto end;
/**/

Пользовался ли кто-нибудь этим способом сортировки? Каков его принцип? Ну и было бы просто замечательно взглянуть на пример реализации.

Заранее большое спасибо за помощь.

Inlight

Дата 3.12.2008, 14:00 (ссылка)

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

Загрузка ...

Новичок

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

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

Посмотри эти исходники: Сортировка двоичными вставками и Бинарные вставки
А сортировки я смотрю обычно здесь - Методы сортитировок или у Седжвика в "Фундаментальные алгоритмы на С++"

Это сообщение отредактировал(а) Inlight - 3.12.2008, 14:09

iDeus

Дата 4.12.2008, 03:20 (ссылка)

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

Загрузка ...

Deus vult

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

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

Inlight, разобрался, спасибо за помощь.

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