int - Vector der Größe nach sortieren

Hey Leute,

hab seit einigen Tagen ein Problem, an dem ich net weiterkomme, und zwar will ich ne Funktion basteln, der ich einen int-vector übergebe und die mir einen int-vector mit den gleichen Elementen, aber der Größe nach aufsteigend sortiert zurückliefert ...

const std::vector<int> SortiereAufsteigend(std::vector<int> v) {
  std::vector<int> _mvec(v);

  // krieg ich net hin

  return _mvec;
}

Was ich auch probiert hab, irgendwas hat immer net gepasst; irgendwie bin ich zu doof dafür

Konrad Rudolph

std::sort(vec.begin(), vec.end());

Header: algorithm.

kenn ich schon, aber ich wills ja mal sehen, wie der Code aussieht, wenn mans selber machen würde -.-

Konrad Rudolph

VectornichtBlicker schrieb:

kenn ich schon, aber ich wills ja mal sehen, wie der Code aussieht, wenn mans selber machen würde -.-

Dann schau Dir doch den Quelltext der Datei an. Wenn Du es erklärt haben willst, lies die Wikipedia-Artikel zu Quicksort, Heapsort und Introsort.

hustbaer

@VectornichtBlicker:

Vielleicht solltest du dich Schrittweise herantasten. Der wohl einfachste sort Algorithmus is der "selection sort" - das ist quasi die "brute force" Variante beim Sortieren. Den bekommt jeder hin.

http://en.wikipedia.org/wiki/Selection_sort

Dann weiter zum Bubble Sort, der is schon eine winzige Spur komplizierter, dafür auch manchmal schneller. Wenn du die beiden hast guck dir als nächstes Quicksort oder Mergesort an (eher Quicksort, is denke ich der einfachere der beiden). Heapsort lass mal aussen vor.

Alles nicht so wild tragisch, sortieren ist echt keine Zauberei

Konrad Rudolph

hustbaer schrieb:

Alles nicht so wild tragisch, sortieren ist echt keine Zauberei

In C++ schon ein wenig. Sortieralgorithmen sind in Sprachen mit Fokus auf die Problemstellung, wir Haskell, sehr viel einfacher zu lernen. Wenn man sich z.B. Hoares C-Implementierung des Quicksort-Algorithmus anschaut, dann schaut man gewissermaßen in die Röhre. Ich würde daher sehr empfehlen, Quicksort am Beispiel der Haskell-Implementierung durchzuexerzieren, selbst wenn das bedeutet, dass man zuerst Haskell lernen muss (lohnt sich sowieso).

finix

hustbaer schrieb:

Der wohl einfachste sort Algorithmus is

Bogosort?

hustbaer

Naja, wenn man die "is sorted" Funktion und die "random shuffle" Funktion selbst ausprogrammieren muss dann ist das denke ich etwa gleich viel Aufwand wie einen selection sort zu programmieren.

Aber dümmer ist er auf jeden Fall

Shinja

http://www.sortieralgorithmen.de

Beschreibungen, Code Beispiele, Verbesserungen. Mir gefällt die Seite zumindest.

Anfangslektüre: Bubblesort, Selectionsort, Insertionsort, Shellsort und Quicksort (persönliche Meinung). Danach beliebig weiter.