[C++ / Ordinamento Quicksort] Problemi nella ricorsione

[unslee]

Ciao a tutti,
ormai da qualche giorno sono impantanato su un esercizio. Ci ho ragionato, l'ho rifatto da zero ... ma niente!

Quest'esercizio è all'intero del capitolo sui puntatori.

Il testo recita così:
Ordinamento quicksort; l'algoritmo di base per un array monodimensionale è il seguente:

a) Partizionamento: Prendete il primo elemento di un array non ordinato e determinate il suo indirizzo finale nell'array ordinato, vale a dire tutti i valori a sinistra dell'elemento sono minori e tutti i valori a destra sono maggiori. A questo punto si ha un elemento nell'indirizzo giusto e due sottoarray non ordinati.

b) Passo ricorsivo: Effettuate l'operazione precedente su ciascun sottoarray.

Scrivere la funzioni quicksort che ordina un array di interi monodimensionale. La funzione dovrebbe ricevere come argomenti l'array di interi, l'indice iniziale e l'indice finale. La funzione quickSort dovrebbe chiamare la funzione partition per effettuare il partizionamento.

Con altre indicazioni relative al partizionamento sono riuscito a metter su la funzione partition che
a) riceve un array un indice iniziale ed un indice finale
b) sistema al posto giusto il primo valore dell'array
c) restituisce alla funzione chiamante il valore sistemato

La fuzione chiamante (quickSort) tramite il valore che le restituisce la funzione partition riesce a determinare esattamente ila posizione del valore in questione.

A questo punto dovrei creare due sottoarray (uno con i valori a destra del primo valore sistemato, l'altro con i valori a sinistra) da ridare in pasto alla funzione partition ma la cosa qui si complica parecchio.

a) Se cerco di creare due sottoarray distinti mi trovo un muro davanti perché la dimensione deve essere una costante (nel nostro caso non lo è perchè il primo valore sistemato può trovarsi ovunque nell'array).

b) Se cerco di lavorare sull'array originario facendo variare le posizioni iniziali e le posizioni finali da dare in pasto a partition non riesco ad impostare la ricorsione.

Di seguito posto il codice. La perplessità è anche che, trattandosi di esercizio sul capitolo relativo ai puntatori, dovrei sfruttarne le potenzialita, ma non riesco a capire come!

Ringrazio anticipatamente tutti per l'aiuto.

#include "stdafx.h"

#include <iostream>
using std::cout;
using std::endl;


int _tmain(int argc, _TCHAR* argv[])
{
	return 0;
}

void quickSort(int [], int, int);
int partition(int [], int, int);

int main()
{
	int a[10] = {3, 6, 5, 1, 2, 9, 8, 10, 11, 7};
	int indiceIniziale = 0;
	int indiceFinale = 9;

	quickSort(a, indiceIniziale, indiceFinale);

	for (int i = 0; i <= 9; i++)
		cout << a[i] << "-";

	cout << endl;

	return 0;
}

void quickSort(int a[], int indiceIniziale, int indiceFinale)
{
	
	int numberx = partition(a, indiceIniziale, indiceFinale);
	int position = 0;

	for (int i = indiceIniziale; i <= indiceFinale; i++)
		if (a[i] == numberx)
			position = i;
	
	for (int i = indiceIniziale; i < position; i++)
		{cout << a[i] << "-";
		counter1++;}

//Da qui non riesco più ad andare avanti!

	
}

