[Benötige Hilfe] 2 Sortieralgorythmen

Special-K

hi leute.
ich bin neu hier und brauche gleich einmal eure hilfe

kurze einführung:

ich bin derzeit schüler einer HTL in österreich und mache meine Maturaarbeit im Bereich Informationstechnik. Als großes Hard- und Softwareprojekt wurde ich zusammen mit einigen anderen Schülern für das den Bau und Programmierung eines autonomen Roboters beauftragt.

Mein Projektteil beinhaltet die Bildverarbeitung, welche über eine Kamera die Umgebng des Roboters erkennt und diese in Graustufen umwandeln soll. Ziel ist eine Linienerkennung damit dem Hauptcontroller des Roboters über CAN-Bus die Bewegungskoordinaten vermittelt werden.

Das ganze geschieht mit einem Blackfin-Prozessor, genauer mit dem EZ-KIT Lite BF537.

Da im vorigen Jahr die Quellcodes bereits geschrieben wurden, es jedoch ein Problem mit der Synchronisierung der Bilddaten gab, liegt es nun an mir dieses zu beheben. Die dazu benötigten Kenntnisse sind zwar vorhanden, aber teils unzureichend.

Der gesammte Quellcode ist und wird in C geschrieben

Frage:

Könnte mir jemand die Funktionsweise des unten zu lesenden Quellcodes, speziell die Sortieralgorythmen erklären? Diese erscheinen mir... recht unlogisch

ich hoffe damit niemanden zu überfordern und würde mich über eine antwort freuen

/*
 * Getting Started With the ADSP-BF537 EZ-KIT Lite
 * Part 1, Exercise 1
 */

#include <stdlib.h>

#define NUM_ITERATIONS   1
#define ARRAY_LENGTH     128

/* Initialize two arrays to the same set of random values */
void randomize_arrays ( int *v1, int *v2, unsigned int length )
{
	unsigned int i;

	for ( i = 0; i < length; ++i )
	{
		v1[ i ] = v2[ i ] = rand () % 1024;
	}
}

/* A standard bubble sort algorithm, O(n^2) */
void bubble_sort ( int *v, unsigned int length )
{
	unsigned int i, j;

	for ( i = 0; i < length - 1; ++i )
	{
		for ( j = i + 1; j < length; ++j )
		{
			if ( v[ i ] > v[ j ] )
			{
				int temp = v[ i ];
				v[ i ] = v[ j ];
				v[ j ] = temp;
			}
		}
	}
}

/* A standard quick sort algorithm, O(n*log(n)) */
void quick_sort ( int *v, unsigned int p, unsigned int r )
{
	if ( p < r )
	{
		unsigned int x, i, j, q;

		x = v[ p ];
		i = p - 1;
		j = r + 1;

		for ( ;; )
		{
			do { --j; } while ( v[ j ] > x );
			do { ++i; } while ( v[ i ] < x );

			if ( i < j )
			{
				int temp = v[ i ];
				v[ i ] = v[ j ];
				v[ j ] = temp;
			}
			else
			{
				q = j;
				break;
			}
		}

		quick_sort ( v, p, q );
		quick_sort ( v, q + 1, r );
	}
}

int out_b[ ARRAY_LENGTH ];
int out_m[ ARRAY_LENGTH ];

void main ()
{
	int i;

	srand ( 22 );

	for ( i = 0; i < NUM_ITERATIONS; ++i )
	{
		randomize_arrays ( out_b, out_m, ARRAY_LENGTH );
		bubble_sort ( out_b, ARRAY_LENGTH );
		quick_sort ( out_m, 0, ARRAY_LENGTH - 1 );
	}
}

CStoll

Ich könnte es machen, aber ich verweise lieber auf vorgefertigte Erklärungen: BubbleSort und QuickSort.

Randfrage: Was genau haben die Sortieralgorithmen eigentlich mit deinem Roboter zu tun?

Special-K

1. danke für die verweise

CStoll schrieb:

Randfrage: Was genau haben die Sortieralgorithmen eigentlich mit deinem Roboter zu tun?

2. das is das von analog devices (hersteller des boards) mitgelieferte beispielprogramm. direkt mit dem roboter hat dies (noch) nichts zu tun...
dachte nur das es die eine oder andere meckerei (hatte bisher noch net so viele foren, in denen einem wirklich geholfen wurde) damit vermieden werden könnte. :p

ArneS

Kurze Randnotiz:

der Quicksort ist in Deinem Codeschnipsel ganz offensichtlich rekursiv programmiert. Da Du ja auf einem embedded System (Roboter) mit sicher recht eingeschränkten Ressourcen (RAM) unterwegs bist, mach Dir bei rekursiven Algorithmen besser Gedanken um die Rekursionstiefe, da diese ja den Stackverbrauch stark beeinflusst. Überlaufende Stacks können böse Debugfallen sein.

Special-K

quicksort wird soweit ich weiß nicht eingesetzt beim programmieren. aber keine sorge wird schon noch nachgepostet ^^

danke für die antworten