Sortowanie różne metody
Kod był wyświetlany 3774 razy.
    /*
  Name: Sortowanie różne metody 
  Copyright: GPL GNU
   Date: 11-04-10 20:15
  Description: 
*/

// -----------------------------------------------------------------------------
//
//  Prezentacja metod sortowania (bubblesort, insertsort, selectionsort
//                                mergesort, quicksort)
//   
//
// -----------------------------------------------------------------------------

#include <iostream>

using namespace std;

// -----------------------------------------------------------------------------
//
//  (globalne) Deklaracje stalych oraz tablic: sortowanej i pomocniczej
//
// -----------------------------------------------------------------------------
const int rozmiar = 32;
const int zakres = 64;
int tab[rozmiar],temp[rozmiar];

// -----------------------------------------------------------------------------
//
// Procedura sortowania babelkowego
//
// -----------------------------------------------------------------------------

void bubblesort()
{
  int i,j; // zmienne - liczniki do petli for
  for (i=rozmiar-1;i>=1;i--) // tablice bedziemy przeszukiwac rozmiar-1 razy
    for (j=0;j<i;j++) // w tej petli odbywa sie przeszukanie tablicy za kazdym
                      // przeszukaniem jeden babelek bedzie wskakiwal na swoje miejsce
      if (tab[j]>tab[j+1]) swap(tab[j], tab[j+1]); // tu nastepuje "opadanie ciezkich babelkow"
                                                   // i unoszenie lekkich
}

// -----------------------------------------------------------------------------
//
// Procedura sortowania przez wstawianie
//
// -----------------------------------------------------------------------------

void insertsort()
{ 
  int i,j,t; //zmienne pomocnicze - i,j - liczniki petli, t - tymczasowa skrytka na wstawiany element
  for (j=rozmiar-2;j>=0;j--) // przeszukiwanie tablicy od elementu przedostatniego do poczatku
  {
    t=tab[j]; // chowamy wstawiany element to skrytki
    i=j+1;
    while ((i<=rozmiar-1) && (t>tab[i])) // w petli sprawdzamy gdzie sie ma znaleźć elememt w t
    {
      tab[i-1]=tab[i]; // robimy dla niego miejsce - "przesuwamy karty w lewo"
      i++;
    }
    tab[i-1]=t; // a gdy znajdziemy gdzie powinien byc, to wstawiamy
  }    
}

// -----------------------------------------------------------------------------
//
// Sortowanie przez wybor
//
// -----------------------------------------------------------------------------

void selectsort()
{
  int i,j,t; // deklaracje zmiennych: i,j - liczniki petli, t - tu przechowywujemy 
             //indeks najmniejszego elementu
  for (i=0;i<=rozmiar-2;i++) // dla elementow zbioru przeprowadzamy
  {                          // nastepujace operacje:
    t=i;                         // wyszukujemy element
    for (j=i+1;j<=rozmiar-1;j++) // najmniejszy wsrod elementow o indeksach
      if (tab[j]<tab[t]) t=j;    // od i+1 do konca tablicy     
    swap(tab[i],tab[t]);         // i zamieniamy go z elementem na pozycji i
  }                              // (na jego miejsce na poczatek)
}

// -----------------------------------------------------------------------------
//
// Sortowanie przez scalanie
//
// -----------------------------------------------------------------------------

void merge(int l, int s, int p) // pomocnicza procedura scalajaca dwa posortowane podzbiory
                                // procedura ta wykorzystuje globalnba tablice 'temp'
          // parametry: l - wspolrzedna pierwszego elementu pierwszego podzbioru
          //            s - wspolrzedna ostatniego elementu pierwszego podzbioru
          //            p - wspolrzedna pierwszego elementu drugiego podzbioru
{
  int a,b,c; // deklaracja zminnych: a,b - indeks w odpowiednio pierwszym i drugim podzbiorze
             // c - indeks elementu w tablicy temp pod który wstawimy element z jednego z podzbiorow
  c=l;       // przypisujemy c wartosc lewej wspolrzednej pierwszego podzbioru
  a=l;       // przypisujemy a wartosc lewej wspolrzednej pierwszego podzbioru
  b=s+1;     // przypisujemy c wartosc lewej wspolrzednej drugiego podzbioru 
             //(czyli indeks ostatniego elementu pierwszego podzbioru plus 1)
  for (c=l;c<=p;c++) // w petli przeszukujemy caly zbior 
  {
    if (a<=s) // jezeli a miesci sie w pierwszym podzbiorze
    {
      if (b<=p) // to sprawdzamy czy b miesci sie w drugim podzbiorze
      { // jak tak to porownujemy elementy podzbiorow i przzepisujemy odpowiedni
        // element z jednego z podzbiorow do tablicy tymczasowj
        if (tab[a]<tab[b])
        {
          temp[c]=tab[a];
          a++;
        }
        else
        {
          temp[c]=tab[b];
          b++;     
        }    
      }
      else // jeżeli b>p, to w drugim podzbiorze nie ma już co przepisiwac
      {    // ale w pierwszym jest jeszcze co
        temp[c]=tab[a]; // i przepisujemy to do tymczasowej tablicy
        a++;  
      }
    } else { // jeśli zaś a>s, to w pierwszym podzbiorze nie ma co przepisiwac
      temp[c]=tab[b]; // ale jest w drugim, wiec przepisujemy to tymczasowej tablicy
      b++;  
    }
  }
  for (c=l;c<=p;c++) // na sam koniec przepisujemy elementy z tablicy tymczasowj to podstawowej
    tab[c]=temp[c];
}

