Kody źródłowe/Sortowanie przez scalanie

Asembler x86

Poniższy kod jest prostą iteracyjną implementacją algorytmu sortowania przez scalanie. Sortowane są w kolejności rosnącej elementy tablicy znaków zgodnie z ich kodem ASCII.

section .data
; ciąg znaków do posortowania
msg1 db '9876543210ZYXQVUTSRQPONMLKJIHGFEDCBAzyxwvutsrqponmlkjihgfedcba543210'
; tablica pustych znaków
msg2 db '                                                                    '
src  dd 0	; wskaźnik do aktualnej źródłowej tablicy
dst  dd 0	; wskaźnik do aktualnej tablicy wynikowej
cnt  dd  68     ; rozmiar tablicy wpisany na stałe, znajdujący się także
                ; wpisany na stałe w linii 115 tego kodu źródłowego

bufor dd 0     ; ofset kolejnego znaku tablicy dst
skok dd 2      ; skok do początku następnej pary podciągów
ofset dd 0     ; 
indeks dd 0    ;

esiend dd 0    ; graniczne indeksy scalanych podciągów
ediend dd 0    ;
srcend dd 0    ;

endl  db 0x0a	; znak końca linii

section .text
global _start

_start:
   mov [src],dword msg1   ; początkowy wskaźnik do tablicy źródłowej
   mov [dst],dword msg2   ;  i docelowej

petla2:
   mov [bufor],dword 0    ; reset wartości indeksowych na początku
   mov [ofset],dword 0    ;  każdego obiegu pętli głównej
   mov [indeks],dword 0

   mov edx,[src]      ; ustawienie granicznych indeksów podciągu drugiego
   add edx,[cnt]      ; na koniec tablicy źródłowej
   dec edx            ;
   mov [srcend],edx   ;       
   
petla1:
   mov  ecx,[skok]     ; ecx zawiera liczbę znaków w obu podciągach do
					; wstawienia do ciągu wynikowego

   shr ecx,1        ; tymczasowa modyfikacja ecx na potrzeby poniższych
                    ; instrukcji
                    
   mov  esi,[src]	; esi ustawione na początek podciągu pierwszego
   add  esi,[ofset]
   
   mov  edi,esi		; 
   add  edi,ecx		; edi ustawione na początek podciągu drugiego

   mov  al,[esi]	; rejestry eax oraz ebx zawierają kolejne elementy
   mov  bl,[edi]	; porównywane w celu scalenia podciągów

   dec ecx          ; tymczasowa modyfikacja ecx na potrzeby poniższych
                    ; instrukcji
   
   mov edx,esi      ; ustawienie granicznych indeksów podciągu pierwszego
   add edx,ecx      ; na koniec podciągu pierwszego
   mov [esiend],edx ; 

   mov edx,edi      ; ustawienie granicznych indeksów podciągu drugiego
   add edx,ecx      ; na koniec podciągu drugiego zwiększając wartość o CF
   mov [ediend],edx ; 
   
   inc ecx          ; przywrócenie pierwotnej wartości ECX, który 
   shl ecx,1        ; będzie wykorzystywany w petli 'loop porownaj'

   mov edx,[dst]      ; wyznaczenie pierwszego indeksu ciągu wynikowego
   add edx,[ofset] ;
   mov [bufor],edx  ; kolejny indeks przechowywany jest w zmiennej bufor

   add [ofset],ecx ; zwiększenie ofsetu o wartość skoku na potrzeby kolejnego
                   ; obiegu pętli
porownaj:
      mov  edx,[bufor]

      cmp  esi,[srcend] ; jeżeli pierwszy podciąg doszedł do końca tablicy źródłowej
      jg   koniec       ;  rozpoczyna sie nowy obieg petli
      
      cmp  edi,[srcend] ; jeżeli drugi podciąg doszedł do końca tablicy źródłowej
      jg   pierwszy     ;  do tablicy wynikowej wpisywane są pozostałe 
                        ;  elementy z pierwszego podciągu

      cmp  esi,[esiend] ; jeżeli doszliśmy do końca pierwszego podciągu
      jg   drugi        ;  do tablicy wynikowej wpisywane są pozostałe 
			;  elementy z drugiego podciągu

      cmp  edi,[ediend] ; jeżeli doszliśmy do końca drugiego podciągu
      jg   pierwszy     ;  do tablicy wynikowej wpisywane są pozostałe 
                        ;  elementy z pierwszego podciągu

      cmp  al,bl	; porównuje kolejne elementy ze scalanych podciągów
      jl   pierwszy	;  kopiuje mniejszy z nich do tablicy wynikowej

drugi:
      mov  [edx],bl   ; jeżeli BL<=AL, wstawiamy BL do ciągu wynikowego
      inc  edi         ; przechodzimy do następnego znaku podciągu drugiego
      mov  bl,[edi]   ; i ładujemy do rejestru BL
      jmp  koniec

pierwszy:
      mov  [edx],al   ; jeżeli AL<BL, wstawiamy AL do ciągu wynikowego
      inc  esi        ; przechodzimy do następnego znaku podciągu pierwszego
      mov  al,[esi]   ; i ładujemy go do rejestru AL

koniec:
      inc edx
      mov [bufor],edx
      inc dword [indeks];
      loop porownaj    ; skok do kolejnego porównania

   cmp  [indeks], dword 68 ; dopóki nie przeszliśmy końcowego elementu ciągu
   jl  petla1     ; wynikowego, to porównujemy elementy kolejnych par podciągów

; wyświetla pośrednie tablice wynikowe
   mov	eax, 4		; eax=4, write() syscall
   mov	ebx, 1		; ebx=1, stdout
   mov	ecx, [dst]	; adres tekstu do ecx
   mov	edx, [cnt]	; długość tekstu do edx
   int	0x80		; wywołanie funkcji systemowej

