Partycjonowanie tablicy.

Question

Nie działa mi poprawnie następujący program, mający partycjonować tablicę względem ostatniego elementu:

#include <iostream>

using namespace std;

void part( int * input, int l, int r );

int main()
{
	int A[6]={12,97,13,42,50,29};
		
	cout << "Tablica przed partycjonowaniem" << endl;
	
	for(int i=0; i<6; ++i)
	{
		cout << A[i] << endl;
	}
	
	part(A,0,6);
	
	cout << "Tablica po partycjonowaniu" << endl;
	
	for(int i=0; i<6; ++i)
	{
		cout << A[i] << endl;
	}
	
	return 0;
	
}

/*************************************************************************************************************************************************************/

void swap(float &a, float &b)
{
	a = a + b;
	b = a - b;
	a = a - b;
	return;
}

/*************************************************************************************************************************************************************/

void part( int * input, int l, int r ) //partycjonuje wzgledem ostatniej liczby
{
    int pivot = input[ r ];
   
    while( l < r )
    {
        while( input[ l ] < pivot ) 
             l++;
       
        while( input[ r ] > pivot )
             r--;
       
        if( input[ l ] == input[ r ] )
             l++;
        else if( l < r )
        {
        	swap(input[ l ],input[ r ]);
        }
    }
}

Tablica po partycjonowaniu powinna wyglądać tak, że elementy mniejsze od 29 są z lewej, a większe z prawej. Tymczasem po wywołaniu programu pojawia się tablica: 1,97,13, 42, 50, 29 (skąd w ogóle ta jedynka?!?!). Nie wiem czemu tak się dzieje. Byłbym wdzięczny jakby ktoś zerknął okiem i wskazał co zrobiłem nie tak.

Comments

Nie bedzie latwiej i szybciej przy pomocy ifa, to pytanie dla zaawansowanych z Was

Answer 1

1. Co to za przedziwna implementacja funkcji swap? Każda taka linijka to operacja arytmetyczna plus przypisanie, co daje w sumie przynajmniej sześć operacji. W porównaniu z utworzeniem zmiennej tymczasowej z jej inicjalizacją i wykonaniem dwóch podstawień wygląda to słabo. Poza tym istnieje już implementacja std::swap w bibliotece utility - skoro jest, to można skorzystać (implementacja w GCC6 również opiera się na zmiennej tymczasowej).

2. W wywołaniu funkcji part() podajesz jako prawą granicę indeks równy sześć - a Twoja tablica kończy się na piątym elemencie. Popraw to i powiedz, czy o to Ci chodziło.

Comments

ad.2 Dzięki, teraz działa. Coś słabo ze spostrzegawczością u mnie ostatnio.