C++ Sortare

[Robert1995]

Am scris un program de sortare de plictiseala , nu zic ca e cea mai buna metoda si nu stie sigur daca merge in fiecare caz , daca stie cineva o metoda mai rapida , va rog share it

C++

#include <iostream>
#include <fstream>

using namespace std;

fstream fin("sortare.in" , ios::in);
fstream fout("sortare.out" , ios::out);

int vector[10000];
int vector_length;

void citire(){
    fin>>vector_length;
    for(int i=1;i<=vector_length;i++){
            fin>>vector[i];
    }
}

void dumpArray(){
    for(int i=1;i<=vector_length;i++){
            cout<<vector[i]<<" ";
    }
    cout<<endl;
}

void sortArray(){
    int last_number = vector[1];
    int last_position = 1;
    int aux;
    for(int i=2;i<=vector_length;i++){
            if(vector[i] < vector[i-1]){
                    aux = vector[i - 1];
                    vector[i-1] = vector[i];
                    vector[i]   = aux;
            }
            if(last_number > vector[i-1]){
                for(int j = last_position ; j>=1;j--){
                    if(vector[j-1] > vector[j]){
                        aux = vector[j - 1];
                        vector[j] = vector[j-1];
                        vector[j-1]   = aux;
                    }
                }
            }
            if(vector[i] > last_number ){
                last_number    = vector[i];
                last_position  = i;
            }
    }
}

int main(){
    citire();
    sortArray();
    dumpArray();
fin.close();fout.close();
return 0;
}

Teste

sortare.in

10

5 3 100 4 205 101 203 304 405 103

20

5 3 100 4 205 101 203 304 405 103
103 3 10440 4 2445 101 23303 304 42205 103

Edited September 30, 2011 by Robert1995

[Zamolxis666]

Nu e prea eficient pt ca foloseste bubble sort care are O(n) = n^2. Ceva eficient este Shell sort implementata cu threaduri, adica vectorul tau de nr era impartit in bucati si fiecare core al procesorului sorta cate o bucata, dupa care core-urile isi "luau" o alta bucata din vector pt sortat pe baza unui pas prestabilit.

[cmiN]

timsort > heapsort > mergesort > quicksort >> bubble sort

#include <algorithm>
std::sort(obj.begin(), obj.end()) // NlogN

[Robert1995]

multam fain

Revin cu edit ( nu vreau sa re inviu un post)

dupa un timp indelungat cand am avut timp sa mai ma joc cu c++

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

/** Pentru a stii daca execut interschimbarea din codul meu nu din functie , 
  * Mai multa viteza , asta e cea mai rapida cale de sortares
  */
struct myclass {
  bool operator() (float i,float j) { return (i<j);}
} myobject;

int main () {
    int nr_elem;
    // Citeste Elemente Clasic way ca un array
        cout<<"Nr Elemente :";cin>>nr_elem;
        float myints[1000];
        for(int i=0;i<nr_elem;i++){
            cin>>myints[i];    
        }  
    // Tranformam din array in obiect pentru a folosi tsort
        vector<float> myvector (myints, myints+nr_elem);
        vector<float>::iterator it;

    // Sortare Prima Jumatate
        sort (myvector.begin(), myvector.begin()+(nr_elem/2) , myobject);
    // Sortate a doua jumatate
        sort (myvector.begin()+(nr_elem/2), myvector.end(), myobject);  
    // Sortare intreaga , dar avem vectorul impartit in doua bucati gata sortate
        sort (myvector.begin(), myvector.end(), myobject);


    cout << "Vector :";
    for (it=myvector.begin(); it!=myvector.end(); ++it)
        cout << " " << *it;

    cout << endl;

return 0;
}

Edited October 28, 2011 by Robert1995