; wyświetla znak końca linii
   mov	eax, 4		; eax=4, write() syscall
   mov	ebx, 1		; ebx=1, stdout
   mov	ecx, endl	; adres tekstu do ecx
   mov	edx, 1		; długość tekstu do edx
   int	0x80		; wywołanie funkcji systemowej

   mov eax,[src]        ; w celu oszczędności pamięci
   mov ebx,[dst]        ; tablica wynikowa staje się teraz źródłową,
   mov [src],ebx        ; a aktualna źródłowa będzie nadpisana zawartością
   mov [dst],eax        ; nowej tablicy wynikowej
		
   mov ecx,[skok]	; mnożymy skok przez 2, jeżeli nowy skok
   shl ecx,1		;  jest mniejszy od dwukrotności rozmiaru 
   mov [skok],ecx	; tablicy, wykonujemy skok do początku pętli głównej
   shr ecx,1		;
   cmp ecx,[cnt]	; rozpoczynając scalanie od pierwszego znaku
   jl petla2		; 

; kończy program
   mov	eax, 1			; exit() syscall
   mov	ebx, 5			; kod wyjścia
   int	0x80			;

Pascal

Struktura tablica jest tablicą, której elementy mogą być zmieniane, argumenty start, koniec są całkowitoliczbowe.

procedure merge(tablica, start, środek, koniec);

var tab_pom : array [0..koniec-start] of integer;
    i,j,k   : integer;

begin

  i := start;
  k := 0;
  j := środek + 1;

  while (i <= środek) and (j <= koniec) 
    begin 
      if tablica[i] <= tablica[j] then
        begin 
          tab_pom[k] := tab[i]
          i := i + 1;
        end
      else
        begin
          tab_pom[k] := tab[j];
          j := j + 1;
        end;
      k := k + 1;
    end;


  while (i <= środek)
    begin
      tab_pom[k] := tab[i];
      i := i + 1;
      k := k + 1;
    end;

  while (j <= koniec)
    begin
      tab_pom[k] := tab[j];
      j := j + 1;
      k := k + 1;
    end;

  for i:= 0 to koniec-start do
    tab[start + i] := tab_pom[i];  

end;



procedure merge_sort(tablica, start, koniec);

var środek : integer;

begin

  if start <> koniec then
  begin
     środek := (start + koniec) div 2;
     merge_sort(tablica, start, środek);
     merge_sort(tablica, środek + 1, koniec);
     merge     (tablica, start, środek, koniec);
  end;

end;

JavaScript

Porównanie mergsorterów znalezionych na: http://edu.i-lo.tarnow.pl/inf/alg/003_sort/0013.php oraz http://www.algorytm.org/algorytmy-sortowania/sortowanie-przez-scalanie-mergesort/merge-d.html Wszystko gotowe do odpalenia w konsoli firebuga

function merge(pocz, sr, kon)
{
  var i,j,q;
  t = new Array();
  for (i=pocz; i<=kon; i++) t[i]=tab[i];  // Skopiowanie danych do tablicy pomocniczej
  i=pocz; j=sr+1; q=pocz;                 // Ustawienie wskaźników tablic
  while (i<=sr && j<=kon) {  // Przenoszenie danych z sortowaniem ze zbiorów pomocniczych do tablicy głównej
        tab_iter++;
              
    if (t[i]<t[j])
        tab[q++]=t[i++];
    else
        tab[q++]=t[j++];
  }
  while (i<=sr) tab[q++]=t[i++]; // Przeniesienie nie skopiowanych danych ze zbioru pierwszego w przypadku, gdy drugi zbiór się skończył
}


function mergesort(pocz, kon)
{
  var sr;
  if (pocz<kon) {
    sr=Math.floor((pocz+kon)/2);
    mergesort(pocz, sr);    // Dzielenie lewej części
    mergesort(sr+1, kon);   // Dzielenie prawej części
    merge(pocz, sr, kon);   // Łączenie części lewej i prawej
  }
}



function onemerge(i_p, i_k)
{
  var i_s,i1,i2,i;
  p = new Array();
  i_s = Math.floor((i_p + i_k + 1) / 2);
  if(i_s - i_p > 1) onemerge(i_p, i_s - 1);
  if(i_k - i_s > 0) onemerge(i_s, i_k);
  i1 = i_p; i2 = i_s;
  for(i = i_p; i <= i_k; i++)
   {  d_iter++;
      
      p[i] = ((i1 == i_s) || ((i2 <= i_k) && (d[i1] > d[i2]))) ? d[i2++] : d[i1++];
   }

  for(i = i_p; i <= i_k; i++) d[i] = p[i];
}






tab_iter = d_iter = 0;
source= new Array();
for(counter = 0; counter < 100; counter++) source[counter] = Math.floor(Math.random() * 100);
tab = d = source;

mergesort(0, source.length-1);
onemerge(0,source.length-1);


console.log(tab);
console.log('tab iter'+tab_iter);
console.log('##################');
console.log(d);
console.log('d iter'+d_iter);

Python

def scal(n):
	if len(n)==1:return n
	s=int(len(n)/2)
	a=scal(n[:s])
	b=scal(n[s:])
	a=a[::-1]
	b=b[::-1]
	i=a.pop()
	e=b.pop()
	c=[]
	for x in range(len(n)):
			if(i<e):
				c.append(i)
				if not len(a)==0:
					i=a.pop()
				else:
					c.append(e)
					for q in b:
							c.append(q)
					break	
			else:
				c.append(e)
				if not len(b)==0:
					e=b.pop()
				else:
					c.append(i)
					for q in a:
							c.append(q)
					break

	return c