Sortowanie pozycyjne, potrzebuje pomocy

0

Witam,
Potrzebuje zrealizować algorytm sortowania pozycyjnego przez sortowanie przez zliczanie. Mam działający kod ale nie do końca go rozumiem i prosił bym o łatwe i przejrzyste wyjaśnienie. Jestem początkujący.

#include "stdafx.h"
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <time.h>

using namespace std;

const int N     =  80;  // ilość elementów
const int MAXEL = 999;  // maksymalna wartość elementu

// Procedura sortująca

void Sortuj(unsigned z1[], unsigned z2[], unsigned m)
{
  unsigned L[2],i;

  L[0] = L[1] = 0;
  for(i = 1; i <= N; i++) L[(z1[i] & m) > 0]++;
  L[1] += L[0];
  for(i = N; i >= 1; i--) z2[L[(z1[i] & m) > 0]--] = z1[i];
}

int main()
{
  unsigned d[N+1],b[N+1],i,m;

  cout <<"Przed sortowaniem:\n\n";
          
// Generujemy pseudolosową zawartość zbioru d[ ]

  srand((unsigned)time(NULL));

  for(i = 1; i <= N; i++)
  {
    d[i] = rand() % (MAXEL + 1);
    cout << setw(4) << d[i];
  }
  
// Ustawiamy maskę na najmłodszy bit

  m = 1;

// Sortujemy

  while(m <= MAXEL)
  {
    Sortuj(d,b,m); m <<= 1;
    Sortuj(b,d,m); m <<= 1;
  }

// Wyświetlamy wyniki

  cout << "\nPo sortowaniu:\n\n";
  for(i = 1; i <= N; i++) cout << setw(4) << d[i];
  cout << endl;
  system("pause");
  return 0;
}

Czym tak na prawdę jest ta maska m? Czemu przyjmuje takie wartości?
I jak działa sama procedura sortująca? Teoretycznie wiem ale nie widzę w tym przełożenia na kod:

void Sortuj(unsigned z1[], unsigned z2[], unsigned m)
{
  unsigned L[2],i;

  L[0] = L[1] = 0;
  for(i = 1; i <= N; i++) L[(z1[i] & m) > 0]++;
  L[1] += L[0];
  for(i = N; i >= 1; i--) z2[L[(z1[i] & m) > 0]--] = z1[i];
}

Proszę o pomoc.
Studiuję informatykę i jest mi to potrzebne do pewnego projektu.Wydaje mi się, że taki algorytm ma ogromny potencjał i chciał bym go dobrze zrozumieć.

0

Przepraszam za podwójnego posta ale nie mam opcji edytowania ponieważ nie mam konta.
Chcę bliżej wyjaśnić co jest dla mnie niezrozumiałe:

L[(z1[i] & m) > 0]++; Co tutaj tak naprawdę jest wartością tej tabeli? Czy jej indeksem jest wartość tabeli z1 po indeksie i? To by mi nie pasowało do algorytmu ale z mojego punktu widzenia tak wynika z kodu.
Czemu jest ....&m>0 skoro m przyjmuje wartości 1++ zawsze będzie większe. Ehh wygląda na to, że w ogóle nie rozumiem tej instrukcji
z2[L[(z1[i] & m) > 0]--] = z1[i]; podobnie tutaj

I w jaki sposób to w ogóle rozpoznaje wagę cyfry w liczbie? Za pomocą maski m? Ale czemu w takim razie ona przyjmuje takie wartości.....

0

Popatrz tu : http://www.algorytm.org/kurs-algorytmiki/operacje-bitowe.html
a co do m to jest on ustawiony na 1 czyli binarnie jest to 00000001 po operacji m<<=1 jest to juz 00000010
Może Ci sie to do czegos przydac a na pewno nie zaszkodzi .

0

Dzięki za pomoc.
Przydała się.

1 użytkowników online, w tym zalogowanych: 0, gości: 1