My Pastes
Public Pastes
Layout Width
Share Pastebin
Guest
Public paste!

sortowanie kubelkowe

By: a guest | Mar 20th, 2010 | Syntax: C++ | Size: 2.92 KB | Hits: 140 | Expires: Never
Download | Raw | Embed | Report abuse
Copy text to clipboard
  1. //sortowanie zliczeniowe
  2. void sortowanieZliczeniowe(int* tablica, int rozmiar)
  3. {
  4.      int min = tablica[0];
  5.      int max = tablica[0];
  6.      for(int i = 1; i < rozmiar; i++)
  7.      {
  8.          if(min > tablica[i])
  9.          {
  10.              min = tablica[i];
  11.          }
  12.          if(max < tablica[i])
  13.          {
  14.              max = tablica[i];
  15.          }
  16.      }
  17.      int* wartosci = new int[max - min + 1];
  18.      for(int i = min; i <= max; i++)
  19.      {
  20.          wartosci[i - min] = 0;
  21.      }
  22.      for(int i = 0; i < rozmiar; i++)
  23.      {
  24.          wartosci[tablica[i] - min]++;
  25.      }
  26.      int j = 0;
  27.      for(int i = min; i <= max; i++)
  28.      {
  29.          while(wartosci[i - min] > 0)
  30.          {
  31.              tablica[j] = i;
  32.              j++;
  33.              wartosci[i - min]--;
  34.          }
  35.      }
  36.      delete [] wartosci;
  37.      wartosci = 0;
  38. }
  39. //sortowanie kubełkowe
  40. void sortowanieKubelkowe(int* tablica, int rozmiar)
  41. {
  42.      int min = tablica[0];
  43.      int max = tablica[0];
  44.      for(int i = 1; i < rozmiar; i++)
  45.      {
  46.          if(min > tablica[i])
  47.          {
  48.              min = tablica[i];
  49.          }
  50.          if(max < tablica[i])
  51.          {
  52.              max = tablica[i];
  53.          }
  54.      }
  55.      int przedzial = (int)sqrt(max - min);
  56.      if(przedzial == 0)
  57.      {
  58.          przedzial = 1;
  59.      }
  60.      int ile = (int)((max - min)/przedzial)+1;
  61.      int *rozmiary = new int[ile];
  62.      int *indeksy = new int[ile];
  63.      int **kubelki = new int*[ile];
  64.      int ktory;
  65.      for(int i = 0; i < ile ;i++)
  66.      {
  67.          rozmiary[i] = 0;
  68.          indeksy[i] = 0;
  69.      }
  70.      for(int i = 0; i < rozmiar; i++)
  71.      {
  72.          ktory = (int)((tablica[i] - min)/przedzial);
  73.          rozmiary[ktory]++;
  74.      }
  75.      for(int i = 0; i < ile; i++)
  76.      {
  77.          if(rozmiary[i] > 0)
  78.          {
  79.              kubelki[i] = new int[rozmiary[i]];
  80.          }
  81.      }
  82.      for(int i = 0;i < rozmiar; i++)
  83.      {
  84.          ktory = (int)((tablica[i] - min)/przedzial);
  85.          kubelki[ktory][indeksy[ktory]] = tablica[i];
  86.          indeksy[ktory]++;
  87.      }
  88.      for(int i = 0; i < ile; i++)
  89.      {
  90.          if( (rozmiary[i] > 1)&&(!sprawdzTablice(kubelki[i],rozmiary[i]) ) )
  91.          {
  92.              if(przedzial > 100)
  93.              {
  94.                  sortowanieKubelkowe(kubelki[i],rozmiary[i]);
  95.              } else {
  96.                  sortowanieZliczeniowe(kubelki[i],rozmiary[i]);
  97.              }
  98.          }
  99.      }
  100.      int index = 0;
  101.      for(int i = 0; i < ile; i++)
  102.      {
  103.          for(int j = 0; j < rozmiary[i]; j++)
  104.          {
  105.              tablica[index] = kubelki[i][j];
  106.              index++;
  107.          }
  108.      }
  109.      for(int i = 0; i < ile; i++)
  110.      {
  111.          if(rozmiary[i] > 0)
  112.          {
  113.              delete [] kubelki[i];
  114.              kubelki[i] = 0;
  115.          }
  116.      }
  117.      delete [] kubelki;
  118.      kubelki = 0;
  119.      delete [] rozmiary;
  120.      rozmiary = 0;
  121.      delete [] indeksy;
  122.      indeksy = 0;
  123. }
create new paste | create new version of this paste RAW Paste Data