Sortieren

Stromberg

Bei der Sortierung hier:

#include <iostream>
#include <conio.h>
#include <stdlib.h>
using namespace std;

int rnd(int a,int b);
void Swap(int &a,int &b);
void Sort(int *array,int size);

int main()
{
    srand(time(0));
    rand();

    int data[300000];
    for (int i=0;i<300000;i++)
    {
        data[i]=rnd(0,50000);
    }
    cout << "START\n";

    int anfang=time(0);

    Sort(data,300000);

    int ende=time(0);
    for (int i=0;i<300000;i++)
    {
        cout << data[i] << "\n";
    }
    cout << "Es sind " << ende-anfang << " Sekunden vergangen.\n";
    getch();

    return 0;
}

void Sort(int *array,int size)
{
    int minPos;
    for (int feld=0;feld<size-1;feld++)
    {
        minPos=feld;
        for (int i=feld+1;i<size;i++)
        {
            if (array[i]<array[minPos])
            {
                minPos=i;
            }
        }
        Swap(array[feld],array[minPos]);
    }
}

void Swap(int &a,int &b)
{
    int temp=a;
    a=b;
    b=temp;
}

int rnd(int a,int b)
{
     return (rand() % (b-a+1)) + a;
}

dauert es bei mir 192 Sekunden bis das data[300000] Feld sortiert ist! (anfangs schreibe ich ja mit Hilfe der rnd Funktion Zufallswerte in das data Feld)
Wie kann ich die Sortierung beschleunigen? Was für Ideen habt ihr?

Fabeltier

Hallo,
Entweder nen anderen Suchalgorithmus, bspw. Quicksort oder gleich sort() bzw. stable_sort() aus der STL verwenden.

Stelfer

je nach aufgabe, shellsort, quicksort, heapsort oder sort by insert benutzen

das verringert die zeit

deine funktion wächst x² das ist eigentlich sehr schlecht bei einem eingabewert gegen unendlich, bei großen zahlen quicksort benutzen, bei einfachen zahlen kannst du es aus der lib nehmen, andernfalls wenn es was kompliziertes ist musst du es halt selbst schreiben