int partition(int a[], int indiceIniziale, int indiceFinale)
{

int numberx = a[0];
int currentPosition = 0;
int previousPosition = 0;
int stopCicle = 1;
int stopWhile = 0;
int temp = 0;

for (int i = indiceFinale; i >= currentPosition && stopCicle == 1; i--)
	if (a[i] < a[currentPosition])
		{temp = a[i];
		a[i] = a[currentPosition];
		a[currentPosition] = temp;
		stopCicle = 0;}

for (int i = 0; i <= indiceFinale; i++)
cout << a[i] << "-";
cout << endl;

for (int i = 0; i < indiceFinale; i++)
	{if (a[i] == temp)
		previousPosition = i;
	if (a[i] == numberx)
		currentPosition = i;}

if (currentPosition != indiceIniziale && currentPosition != indiceFinale)
{

while (stopWhile == 0)
{
for (int i = 0; i < indiceFinale; i++)
	{if (a[i] == temp)
		previousPosition = i;
	if (a[i] == numberx)
		currentPosition = i;}

for (int i = previousPosition + 1; i <= currentPosition && stopCicle == 0; i++)
	if (a[i] > a [currentPosition])
		{temp = a[i];
		a[i] = a[currentPosition];
		a[currentPosition] = temp;
		stopCicle = 1;
		stopWhile = 0;}
	else
		stopWhile = 1;

for (int i = 0; i <= indiceFinale; i++)
cout << a[i] << "-";
cout << endl;

for (int i = 0; i < indiceFinale; i++)
	{if (a[i] == temp)
		previousPosition = i;
	if (a[i] == numberx)
		currentPosition = i;}

for (int i = previousPosition - 1; i >= currentPosition && stopCicle == 1; i--)
	if (a[i] < a [currentPosition])
		{temp = a[i];
		a[i] = a[currentPosition];
		a[currentPosition] = temp;
		stopCicle = 0;
		stopWhile = 0;}
	else
		stopWhile = 1;

	for (int i = 0; i <= indiceFinale; i++)
	cout << a[i] << "-";
	cout << endl;
}

}
cout << numberx << endl;
return numberx;

}

[banryu79]

Ciao unslee,
qui su wikipedia trovi una pagina dedicata al popolarissimo quicksort: verso l'inizio c'è la descrizione in pseudo-codice dell'implementazione ricorsiva.
Per divertiti puoi anche consultare il pseudo-codice della versione iterativa e provare a implementare anche quella.

Ci dedichi 30 min di attenta lettura e secondo me basta per dipanarti i dubbi

[71104]

#include <cstdlib>

...

int Comparator(const void *Item1, const void *Item2)
{
	if (*(int*)Item1 < *(int*)Item2)
	{
		return -1;
	}
	else if (*(int*)Item1 > *(int*)Item2)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

void QuickSort(int *Array, size_t Count)
{
	qsort(Array, Count, sizeof(int), Comparator);
}

[71104]

anzi guarda, ti metto anche un'implementazione più efficiente

#include <cstdlib>

...

int Comparator(const void *Item1, const void *Item2)
{
	return *(int*)Item1 - *(int*)Item2;
}

void QuickSort(int *Array, size_t Count)
{
	qsort(Array, Count, sizeof(int), Comparator);
}

[unslee]

Che dire ... uno spettacolo! rimango sempre senza parole!

Grazie a tutti per il preziosissimo aiuto.

Mi metto subito al lavoro per capire l'esercizio secondo le indicazioni di 71104. Non mancherò di approfondire su wikipedia come suggerito da banryu79.

Se non ci foste ... bisognerebbe inventarvi!.

A presto,

Unslee

[banryu79]

Solo un momento, l'ottimo codice di 71104 fa uso della funzione qsort presente nella libreria standard "cstdlib": se tu stai imparando dalle basi allora ti consiglio di:
- leggerti le risorse online sul quick sort
- scrivere una tua implementazione dell'algoritmo (anche per via dell'esercizio sui puntatori)
- quindi leggere e capire quello che ha scritto 71104 e leggere e capire qsort

Ciao e buono studio

[unslee]

Grazie per il suggerimento. In effetti ho trovato la risoluzione di 71104 un pò complessa ed allora ne ho preso solo qualche spunto. Dopo aver studiato la problematica su wikipedia en e it sono riuscito a risolvere l'esercizio.

Di seguito la risoluzione completa. E' chiaro che qualsiasi suggerimento sarà gradito perchè sono veramente alle prime armi!

#include "stdafx.h"

#include <iostream>
using std::cout;
using std::endl;


int _tmain(int argc, _TCHAR* argv[])
{
	return 0;
}

void quickSort(int [], int, int);
int partition(int [], int, int);

