3. Versuch, BubbleSort zu schreiben.

Versuch, BubbleSort zu schreiben.

  • S

    Ich habe versucht, den Algorithmus "BubbleSort" in C++ zu realisieren. Hätte gerne Eure Meinung bezüglich Stil und bin offen für Verbesserungsvorschläge:

    #include <iostream>
using namespace std;

template <size_t S>
void bubbleSort(int (&a)[S]);

int main()
{
	int a[19] = {34,34,56,657,768,435,76,35,27,87,546,8,65,754,756,8756,875,76};
	bubbleSort(a);
	for(int i = 0; i < 18; ++i)
		cout << a[i] << endl;
	cin.get();
}

template <size_t S>
void bubbleSort(int (&a)[S])
{
	for(int i = 0; i < S ; ++i)
	{
for(int i = 0, j = 1; i < S, j < S-1; ++i, ++j)
if(a[j] > a[i])
{
	int tmp;
	tmp = a[j];
	a[j] = a[i];
	a[i] = tmp;
}
}
}
    0
  • D

    Ne lesbare Version wär nich schlecht. Und bist du dir sicher mit dem 'i'? Ich habs nich komplett nachvollzogen, aber das sieht ziemlich seltsam aus.

    0
  • S

    David_pb schrieb:

    Ne lesbare Version wär nich schlecht. Und bist du dir sicher mit dem 'i'? Ich habs nich komplett nachvollzogen, aber das sieht ziemlich seltsam aus.

    Es tut schon das, was es soll, aber lesbarer wirds dadurch nicht, das stimmt schon -.- Hier nochmal mit Zufallszahlen:

    #include <iostream>
#include <time.h>
using namespace std;

template <size_t S>
void bubbleSort(int (&a)[S]);

int main()
{
	time_t t;
	int a[19];
	srand(time(&t));
	for(int f = 0; f < 18; ++f)
		a[f] = rand();
	bubbleSort(a);
	for(int i = 0; i < 18; ++i)
		cout << a[i] << endl;
	cin.get();
}

template <size_t S>
void bubbleSort(int (&a)[S])
{
	for(int i = 0; i < S ; ++i)
	{
for(int i = 0, j = 1; i < S, j < S-1; ++i, ++j)
if(a[j] > a[i])
{
	int tmp;
	tmp = a[j];
	a[j] = a[i];
	a[i] = tmp;
}
}
}
    0
  • J

    eine ordentliche Einrückung wäre mal das mindesteste.

    0
  • Mod

    Ich habe in deinem anderen Thread vorgeschlagen, dass Bubblesort sich als Übung für den abstrakten Umgang mit Iteratoren anbietet, ist aber wahrscheinlich noch etwas zu früh in deinem C++ Lernprozess. In ein paar Wochen kannst du das ja nochmal anschauen.

    0
  • ?

    Das mit deinem zweiten i ist definitiv redundant. Schau dir nochmal den Algorithmus genauer an, vorallem wo die zweite Schleife anfängt.

    Und da du schon auf einem template<> sitzt, könntest du noch aus dem int nen generisches T machen und somit beliebige Typen übergeben, vorausgesetzt op< ist für T überladen.

    0
  • S

    Hätte gerne Eure Meinung bezüglich Stil

    Ok. Die Wahl des Template-Parameters ist sehr unpraktisch:
    - Die Größe der zu sortierenden Sequenz muss zur Compile-Zeit bekannt sein.
    - Für jede Größe, wird eine eigene Funktion übersetzt ==> "code bloat"

    Eine freie Funktion a la

    void bubble_sort(int* start, size_t length)
{
  ...
}

    hätte es auch getan. Man kann ja immer noch ein Template für Arrays anbieten. Dann aber bitte inline und auf den obigen bubble_sort "umlenken":

    template<size_t N>
