[LUGOS-PROG] Mergesort iterativno

[Andrej (Andy) Brodnik]

On Wed, Nov 05, 2003 at 03:04:26PM +0100, Simon Striker wrote:
> 
> Mi lahko kdo lepo prosim pomaga najti itertivno re9itev algoritma
> mergesort. Pripenjam prilogo, v kateri je moj program z rekurzivnim
> algoritmom, jaz pa moram program spremeniti tako, da bo algoritem
> iterativen.
> 
> Za morebitno pomoh oziroma nasvet se vsam >e v naprej zahvaljujem.

To ni ne zlivanje ne pospeseno urejanje. V osnovi je:

  mergsort(a, l, h):

    if (l < h) then
      mergesort(a, l, (l+h)/2)
      mergesort(a, (l+h)/2+1, h)
      merge(a, l, (l+h)/2, h)    // srednji argument je lahko opuscen

v resnici res zlivanje. Pospeseno urejanje je pa:

  quicksort(a, l, h):

    if (l < h) then
      m= choose(a, l, h)         // izberi delilini argument
      m= split(a, l, m, h)       // polje a je razdeljeno tako, da
				 // a[i]<=a[j], l<i<m<j<h
      quicksort(a, l, m-1)
      quicksort(a, m+1, h)

Bistvena  razlika je,  da se  rekurzivni  del ,,deli  in vladaj``  pri
zlivanju  zgodi  _pred_  zlivanjem  in pri  pospesenem  urejanju  _po_
razdeljevanju  polja.  To  in  kolicina zbrane  informacije  imata  za
posledico,  da  en  ureja v  O(n  logn)  premikih  in drugi  v  O(n^2)
premikih.

Kar  zadeva  iterativne  resitve   je  tako,  da  potrebujemo  dodatno
strukturo, ki hrani podprobleme, katere  se moramo resiti. To je lahko
sklad, na katerega nalagamo probleme in jih sproti resujemo:


  push(sklad, "mergesort(0, n)");

  while (! empty(sklad))
    problem= pop(sklad)
    if (problem == "mergesort(l, h)")
      if (l < h) then
        push(sklad, "merge(l, (l+h)/2, h)   ")
        push(sklad, "mergesort((l+h)/2+1, h)")
        push(sklad, "mergesort(l, (l+h)/2)  ")
    else
      merge(a, l, m, h)


Malce se je se potreba poigrati z definicijo sklada, a za namig:

typedef struct {
  bool  isMerge;
  union {
    struct _isMerge     { ... };
    struct _isMergeSort { ... };
  }
} itemOnStack;

Izziv: kako napisati podatkovno strukturo, ki si bi jo delilo vec
procesov in bi zlivanje napisali z vzporedno delujocimi procesi?

LPA