[Oren131]

i sat on this like a week and didnt succeed
is someone here have or knows of a site that has the code to iterative QuicSort using stack(prefer c++ if have)
i need it urgely so if someone could really help me i would so be gratfull for him

[janotte]

Why did you sit on it?
Works for eggs but not for software.

Read these and then show us your best effort so far
http://en.wikipedia.org/wiki/Quicksort
http://www.algolist....rting/Quicksort
http://www.iti.fh-fl...ick/quicken.htm

[Oren131]

i did seat on it man for a week and didnt succeed unfourchanly, if u can help me please please do
i dont want to do this course again just because of one program i didnt succeed, after last year i left the course in the middle just to recure from cancer.
i dot usually do that but in this program i have to get more then 60 in order to get a change to be tested

i need a code that uses stack/

[janotte]

You need to show us your code and answer these questions about it
( a ) Does your code compile?
( b ) Any errors or warnings? If there are then share them with us.
Copy and paste the errors exactly as they are.
( c ) Is the program producing any output?
( d ) How is the actual output different to what you want / expect?
Give details and, ideally, examples.
If you provided inputs to the program tell us what they were.
( e ) What have you already tried to fix it?

If you keep asking for code to be given to you then the Mods will sweep your thread away (effectively, you will fail at posting on DIC).

So 'show us the code'.

EDIT
I see you have a Forum Leader helping you now so I am out off here.
Good luck and happy coding.

This post has been edited by janotte: 25 December 2010 - 04:45 PM

[Oren131]

u want me to send u by mail my code?
or upload it here?

[ishkabible]

you need to post you code in code tags in this thread.
watch this, read this and always remember to post code between code tags like so
always post code in thread so everyone can see it and help you. please read the rules before posting as well.

[Oren131]

typedef int ItemType;

class ARRAY
{
	ItemType *arr;
	int size;

public:

	ARRAY();
	void init();
	void print();
	ItemType*  get_arr();
	int 	   get_size();
	~ARRAY();

};

#endif

///////////////////////////

#include "array.h"
#include <iostream>
using namespace std;


ARRAY::ARRAY()
{
	cout <<"Plese enter the size of your array :" << endl;
	cin  >> size;

	arr=new ItemType [size];
	if(!arr)
		throw "Allocation of the array fail.";

}

void ARRAY::init()
{
	cout << "Please, enter the numbers: " << endl;
		for (int i = 0; i < size; i++)
			cin >> arr[i];

}


void ARRAY::print()
{

	for (int i = 0; i < size; i++)
		cout << arr[i] <<" " ;

	cout <<endl;
}


ItemType* ARRAY:: get_arr()
{
	return arr;
}

int ARRAY:: get_size()
{
	return size;
}



ARRAY::~ARRAY()
{
	delete []arr;
}

//////////////////////////

#ifndef NODE_H
#define NODE_H

#include "stack.h"
#include "array.h"

class Node
{
	ItemType data;
	Node* next;

	public:
	//constructor & distructors
		Node(ItemType d = 0);
		Node(Node& obj);//Copy CTOR
		~Node();

	//methods and functions
		void Setdata(ItemType s);
		void SetNext(Node* p);
		ItemType GetData();
		Node* GetNext();

};



#endif

//////////////////////

#include "node.h"


Node::Node(ItemType d):data(d), next(NULL){} //default c'tor

Node::Node(Node& obj)   //copy c'tor
{
	data = obj.data;
	next = obj.next;
}
Node::~Node()    //d'tor
{
	delete next;
}

void Node::Setdata(ItemType d)
{
	data = d;
}

void Node::SetNext(Node* p)
{
	next = p;
}

ItemType Node::GetData()
{
	return data;
}

Node* Node::GetNext()
{
	return next;
}
//////////////////////////////

#ifndef STACK_H
#define STACK_H

#include <iostream>
#include "node.h"
#include "array.h"

using namespace std;

class Node;

class stack
{
	Node *top;

	public:
	//constructor & distructors
		stack();
		~stack();

    //methods and functions
		void MakeEmpty();
		int IsEmpty();
		void Push(ItemType obj);
		ItemType Pop();
		ItemType Top();
};
#endif

