czwartek, 10 maja 2012

Proste sortowanie tablic w C++ - idealny sposób na maturę z informatyki

Matura się zbliża więc czas na trochę hacków ;)
Do rzeczy, czyli jak posortować tablicę liczb lub znaków bez znajomości ani jednego algorytmu sortowania:

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int i;
    string lancuch = "string do posortowania abzwcdexyfh";
    string tab_string[] = {"test","bB","A","D","1A","a","ds","asd","Bb","z"};
    int tab_int[] = {2,4,6,3,8,6,88,1,5,84,62};
    /*-------- Sortowanie tablicy z liczbami  ------*/

    int elementow = sizeof(tab_int)/sizeof(tab_int[0]);


    cout <<"Posortowana malejaco: ";
    sort(tab_int,tab_int+elementow,greater<int>());  //sortuje od najmniejszego do najwiekszego 1*
    for (i=0; i<elementow; i++)
    {
        cout << " "<< tab_int[i] ;
    }

    cout << endl<<"Posortowana rosnaco: ";
    sort(tab_int,tab_int+elementow); //sortuje od najwiekszego do najmniejszego 2*
    for (i=0; i<elementow; i++)
    {
        cout << " "<< tab_int[i] ;
    }
    /*-------- Sortowanie tablicy stringow ------*/
    elementow = sizeof(tab_string)/sizeof(tab_string[0]);



    cout << endl<<"Posortowana rosnaco: ";
    sort(tab_string,tab_string+elementow); //sortuje od najwiekszego do najmniejszego
    for (i=0; i<elementow; i++)
    {
        cout << " "<< tab_string[i] ;
    }

    cout << endl<<"Posortowana malejaco: ";
    sort(tab_string,tab_string+elementow,greater <string>());
    for (i=0; i<elementow; i++)
    {
        cout << " "<< tab_string[i] ;
    }
     /*-------- Zmiana wielkosci liter ---------*/
    cout<< "\nzamiana na duze litery";
    for (i=0; i<elementow; i++)
    {
        transform(tab_string[i].begin(),tab_string[i].end(),tab_string[i].begin(),::toupper);  //albo ::tolower 3*
    }
    cout << endl<<"Posortowana malejaco: ";
    sort(tab_string,tab_string+elementow,greater <string>());
    for (i=0; i<elementow; i++)
    {
        cout << " "<< tab_string[i] ;
    }

    cout << endl<<"Posortowana rosnaco: ";
    sort(tab_string,tab_string+elementow); //sortuje od najwiekszego do najmniejszego
    for (i=0; i<elementow; i++)
    {
        cout << " "<< tab_string[i] ;
    }


    cout<< "\nSortowanie wyrazow:";
    cout << endl<<"Posortowany rosnaco: ";
    sort(lancuch.begin(),lancuch.end());
    cout <<lancuch<<endl;

    cout << endl<<"Posortowany malejaco: ";
    sort(lancuch.begin(),lancuch.end(),greater <char>());
    cout <<lancuch<<endl;
    return 0;
}

Wynikiem tego kodu jest coś takiego:

Posortowana malejaco: 88 84 62 8 6 6 5 4 3 2 1
Posortowana rosnaco: 1 2 3 4 5 6 6 8 62 84 88
Posortowana rosnaco: 1A A Bb D a asd bB ds test z
Posortowana malejaco: z test ds bB asd a D Bb A 1A
zamiana na duze litery
Posortowana malejaco: Z TEST DS D BB BB ASD A A 1A
Posortowana rosnaco: 1A A A ASD BB BB D DS TEST Z
Sortowanie wyrazow:
Posortowana rosnaco: aaabcddefghiinnooooprrssttwwxyz
Posortowana malejaco: zyxwwttssrrpoooonniihgfeddcbaaa

Jak już z pewnością zauważyłeś po tym jak wnikliwie zanalizowałeś kod i wynik to funkcją sortującą z biblioteki algorithm jest sort a wykorzystuje się ją tak:
sort(pierwszy_element, ostatni_element, opcja);
opcja czyli w jaki sposób posortować zostawienie tylko dwóch pierwszych argumentów powoduje posortowanie od najwiekszego do najmniejszego elementu(1*) a z opcją
greater <typ_zmiennej>() sortuje od najmniejszego do największego elementu (2*)

Zauważamy również że funkcja sort sortuje znaki według numerów z tablicy znaków ASCII gdzie A ma numer 65, B 66, a mała litera: a 97. Dlatego może być nam potrzebna funkcja zamieniająca małe litery na duże (lub na odwrót). Funkcja ta to transform przykład jej użycia jest w wierszu 52 (3*)

Kolejną ciekawą funkcją jest partial_sort która pozwala nam posortować wybrany przez nas zakres.
przykład użycia:

string lancuch = "987654321";
partial_sort (lancuch.begin(), lancuch.begin()+5, lancuch.end());
cout << lancuch;

wynikiem będzie: 123459876