Member Avatar for rizoshar

well i have 2 weeks reading and testing some C++ but unfortunately i fell into a wall.

I succeed making an array with random length and random elements (yeah i did it)and i want to help me making those elements sorted. eg quicksort

I read "algorithms in C++ " written by SEDGEWICK and here his proposal

template<class Item>
void quicksort(Item a[],int l,int r)
{
	if (r<=l) return;
	int m=partition(a,l,r);
	quicksort(a,l,m-1);
	quicksort(a,m+1,r);
}

template<class Item>
int partition(Item a[],int l, int r)
{
	int m=l-1, j=r; Item v=a[r];
	for(;;)
	{
		while(a[++m]<v);
		while(v<a[--j]) if (j==1) break;
		if(m>=j)break;
		exch(a[m],a[j]);
	}
	exch(a[m],a[r]);
	return m;
}

1st --How do i declare quicksort and partition in my main function. I tried to copy paste it (i know its wrong) and compile it but no luck
2nd--in the code above "a" will be my arrays name instead?
thanks
I'm looking forward to hearing from you

#include <iostream>
#include <cstdlib>
#include <ctime>






using namespace std;

class menu
{
	private:
		int choice;
	public:
		menu();
		void chooseOp();
};



int main()
{
      
    int len;
    int i;
    int *table;
    cout<<"******* WELCOME TO MY QUICKSORT ALGO *******\n";
    cout<<"Please enter the length of the array --> ";
    cin >>len;
    table=(int*)malloc(sizeof(int)*len);

    srand((unsigned)time(NULL));
    for(int i=0; i<len; i++)
    {
            
            table[i]=(rand()%20000)+1;
            cout<<table[i]<<" ";
    }
    menu();
    quicksort();
    return 0;
}

menu::menu()	
{
	cout<< "\n************************************************************************\n";
	cout<< "This program implements a quicksort algo................................\n";
	cout<< "Push a button to perform the corresponding operation....................\n";
	cout<< endl << endl;
	chooseOp();
}

void menu::chooseOp()	
{
	cout<< endl;
	cout<< "........1 ------- Sort the above array's implements --------------------\n";
	cout<< "........2 ------- Quit from Program ------------------------------------\n";
	cout<< endl;
	cin>> choice;

	if( choice == 1 )
	{
       		cout<<"The Quicksort Algo begins\n";
		exit(1);
	}	
	else if ( choice == 2 )
       	{
		cout<<"Bye bye.....\n";
		exit(0);
	}	
	else if (choice != 1 && choice!=2)
	{
        	cout<<"Wrong choice ... Please try again\n";
		menu();	
	}
}

/* here is the code that book has

template<class Item>
void quicksort(Item a[],int l,int r)
{
	if (r<=l) return;
	int m=partition(a,l,r);
	quicksort(a,l,m-1);
	quicksort(a,m+1,r);
}

template<class Item>
int partition(Item a[],int l, int r)
{
	int m=l-1, j=r; Item v=a[r];
	for(;;)
	{
		while(a[++m]<v);
		while(v<a[--j]) if (j==1) break;
		if(m>=j)break;
		exch(a[m],a[j]);
	}
	exch(a[m],a[r]);
	return m;
} 
*/
  • 3 Contributors
  • 4 Replies
  • 138 Views
  • 2 Days Discussion Span
  • Latest Post Latest Post by Narue
Member Avatar for n.aggel

hi rizoshar,

-first of all try to use code tags and indent your code to make it more readable....
read here to learn how to use code tags

- SEDGEWICK uses templates, you seem to be a beginner so try not to use templates until you learn a bit more....

-before you try to program an algorithm{i.e. quicksort} it would be useful to know what the algorithm is supposed to do {except from the apparent... i.e. sort} and then try to understand a simple implemenation in pseudocode. Afterwards you can procede and code it in your language of choice and in a second attempt you could use some facilities the language offers {i.e. templates} to make it more reusable, efficient etc.....

-there are tons of internet sites and books that explain quicksort. For example you could try wikipedia or this. Also a nice book is Introduction to Algorithms

After all these steps, if you have any question post back and we will help!

merry christmas :)
-nicolas

1st --How do i declare quicksort and partition in my main function. I tried to copy paste it (i know its wrong) and compile it but no luck
2nd--in the code above "a" will be my arrays name instead?
thanks

1st:: yeap, it is bad to copy paste code that you don't understand so don't do it :P .Of course it won't compile sedgewick uses some of his own functions{if i recall correctly} to make the code more readable
2nd:: yes a will be your array's name....

Member Avatar for Narue

First and foremost, don't ever use Robert Sedgewick's code. He knows his stuff when it comes to algorithms, he's a smart guy, and I recommend his books wholeheartedly for the descriptions and insights. But his code sucks ass! It's poorly written and often contains subtle or not so subtle bugs. I learned long ago that it's easier to understand the algorithm and write it myself than to fix Sedgewick's broken examples.

Try this instead, but keep that book and learn from it as long as you don't use the code. ;)

Member Avatar for rizoshar

Well thank you my friends for your advice;
I did what aggel said and i made my own version. It was a bit difficult but my algo seems to work wright. I love C programming more than C++ but the second one has more abilities i think. I will find them time to time. Narue the book you posted is a very good one. I didnt read it in detail but i think it will help me understand algo's. Sedgewicks book is very good too with full explanation but no very good code i think.

Merry Christmass and a happy new year

Member Avatar for Narue

>I love C programming more than C++ but the second one has more abilities i think.
C++ has more features, but it's no more powerful than C. In fact, simplicity is one of C's biggest strengths. While I would question whether anyone in the world knows C++ in its entirety, I would be surprised if any good C programmer wasn't familiar with all of C.

Personally, I'm not a big fan of C++.

>Narue the book you posted is a very good one.
Thank you.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.