inline void bubble_sort(int (&arr)[N])
{ bubble_sort(arr,N); }

    Die innere Schleife sieht ein bissel kompliziert aus. Brauchst Du unbedingt 2 Laufvariablen? Eine von denen heißt ja auch wieder "i". Da kann man schonmal durcheinander kommen. Man muss in der inneren Schleife auch nicht mehr alle Elemente anfassen. Eigentlich nur S-i viele, wobei ich mit "i" das erste "i" meine. Denn nach dem ersten Durchlauf steht das größte Element ja schon an letzter Stelle. Nach dem 2. Durchlauf steht das zweitgrößte Element auch an zweitletzter Stelle u.s.w.

    Gruß,
    SP

    0

  • normalerweise hört man auf zu bubblen wenn man einen durchlauf hatte, wo man nichtmehr tauschen musste.

    so implementiert gibt es dann sogar praktische anwendungen für bubble-sort. nämlich wenn man oft mit bereits komplett sortierten input zu tun hat, bzw. mit welchen wo nur ein paar elemente um kurze strecken "verschoben" werden müssen.

    dann... die zweifache verwendung von "i" als laufvariable ist fürchterlich.

    und die zwei laufvariablen in der inneren schleife sind sinnlos - eine reicht da vollkommen. dadurch wird der schleifen-kopf auch 100x übersichtlicher.

    davon abgesehen macht i < S, j < S-1 als bedingung nicht das was du denkst. hier findet der ganz normale komma-operator anwendung, und das ergebnis des ausdrucks ist einfach nur j < S-1 (der teil nach dem letzten komma eben).

    int als schleifen-zähler sind in diesem fall auch nicht gut, hier wäre size_t angebracht. vor allem da du als template-parameter ja (sinnvollerweise) auch einen size_t verwendest.

    p.S.: sehe gerade dass einige dingen die ich da aufführe schon geschrieben wurden. man sehe es als bestätigung an 🙂

    0
  • V

    hustbaer schrieb:

    normalerweise hört man auf zu bubblen wenn man einen durchlauf hatte, wo man nichtmehr tauschen musste.

    Nee, normalerweise bubbelt man nur eins weniger als soweit, wie man beim letzten mal gebubbelt hat mit der Vorherannahme, daß man bis zum Ende gebubbelt haben würde.

    so implementiert gibt es dann sogar praktische anwendungen für bubble-sort. nämlich wenn man oft mit bereits komplett sortierten input zu tun hat, bzw. mit welchen wo nur ein paar elemente um kurze strecken "verschoben" werden müssen.

    Zweifellos. Wobei Spötter und Theoristen behaupten, Insertion Sort sei selbst bei der Heimatanwendung von Bubble Sort einen halben Tacken schneller.

    0

  • volkard schrieb:

    hustbaer schrieb:

    normalerweise hört man auf zu bubblen wenn man einen durchlauf hatte, wo man nichtmehr tauschen musste.

    Nee, normalerweise bubbelt man nur eins weniger als soweit, wie man beim letzten mal gebubbelt hat mit der Vorherannahme, daß man bis zum Ende gebubbelt haben würde.

    Hrrrrrrrrr, ja, hast Recht.
    Peinlich 🙂

    0
  • S
     

    #include <iostream>
#include <time.h>
using namespace std;

template <size_t S, class T>
void bubbleSort(T (&a)[S]);

int main()
{
    time_t t;
    int a[19];
    srand(time(&t));
    for(int f = 0; f < 18; ++f)
        a[f] = rand();
    bubbleSort(a);
    for(int i = 0; i < 18; ++i)
        cout << a[i] << endl;
    cin.get();
}

template <size_t S, class T>
void bubbleSort(T (&a)[S])
{
	for(size_t i = 0; i < S ; ++i)
    {
		for(size_t j = 1; j < S-1; ++j)
		if(a[i] > a[j])
		{
			size_t tmp;
			tmp = a[j];
			a[j] = a[i];
			a[i] = tmp;
		}
	}
}

    Ich habe es etwas verbessert, wäre nett, wenn jemand mir auch noch bei den restlichen Problemen helfen würde.

    0
  • S

    1. Das ist kein BubbleSort mehr
    2. Du parametrisierst immer noch die Länge

    0
  • S

    Sebastian Pizer schrieb:

    1. Das ist kein BubbleSort mehr
    2. Du parametrisierst immer noch die Länge

    #include <iostream>
#include <time.h>
using namespace std;

template <size_t S, class T>
void bubbleSort(T (&a)[S]); 

int main()
{
    time_t t;
    int a[19];
    srand(time(&t));
    for(int f = 0; f < 18; ++f)
        a[f] = rand();
    bubbleSort(a);
    for(int i = 0; i < 18; ++i)
        cout << a[i] << endl;
    cin.get();
}

template <size_t S, class T>
void bubbleSort(T (&a)[S])
{
for(size_t i = 0; i < S ; ++i)
{
	for(size_t i = 0; i < S; ++i)
	if(a[i+1] > a[i])
	{
		size_t tmp;
	    tmp = a[i+1];
		a[i+1] = a[i];
		a[i] = tmp;
	}
}
}

    Hier ist es wieder BubbleSort. Das Array soll dynamisch in der Länge sein? Wie kann ich dem Template denn einen Zeiger übergeben?

    0
  • Mod

    skullyan schrieb:

    Hier ist es wieder BubbleSort. Das Array soll dynamisch in der Länge sein? Wie kann ich dem Template denn einen Zeiger übergeben?

    Du machst irgendwie viel zu viele Threads zu fast gleichen Themen, so dass dann alle guten Antworten verstreut sind. Lies dir dies nochmal durch:

    http://www.c-plusplus.net/forum/viewtopic-var-t-is-248101.html

    Besonders den letzten Post von volkard, der die vorherigen nochmals zusammenfasst.

    0
Anmelden zum Antworten