VPF::[Алгоритм] Ошибка в сортировке

THandle

Дата 18.7.2008, 11:17 (ссылка)

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

Загрузка ...

Хранитель Клуба
Group Icon

Награды: 1

Профиль
Группа: Админ
Сообщений: 3639
Регистрация: 31.7.2007
Где: Moscow, Dubai

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

Привел код в относительно красивое состояние(вдруг кто-то захочет подебажить?):

Код


Procedure busort(var x : array of tip);
var  
  i, j, k, m, n : integer;
  w, v : tip;
  path : array [0..40] of integer;
begin
  n := high(x);
  for m := n div 2 downto 1 do
    begin
      i := 0;
      j := m;
      path[i] := j;
      inc(i);
      while 2 * j < n do
        begin 
          if x[2 * j + 1].key < x[2 * j].key then
            begin  
              j := j * 2; 
              path[i] := j; 
              inc(i) 
            end
          else 
            begin 
              j := j * 2 + 1;
              path[i] := j;
              inc(i)
            end;
        end;
      if 2 * j = n then
        begin    
          j := n;
          path[i] := j;
          inc(i)
        end;
      i := m;
      while (j>i) and (x[j].key < x[i].key) do
        j := j div 2;
      i := m; 
      v := x[path[0]]; 
      k := 0;
      while path[k] < j do 
        begin 
          x[path[k]] := x[path[k + 1]];
          inc(k)
        end;
      x[path[k]]:=v;
    end;
  for m := n downto 2 do
    begin
      w := x[1];
      x[1] := x[m];
      x[m] := w;
      if m <> 2 then
        begin 
          i := 0;
          j := 1;
          path[i] := j;
          inc(i);
          while 2 * j < m - 1 do
            begin 
              if x[2 * j + 1].key < x[2*j].key then
                begin 
                  j := j * 2;
                  path[i] := j;
                  inc(i)
                end
              else 
                begin 
                  j := j * 2 + 1;
                  path[i] := j;
                  inc(i) 
                end;
            end;
          if 2 * j = m - 1 then
            begin 
              j := m - 1;
              path[i] := j;
              inc(i)    
            end;
          i := 1;
          while (j>i) and (x[j].key<x[i].key) do 
            j := j div 2;
          i := 1;
          v := x[path[0]];
          k:=0;
          while path[k] < j do 
            begin 
              x[path[k]] := x[path[k+1]];
              inc(k)
            end;
          x[path[k]] := v;
        end;
    end;
end;

Сам постараюсь заняться этим кодом завтра. Сейчас просто день рождения праздную smile

Кстати, хотелось бы узнать - что это за типчик такой подозрительный в процедурку заходит?

Procedure busort(var x : array of tip);

???

lansel

Дата 18.7.2008, 19:15 (ссылка)

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

Загрузка ...

Новичок

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

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

Цитата(THandle @ 18.7.2008, 11:17)

Procedure busort(var x : array of tip);

Type tipkey=integer; tip=Record key:tipkey; end;
Var X:Array[1..n]of tip;

Palladin

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

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

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 932
Регистрация: 15.5.2007
Где: Беларусь г.Гомель

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

Неужели для задачи необходимо использовать именно этот код? да и именно этот способ сортировки?
P.S. Задачу в студию smile

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

Глуп тот кто полагается на истину авторитета, а не на авторитет истины
[color=red]KAV&KIS==Evil[/color]

lansel

Дата 19.7.2008, 09:25 (ссылка)

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

Загрузка ...

Новичок

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

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

Цитата(Palladin @ 19.7.2008, 02:47)

Какую такую задачу??

Да мне нужен именно этот код!!! smile

HoTMetaL

Дата 19.7.2008, 12:15 (ссылка)

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

Загрузка ...

Шустрый

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

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

Посмотрел я твой код и заодним привёл в порядок. Скажу тебе одну вещь - этот код был написан по алгоритму, в котором нумерация элементов входного массива начиналась с 1, а не с 0. Тебе никто не мешает начинать заполнение массива с первого, а не с нулевого элемента. Пусть он там себе в памяти болтается и никому не мешает.

И ещё, если вдруг кто-то захочет переписать эту программу под массив с нумерацией с нуля, пусть обратит внимание на изменение значений переменной j, т.к. именно она отвечает за индексы.

Код


#include <vcl.h>
#pragma hdrstop
#include "math.h"
#include <stdio.h>
#include <dos.h>
#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
const n=7;

struct zap{
       int key;
};
zap X[n];

//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
        : TForm(Owner)
{
}
//---------------------------------------------------------------------------
int busort (zap X[])
{
    int i,j,k,m,n1;

    int path[20];
    zap w,v;
    
    n1=n-1;
    for(m=n1/2;m>0;m--){
       i=0;
       j=m;
       path[i]=j;
       i++;
       while(2*j<n1){
            if(X[2*j+1].key<X[2*j].key){
              j=j*2;
              path[i]=j;
              i++;
            }else{
              j=j*2+1;
              path[i]=j;
              i++;
            }
       }

       if(2*j==n1){
         j=n1;
         path[i]=j;
         i++;
       }
       i=m;

       while((j>i)&& (X[j].key<X[i].key)){
             j=j/2;
       }

       i=m;
       v=X[path[0]];
       k=0;

       while(path[k]<j){
            X[path[k]]=X[path[k+1]];
            k++;
       }
       X[path[k]]=v;
    }

    for(m=n1;m>=2;m--){
       w=X[1];
       X[1]=X[m];
       X[m]=w;

       if(m!=2){
         i=0;
         j=1;
         path[i]=j;
         i++;

         while((2*j)<(m-1)){
              if(X[2*j+1].key < X[2*j].key){
                j=j*2;
                path[i]=j;
                i++;
              }else{
                j=j*2+1;
                path[i]=j;
                i++;
              }
         }
         if((2*j)==(m-1)){
           j=m-1;
           path[i]=j;
           i++;
         }

         i=1;

         while((j>i)&& (X[j].key<X[i].key)){
              j=j/2;
         }

         i=1;
         v=X[path[0]];
         k=0;

         while(path[k]<j){
              X[path[k]]=X[path[k+1]];
              k++;
         }
         X[path[k]]=v;
       }
    }
}
void __fastcall TForm1::Button1Click(TObject *Sender)
{
     int j,k,i;

     X[0].key=100;
     X[1].key=55;
     X[2].key=8;
     X[3].key=99;
     X[4].key=9;
     X[5].key=3;
     X[6].key=1;
     busort(X);

     for(k=0;k<n;k++)
        Form1->Memo1->Lines->Add(IntToStr(X[k].key)) ;

}

Добавлено через 5 минут и 15 секунд
А на Delphi ещё проще: пишешь

Код


X: array [1..N] of integer;

Это сообщение отредактировал(а) HoTMetaL - 19.7.2008, 12:18

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