///////////////////////

#include "stack.h"
#include "node.h"

stack::stack() {top = NULL;}

stack::~stack()
{
	MakeEmpty();
}

int stack::IsEmpty()
{
	if(top == NULL)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}

void stack::MakeEmpty()
{
	Node* temp;
	while(top != NULL)
	{
		temp = top;
		top = top->GetNext();
		delete temp;
	}
}

void stack::Push(ItemType obj)
{
	Node* temp = new Node(obj);
	if(!temp)
	{
		throw "allocation fail";
		exit(1);
	}
	temp->SetNext(top);
	top = temp;
}

ItemType stack::Pop()
{

	Node* temp = top;
	ItemType item = top->GetData();
	top = top->GetNext();
	temp->SetNext(NULL);

	delete temp;
	return item;
}

ItemType stack::Top()
{

	ItemType item = top->GetData();
	return  item;
}
//////////////////////

#ifndef _QUICKSORT_H_
#define _QUICKSORT_H_


#include "stack.h"
#include "node.h"


class QuickSort
{
	public:

    ////methods and functions
		friend void swap(ItemType& x, ItemType& y);
		int Partition(ItemType arr[], int left, int right);
		void QuickSort_Rec(ItemType arr[], int left, int right);
		void QuickSort_Iter(ItemType arr[], int left, int right);
};
#endif

/////////////////////

#include "quicksort.h"

void swap(ItemType& x, ItemType& y)
{
	ItemType temp;
	temp = x;
	x = y;
	y = temp;
}

int QuickSort::Partition(ItemType arr[], int left, int right)
{
	bool IsPivotLeft = true;
	int pivot ;

	pivot = arr[left];

	while(left < right)
	{
		if(IsPivotLeft)
		{
			if(pivot > arr[right])
			{
				swap(arr[left], arr[right]);
				left++;
				IsPivotLeft = false;
			}
			else
				right--;
		}
		else
		{
			if(pivot < arr[left])
			{
				swap(arr[left], arr[right]);
				right--;
				IsPivotLeft = true;
			}
			else
				left++;
		}
	}

	return left;

};

void QuickSort::QuickSort_Rec(ItemType arr[], int left, int right)
{
	int pivot;

	if(left < right)
	{
		pivot = Partition(arr, left, right);
		QuickSort_Rec(arr, left, pivot-1);
		QuickSort_Rec(arr, pivot+1, right);
	}

}
void QuickSort::QuickSort_Iter(ItemType arr[], int left, int right)
{
	int pivot = 0, leftBorder = left, rightBorder = right;
	stack s;
	leftBorder = pivot+1;

	while(!s.IsEmpty() || leftBorder < rightBorder)
	{
		if(leftBorder < rightBorder)
		{
			pivot = Partition(arr,leftBorder, rightBorder);
			s.Push(leftBorder);
			s.Push(pivot-1);

			leftBorder = pivot + 1;
		}
		else
		{
			rightBorder = s.Pop();
			leftBorder = s.Pop();

		}
	}
}

///////////////

#include <stdio.h>
#include <iostream>
#include "array.h"
#include "stack.h"
#include "node.h"
#include "quicksort.h"

using namespace std;

int main()
{
	

		try
	{
		QuickSort object;
		ItemType *arr = NULL;
		int size = 0;

		cout << "Starting requrcieve version: " << endl;
		ARRAY arr_for_quicksort_req;
		arr_for_quicksort_req.init();
 		arr = arr_for_quicksort_req.get_arr();
		size = arr_for_quicksort_req.get_size();
		object.QuickSort_Rec(arr, 0, size-1);// left = 0,right = size-1;
 		arr_for_quicksort_req.print();

		cout << "Starting itrative	version: " << endl;
		ARRAY arr_for_quicksort_itr;
		arr_for_quicksort_itr.init();
		arr = arr_for_quicksort_itr.get_arr();
		size = arr_for_quicksort_itr.get_size();
		object.QuickSort_Iter(arr, 0, size-1);
		arr_for_quicksort_itr.print();

	}
	catch(char const *str)
	{
		cout << str << endl;
	}

	return 0;
}

