• PËRSHËNDETJE VIZITOR!

    Nëse ju shfaqet ky mesazh do të thotë se ju nuk jeni regjistruar akoma. Edhe pse nuk jeni regjistruar ju arrini të shihni pjesën me të madhe të seksioneve dhe diskutimeve të forumit, por akoma nuk gëzoni të drejten për të marrë pjesë në to dhe në avantazhet e të qënurit anëtar i këtij komuniteti. Ju lutem : REGJISTROHUNI që të dërgoni postime dhe mesazhe në Forumin Netedy.com.
  • Kerkojme ndjese per problemet qe mund te keni hasur me postimet e meparshme. Forumi eshte azhornuar me funksione te reja. Eshte e nevojshme te ri-vendosni foto e profilit nga e para! Argetim te kendshem ne NETEDY.COM!

Renditje e shpejte, duke perdorur vektor dhe interator ne STL

molecule

/dev/null < .cache
I Rregjistruar/e
Mesazhe
3,759
Location
127.0.0.1
Code:
/*
 * By Jianbao Tao @ SSL, UC Berkeley.
 *
 * Variable names follow conventions in CLRS.
 *   
 * Interface:
 * 1. partition(A, p, r): Return an index q so that each element in A[p:q-1] is less
 *                        than A[q] and each element in A[q+1:r] is greater than A[q].
 * 2. quickSort(A, p, r): No return.
 *
 * Operation flow in *partition*:
 * 1. Randomly pick an index irandom in [p, r], and swap A[r] with A[irandom].
 * 2. Use the new A[r] to be the pivot.
 * 3. Make a marching index iless so that it points to the last element that is
 *    less than the pivot and A[ismall+1] is greater than the pivot.
 * 4. Loop over A[p:r-1] with index j. If j > iless and A[j] is less than the pivot,
 *    then swap A[j] and A[iless+1].
 * 5. After the loop, swap A[r] and A[iless+1]
 * 6. Return iless+1 as q, i.e., q is the new position of the pivot.
 *
 * Operation flow in *quickSort*.
 * if p < r:
 *         q = partition(A, p, r);
 *         quickSort(A, p, q-1);
 *         quickSort(A, q+1, r);
 *
 * Compile command:
 *   clang++ -stdlib=libc++ -std=c++ -o a.out main.cpp
 *
 * Sample output:
 * --------------
 * Original order:
 * 32 37 16 33 57 81 14 4 73 3
 * Sorted order:
 * 3 4 14 16 32 33 37 57 73 81
 *
 */
 
#include <iostream>
#include <vector>
#include <random>
#include <ctime>
 
using std::cout;
using std::endl;
using std::vector;
 
//------------------------------------------------------------------------------
vector<int>::iterator partition(const vector<int> &A,
                                const vector<int>::iterator &p,
                                const vector<int>::iterator &r) {
    // Get a random element within A[p:r].
    auto seed = clock() * clock() * clock();
    std::default_random_engine dre(seed);
    std::uniform_int_distribution<size_t> di(0, r - p);
 
    auto random_it = p;
    random_it = p + di(dre);
 
    // Swap values of random_it and r.
    auto tmp = *random_it;
    *random_it = *r;
    *r = tmp;
 
    auto pivot = *r;
 
    int iless = -1;
    for(int i = 0; i < r - p; i++) {
        if(*(p+i) <= pivot) {
            iless++;
            if(iless != i) {
                // Swap *(p+iless) and *(p+i)
                tmp = *(p+iless);
                *(p+iless) = *(p+i);
                *(p+i) = tmp;
            }
        }
    }
 
    // Swap *(p+iless+1) and *r
    *r = *(p+iless+1);
    *(p+iless+1) = pivot;
 
    return p + iless + 1;
}
 
 
//------------------------------------------------------------------------------
void quickSort(const vector<int> &A, const vector<int>::iterator &p,
                                     const vector<int>::iterator &r) {
    if(p < r) {
        auto q = partition(A, p, r);
        quickSort(A, p, q-1);
        quickSort(A, q+1, r);
    }
}
 
//------------------------------------------------------------------------------
int main(int argc, char *argv[]) {
    // Make a vector to hold a sample array.
    vector<int> A;
 
    // Set up random number generator.
    auto seed = clock() * clock() * clock();
    std::default_random_engine dre(seed); // engine
    std::uniform_int_distribution<int> di(0, 100); // distribution
 
    // Populate A with 10 random number in [0,100].
    int num = 10;
    for(int i = 0; i != num; i++) A.push_back(di(dre)); // Roll the die.
 
    // Original order.
    cout << \"Original order:\" << endl;
    for(auto it = A.begin(); it != A.end(); it++)
        cout << *it << \" \";
    cout << endl;
 
    // Sort.
    auto p = A.begin();
    auto r = A.end() - 1;
    quickSort(A, p, r);
 
    cout << \"Sorted order:\" << endl;
    for(auto it = A.begin(); it != A.end(); it++)
        cout << *it << \" \";
    cout << endl;
 
    return 0;
}
 
Behuni pjesë e platformës së njohjeve online! Netedy është platforma e chatit më e madhe shqipfolëse! Aty ku mundesia për tu njohur me Vajza & Djem eshte bërë me e thjeshtë!
Top