void mergesort(int l, int p) // góowna procedura sortowania przez scalanie
{                            //parametry l,p to indeks pierwszego i ostatniego elementu podzbioru w tablicy
  int t;       // deklaracja zmiennej t
  t=(l+p)/2;   // ktorej przypisujemy indeks "środdkowego" elementu
  if (l<t) mergesort(l,t); //nastepnie dzielimy podzbiory mniejsze (jesli tylko jest
  if (t+1<p) mergesort(t+1,p); // co dzielic) poprzez wywyolanie tej procedury z innymi parametrami
  merge(l,t,p); // a potem scalamy procedurą (poatrz procedura znajdująca się przed tą)
}

// -----------------------------------------------------------------------------
//
//  Procedura sortowania szybkiego
//
// -----------------------------------------------------------------------------

void quicksort(int l, int p) // parametry: l,p - lewa i prawa "wspolrzendna" 
{                            // podzbioru w sortowanej tablicy

  int i,pivot,j; // deklaracja zmiennych: i - licznik,
                 // pivot - zmienna wzgledem ktorej bedziemy dzielic zbior
                 // j - index elementu, z ktorym zamienimy miejscami element mniejszy od pivotu
  pivot=(l+p)/2; // za pivot wybieramy element o indeksie bedacym po srodku
  swap(tab[pivot],tab[p]); // zamieniamy pivot z elementem ostatnim
  j=l; // przypisanie do j lewej wspolrzednej
  for(i=l;i<p;i++) // przegladamy tablice w petli for
    if(tab[i]<tab[p]) //jezeli element o indeksie i jest mniejszy od pivotu 
    {                 //(ktory teraz jest na kocu tablicy)
      swap(tab[j],tab[i]); // to zamieniamy element o indeksie i z el. o indeksie j
      j++;                 // i przesuwamy "wskaźnik" j o jedną pozycję w lewo
    }  
  swap(tab[j],tab[p]); // po przeszukaniu tablicy zamieniamy pivot z elementem o indeskie j
                              // nastepnie stosujemy tą procedurę dla uzyskanych podzbiorow
  if(j-1>l) quicksort(l,j-1); //tych mniejszych od pivotu 
  if(p>j+1) quicksort(j+1,p); //i tych wiekszych od pivotu
                              //(jesli tylko to możliwe, tj. w podzbiorze są co najmniej 2 elementy.
}

// -----------------------------------------------------------------------------
//
// Główna petla programu
//
// -----------------------------------------------------------------------------

int main () 
{
  char wybor; // wybrana opcja menu
  int i; // licznik wwykorzystywany przy wyswietlaniu
  cout<< "\n\n\t\tPREZENTACJA METOD SORTOWANIA\n\n";
  cout <<"\n\t\tTablica przed sortowaniem:\n\n";
  srand(time(NULL)); // inicjujemy generator liczb pseudolosowych
  
  for (i=0;i<rozmiar;i++) // w petli
     {                       // wypelniamy tablice
    tab[i]=rand()%zakres; // losowymi wartosciami
    cout <<"  "<< tab[i] << "\t";//i przy okazji wyswietlamy ja zawartosc
      }
  cout << "\n\n\t\t\tWYBIERZ METODE\n\n\n"; // wyswietlamy menu z dostepnymi algorytmami sortowania
  cout << "\t1. Sortowanie babelkowe" << endl;
  cout << "\t2. Sortowanie przez wstawianie" << endl;
  cout << "\t3. Sortowanie przez wybor" << endl;
  cout << "\t4. Sortowanie przez scalanie" << endl;
  cout << "\t5. Sortowanie szybkie" << endl;
  cout << "\n\n\t? ";
  cin >> wybor; //czekamy na wybór
  switch (wybor)
  {
    case '1': bubblesort(); break; // gdy wybrano 1 - sortujemy babelkowo
    case '2': insertsort(); break; // gdy wybrano 2 - sortujemy przez wstawianie
    case '3': selectsort(); break; // gdy wybrano 3 - sortujemy przez wyszukiwanie
    case '4': quicksort(0,rozmiar-1); break; // gdy wybrano 4 - sortowanie przez scalanie, 
                          //jako parametry indeks pierwszego i ostatniego elementu tablicy
    case '5': mergesort(0,rozmiar-1); break; // gdy wybrano 5 - sortowanie szybkie
                          //jako parametry indeks pierwszego i ostatniego elementu tablicy
    default: cout << "Jak tak pogrywasz, to bedzie sortowanie babellkowe.\n"; bubblesort(); break;
    // gdy ktos testuje idioioodpornosc wpisujac cos spoza menu, to sortowanie babelkowe
  }
  cout << endl;
  cout << "\n\n\t\tTablica po posortowaniu:\n\n" << endl;
  for (i=0;i<rozmiar;i++) // wyswietlamy w petli
  cout <<" "<<tab[i] << "\t";// zawartosc posortowanej tablicy 
  cout << endl;
  
  cin.ignore();
  getchar();
  
  return 0; // i KONIEC :)
}
    
Pobierz plik tekstowy
Administrator WJL
PHP&SQL coded by NOVA-IT