int main()
{
	int a[10] = {37, 2, 6, 4, 89, 8, 10, 12, 68, 45};
	int indiceIniziale = 0;
	int indiceFinale = 9;

	for (int i = 0; i <= 9; i++)
		cout << a[i] << "-";

	cout << endl;

	quickSort(a, indiceIniziale, indiceFinale);

	for (int i = 0; i <= 9; i++)
		cout << a[i] << "-";

	cout << endl;

	return 0;
}

void quickSort(int a[], int indiceIniziale, int indiceFinale)
{
	int positionx;

	if (indiceIniziale < indiceFinale)
	{
		positionx = partition(a, indiceIniziale, indiceFinale);
		
		
		quickSort(a, indiceIniziale, positionx - 1);
		quickSort(a, positionx + 1, indiceFinale);
	}

	return;
}

		

	

int partition(int a[], int indiceIniziale, int indiceFinale)
{

int numberx = a[indiceIniziale];
int currentPosition = 0;
int previousPosition = 0;
int stopCicle = 1;
int stopWhile = 0;
int temp = 0;

for (int i = indiceFinale; i > indiceIniziale && stopCicle == 1; i--)
	if (a[i] < a[indiceIniziale])
		{temp = a[i];
		a[i] = a[indiceIniziale];
		a[indiceIniziale] = temp;
		stopCicle = 0;}

for (int i = indiceIniziale; i <= indiceFinale; i++)
	{if (a[i] == temp)
		previousPosition = i;
	if (a[i] == numberx)
		currentPosition = i;}

if (currentPosition != indiceIniziale)
{

while (stopWhile == 0)
{
for (int i = indiceIniziale; i <= indiceFinale; i++)
	{if (a[i] == temp)
		previousPosition = i;
	if (a[i] == numberx)
		currentPosition = i;}

for (int i = previousPosition + 1; i <= currentPosition && stopCicle == 0; i++)
	if (a[i] > a [currentPosition])
		{temp = a[i];
		a[i] = a[currentPosition];
		a[currentPosition] = temp;
		stopCicle = 1;
		stopWhile = 0;}
	else
		stopWhile = 1;

for (int i = indiceIniziale; i <= indiceFinale; i++)
	{if (a[i] == temp)
		previousPosition = i;
	if (a[i] == numberx)
		currentPosition = i;}

for (int i = previousPosition - 1; i >= currentPosition && stopCicle == 1; i--)
	if (a[i] < a [currentPosition])
		{temp = a[i];
		a[i] = a[currentPosition];
		a[currentPosition] = temp;
		stopCicle = 0;
		stopWhile = 0;}
	else
		stopWhile = 1;

}

}

for (int i = 0; i < indiceFinale; i++)
	if (a[i] == numberx)
		return i;
}

[unslee]

... dimenticavo! Visto che il programma gira mi piacerebbe sapere se, dato il tipo di soluzione che ho adottato, l'utilizzo dei puntatori è consigliato e come implementarlo.

Grazie ancora per la collaborazione!

Unslee

[Noixe]

mmm tempo fa scrissi questa versione di quicksort molto più breve, non so se possa servirti:

#include <iostream>

const int max = 10;

int vettore [max];

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

void quicksort(int left, int right, int array []) {
int i = 0, j = 0, pivot = 0;

        i = left;
        j = right;
        pivot = array[(left + right) / 2];
        do {
	        while (array[i] < pivot)
                  i++;
            while (pivot < array[j])
	              j--;
            if (i <= j) {
              swap(array[i++], array[j--]);
            };
        }
        while  (i <= j);
        if (left < j)
                quicksort(left, j, array);
        if (i < right)
                quicksort(i, right, array);
};


int main () {
    int j = 0;
	for (int i = max - 1; i >= 0; i--)
		vettore[j++] = rand();
		
	for (int i = 0; i < max - 1; i++)
	    std::cout << vettore[i] << std::endl;
     
    std::cout << "\nDopo l'ordinamento:\n" << std::endl;
    
	quicksort(0, max - 1, vettore);
	for (int i = 0; i < max; i++)
		std::cout << vettore[i] << std::endl;
	while(std::cin.get() != '\n');
    return 0;
}

Ciao

[71104]

Originariamente inviato da unslee

In effetti ho trovato la risoluzione di 71104 un pò complessa