• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Iteracyjne sortowanie przez scalanie

Object Storage Arubacloud
0 głosów
317 wizyt
pytanie zadane 8 lutego 2017 w Inne języki przez Mariusz M Obywatel (1,670 p.)
edycja 9 lutego 2017 przez Mariusz M

const maxA=1000;
type TArray=array[0..maxA]of real;

procedure merge(var A:TArray;p,q,r:integer);
var n1,n2,i,j,k:integer;
       B:TArray;
begin
      n1:=q-p+1;
      n2:=r-q;
     for i:=p to r do 
         B[i-p+1]:=A[i];
     i:=1;
     j:=n1+1;
    k:=p;
     while((i<=n1)and(j<=n1+n2)) do 
     begin
         if(B[i]<=B[j]) then
         begin
              A[k]:=B[i];
              i:=i+1;
         end
         else
         begin
            A[k]:=B[j];
            j:=j+1;
         end;
         k:=k+1;
     end;
     while(i<=n1) do
     begin
          A[k]:=B[i];
          i:=i+1;
          k:=k+1;
     end; 
     while(j<=n1+n2) do
     begin
          A[k]:=B[j];
          j:=j+1;
          k:=k+1;
     end; 
end;

procedure mergeSort(var A:TArray;size:integer)
var curr,left,mid,right:integer;
begin
     curr:=1;
     while(curr<=size-1)  do 
     begin
          left:=0;
          while(left<size-1) do
          begin
              mid:=left+curr-1;
               if(left+2*curr-1<size-1) then
                  right:=left+2*curr-1
               else right:=size-1;
                merge(A,left,mid,right);
              left:=left+2*curr;      
          end;
          curr:=curr*2;
     end;
end;

Problem w tym że procedura sortująca napisana jest dla tablic indeksowanych od zera
a procedura scalająca napisana jest dla tablic indeksowanych od jedynki

Przypuśćmy że chcemy aby tablica była indeksowana od jedynki
Jak przesunąć indeksy w procedurze sortującej

Jaka jest złożoność procedury sortującej
Mam wątpliwości czy tak napisana procedura sortująca ma nadal złożoność O(nlogn)

Skoro koniecznie chcecie C to przepiszę interesującą mnie procedurę na C
 

                            
void mergeSort(double* A,int size)
{
      int curr,left,mid,right;
      curr=1;
      while(curr<=size-1) 
      {
        left=0;
        while(left<size-1)
        {
          mid=left+curr-1;
          if(left+2*curr-1<size-1)
             right=left+2*curr-1; 
          else right=size-1;              
          merge(A,left,mid,right);
          left=left+2*curr;
         }
         curr=curr*2;
        }
      } 


1 odpowiedź

0 głosów
odpowiedź 11 lutego 2017 przez Mariusz M Obywatel (1,670 p.)
Warunek dla tej wewnętrznej pętli był źle skonstruowany i dlatego miałem problemy z przesunięciem indeksów

Podobne pytania

0 głosów
2 odpowiedzi 696 wizyt
+1 głos
1 odpowiedź 776 wizyt
pytanie zadane 5 czerwca 2017 w C i C++ przez mazak12 Nowicjusz (150 p.)
0 głosów
2 odpowiedzi 751 wizyt
pytanie zadane 13 maja 2017 w C i C++ przez Ala123456 Użytkownik (760 p.)

92,753 zapytań

141,672 odpowiedzi

320,389 komentarzy

62,100 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...