dont know why whe iterative quicksort doesnt work and how to do it from recursive to interative.

This post has been edited by ButchDean: 25 December 2010 - 05:09 PM
Reason for edit:: Please use code tags [code] with [/code].

[Oren131]

please someone help me, after a horrible year of pain(cancer) i just want to try and finish my study, its not fair becuae on HW i wont be able to be tested, just need an iterative quicksort using stack

[Salem_c]

First, comment out the code that works, so you don't have to keep running it for each debug attempt.
Something like this.

#include <stdio.h>
#include <iostream>
#include "array.h"
#include "stack.h"
#include "node.h"
#include "quicksort.h"

using namespace std;

int main()
{
	try
	{
		QuickSort object;
		ItemType *arr = NULL;
		int size = 0;

#ifdef THIS_IS_WORKING
		cout << "Starting requrcieve version: " << endl;
		ARRAY arr_for_quicksort_req;
		arr_for_quicksort_req.init();
 		arr = arr_for_quicksort_req.get_arr();
		size = arr_for_quicksort_req.get_size();
		object.QuickSort_Rec(arr, 0, size-1);// left = 0,right = size-1;
 		arr_for_quicksort_req.print();
#endif

		cout << "Starting itrative	version: " << endl;
		ARRAY arr_for_quicksort_itr;
		arr_for_quicksort_itr.init();
		arr = arr_for_quicksort_itr.get_arr();
		size = arr_for_quicksort_itr.get_size();
		object.QuickSort_Iter(arr, 0, size-1);
		arr_for_quicksort_itr.print();

	}
	catch(char const *str)
	{
		cout << str << endl;
	}

	return 0;
}

Then compile your program for debugging, and use a debugger to trace through where it is going wrong.

$ g++ -g *.cpp
$ gdb ./a.out 
GNU gdb (GDB) 7.1-ubuntu
Copyright (C) 2010 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
and "show warranty" for details.
This GDB was configured as "i486-linux-gnu".
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>...
Reading symbols from /home/sc/work/meh/a.out...done.
(gdb) run
Starting program: /home/sc/work/meh/a.out 
Starting itrative	version: 
Plese enter the size of your array :
1
Please, enter the numbers: 
1

Program received signal SIGSEGV, Segmentation fault.
0x08048f1e in Node::GetData (this=0x0) at node.cpp:28
28		return data;
(gdb) where
#0  0x08048f1e in Node::GetData (this=0x0) at node.cpp:28
#1  0x080493a4 in stack::Pop (this=0xbffff3e0) at stack.cpp:50
#2  0x08049179 in QuickSort::QuickSort_Iter (this=0xbffff42f, arr=0x804c008, left=0, right=0) at quicksort.cpp:78
#3  0x08048d4e in main () at main.cpp:33

Things to note:
1. Start with a really small amount of test data. An array with 1 element is trivially sorted, so it should do nothing. Later on, try with say "1 2" (also sorted), then "2 1" (needs a swap).
2. Look at the stack trace; this=0 is NOT a good thing to see.

Look back through the code to see where the trouble started.
> while(!s.IsEmpty() || leftBorder < rightBorder)
Well the stack is supposed to be empty at the start, and with only one element in the array, the right hand side of the || should be false.
So how did it get into this loop?

> int stack::IsEmpty()
This returns 0 (false) when top == NULL (empty).
First problem, your IsEmpty() is returning the wrong answer!.

Now you do the same thing - run with simple data, find and fix a problem, then repeat.
Build up a picture of what does / does not work.

> please someone help me, after a horrible year of pain(cancer) i just want to try and finish my study
A word of advice - trying to elicit sympathy is likely to be counter productive. Since we can't possibly verify your claims, this looks like one of many dozens of different ruses used by students to try and get free homework out of people ("my dog ate my homework", and variations).
The experienced helpers on forums will have seen many such ploys in the past.

> its not fair becuae on HW i wont be able to be tested
Have you discussed this with your course tutor? Do they know about your medical condition?
Even if your program doesn't actually work, most reasonable colleges will give you some credit for the work you managed to do.