Sorting Procedure Problems: Quick Sort

[migzicat]

Im currently working on QuickSort,and yes I am just a beginner in C++ and Im still trying to master the basics of C++ programming.
I made my own Quick Sort code, it works fine and it gets the elements sorted.
But when I try inserting same elements like (1, 8, 8, 9, 9, 10, 10, 2, 2, 5), the sorting is unsuccessful.

#include<iostream>
using namespace std;
int main()
{
	int x, y, z, a, b, c, size, ctr=0, hold;
	int num[100];
	int main[100];

	cout<<"Enter desired size of Elements: ";
	cin>>size;
	cout<<endl;

	
	for(x=0;x<size;x++)
	{
		cout<<"Enter #"<<x+1<<": ";
		cin>>num[x];
		cout<<endl;
	}

	cout<<"The Original order of the elements is: ";

	for(x=0;x<size;x++)
	{
		cout<<num[x]<<" ";
	}
	cout<<"\n\n";

	x=0;
	y=size-1;

	for(z=0;z<size-1;z++)
	{
		a=0;
		cout<<"Pass "<<z+1<<"------------------\n\n";


	while(x!=y)
	{
		a=a+1;
		main[z]=num[x];
		ctr=ctr+1;

			if(num[x]>num[y])
			{
				hold=num[x];
				num[x]=num[y];
				num[y]=hold;
			}	
			
					
			if(num[x]==num[y])
			{
			
				y=y-1;
			}
			else
			{
			if(num[x]==main[z])
			{
				y=y-1;
			}
			else if(num[y]==main[z])
			{
				x=x+1;
			}
			}

			cout<<"Round "<<a<<"------------------------"<<endl;
			cout<<"  ";
			
			for(b=0;b<size;b++)
			{
				if(b==size-1)
					cout<<num[b]<<endl;
				else
					cout<<num[b]<<", ";
			}
			cout<<endl;

	}
//for determining the new pivot(main number)
			x=0;
			y=size-1;

			for(c=0;c<ctr;c++)
			{
				if(num[x]==main[c])
				{
					x=x+1;
				}
				if(num[y]==main[c])
				{
					y=y-1;
				}
			}
	}

	cout<<"The sorted Elements are: ";
	
	for(z=0;z<size;z++)
	{
		if(z==size-1)
		{
			cout<<num[z]<<endl;
		}
		else
			cout<<num[z]<<", ";
	}


	cout<<endl;

	return 0;

}

Sorry, I tend to use up many variables coz I hate losing focus when programming like thinking if I could reuse a variable :)
I hope someone can help me fix this problem. Im working on 12 sorting procedures and this is my 7th and It ate up too much of my time :(

[LB]

Would you explain what you mean by "the sorting is unsuccessful"? Does it make your GPU overheat? Does it install Norton? Does it email insults to your best friend? You need to be more descriptive ;)

migzicat wrote:

Sorry, I tend to use up many variables coz I hate losing focus when programming like thinking if I could reuse a variable :)

It is good practice not to use a variable for different purposes, however in your case you are writing this code like it is C99 strict some old C code - there is no need to declare all the variables at the start like that, just declare them as needed when they are needed - that is the C++ way.

[cire]

L B wrote:

however in your case you are writing this code like it is C99 strict

http://stackoverflow.com/a/2321622/1708463

*cough*

[LB]

I don't know my C revisions :p I just know one of them was like that.

[Duthomhas]

I'm not really sure what you are doing here...

You are overloading the use of variables (using them for more than one meaning) -- and they have useless names.

The concept of a pivot is the most difficult to understand in a quicksort -- I think that is part of your problem.

You are using an auxiliary array for something -- you don't need it.

You are implementing "passes" over the array. Quicksort doesn't work that way.

I hate to say it, but you need a fresh start. Throw that code away and try again. This FAQ should help you a lot.
http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/quicksort/

Don't worry about any fancy pivot choice stuff -- just pick the first element. The pivot value is the value of the indexed element. For example, given

    4 6 2 1 5 7 3

choose the first element as pivot. It's value is '4'. Now shuffle all the stuff in the rest of the array so that elements less than four come before elements greater than four.

    4 3 2 1 5 7 6
     less ^ greater    (the caret is at the last of the less, where the indices crossed)

Swap the 4 into the correct spot. (It is now properly sorted.)

    1 3 2 4 5 7 6
     less ^ greater    (now the caret is indexing the sorted piece of the array)

Now you need to call the function again (yes, this should all be in a function), but this time only sorting the less and greater parts.

    1 3 2 4 5 7 6

Recurse once for each side.

    1 2 3 4 5 7 6     (less side sorted)
    1 2 3 4 5 6 7     (greater side sorted)


Since that is a simplistic example, here is one more for you to consider:

6 2 1 4 5 7 3

6 2 1 4 5 3 7    select pivot and partition, finding last of "less thans"
          ^

3 2 1 4 5 6 7    6 is now in the sorted spot. We will not try sorting it again.

3 2 1 4 5 6 7    We'll sort the less than 6s

3 2 1 4 5        Select pivot and partition, finding last of "less thans"
    ^

1 2 3 4 5 6 7    3 is now in its final, sorted spot

1 2 3 4 5 6 7    We'll sort the less than 3s

(done)

1 2 3 4 5 6 7    We'll sort the greater than 3s

(done)

1 2 3 4 5 6 7    Now that the less than 6s are done, we'll sort the greater than 6s

(there's only one element, so it is already sorted)

1 2 3 4 5 6 7    Done.


Hope this helps.

[migzicat]

Thanks :) That helped alot.
I guess the quick sort I understood from youtube was wrong lol. Although it really do sort the elements :)

[migzicat]

is there a sorting procedure like that?
It works like this:
given
7, 5, 1, 4, 3, 2, 6
there's the index x and y.
index x is set on the first element given the condition that it hasn't been the first element; and I called that element the [i]main[/i element since every pass the main element is placed in its right position.
index y is then set on the last element.

7 5 1 4 3 2 6
x..............y
then every round, it checks if the element at index x is greater than the element in index y. If it is, they will swap places. The index of the main element will not move so,

6 5 1 4 3 2 7
x............y
2 5 1 4 3 6 7
...x.........y

2 5 1 4 3 6 1
.....x.......y

2 5 1 4 3 6 1
........x....y

2 5 1 4 3 6 1
...........x.y

and each pass will stop if index y and x are equal
2 5 1 4 3 6 1
.............x
.............y

then the element 6 will be added to a new array for elements which has been a main element so that if the first element has been sorted already (and its really placed there), the index x will move to the next element.
Then it repeats the process until all are sorted.

Well its not quick sort but I wonder what sorting procedure's that. lol

[Duthomhas]

Such a sort wouldn't work the way you think.

(It is a cross between bubble and a selection sorts.)

I'm currently working on the sorting algorithms part of the FAQ.
http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/

The only major one not in there yet is radix sorting methods.
(Unless someone on the forum thinks I have missed an important sorting method.)