Click here to Skip to main content
Click here to Skip to main content

Determine number of steps in sorting algorithms

, 16 Feb 2008
Rate this:
Please Sign up or sign in to vote.
Determine number of steps in sorting algorithms

Introduction

This article helps you in determining the number of steps of different sorting algorithm in a simple way.

Background

When you have large amount of data and you have to sort it, multiple algorithms comes into mind with different complexities. Sometimes you need to determine complexity of algorithms.Here, I am assuming the complexity in teems of number of step rather than memory and speed both. I am giving you a simple demonstration for concluding the complexity of sorting algorithm. Here I am demonstrating three sorting algorithms in my application:
1.Heap Sort
2.Radix Sort
3.Shell Sort
I am not going into the details of these algorithms as I am focusing how can you programmaticaly determine the complexity of these algorithms. But if you want to get some prior knowledge on sorting can visit http://en.wikipedia.org/wiki/Sorting_algorithm The flow will start with the MainSort class that will ask for user choice of algorithm. After that, giveany number of elements less than hundred that you want to provide as input and specify those numbers. When you finished giving input , your selected sorting algorithm starts working. Heap sort will display the number of steps after building heap and each pass required to sort. This will clear a beginner guy that how does heap sort works. MaxHeapify() builds max-heap data stuicture. BuildMaxHeap() maintains the total number of elements that should be one less every time the previous number of elements. HeapSort() executes multiple passes and each time build the maximum heap. Same is the case with Radix sort and Shell sort, their complexities for sorting the list in a single pass will be displayed after each pass until the list is sorted.

Using the code

There are three classes that are responsible for the sorting data via each type of algorithm.HSort for sorting data through Heapsort, RSort for Radix Sort and ShellSort for sorting data through Shell sort.

This class sort data through Heap sort algorithm

<p>
class HSort
{
	private int[] a = new int[100];
	
	private int temp;
	private int HeapSize;
	private int nElements;
	private int nSteps;
	private int totalnSteps;

	// number of elements in array
	public void MaxHeapify(int i)
	{
		int l, r,largest;
		l=2*i+1;
		r=2*i+2;
	
		if(l<=HeapSize && Check(l,i))
		{
			nSteps++;
			largest=l;
		}
		else
		{
			nSteps++;
			largest=i;
		}


		if(r<=HeapSize && Check(r,largest))
		{
			nSteps++;
			largest=r;
		}
		if(largest!=i)
		{
			temp=a[largest];
			a[largest]=a[i];
			a[i]=temp;
			nSteps+=3;
			MaxHeapify(largest);		
		}
		nSteps+=6;
	}// end of MaxHeapify function

	public bool Check(int l, int r)
	{
		nSteps++;		
		return(a[l]>a[r]);		
	}

	public void BuildMaxHeap()
	{
		HeapSize=nElements-1;
		nSteps++;
		for(int i=nElements/2-1;i>=0;i--)
		{
			nSteps++;
			MaxHeapify(i);
		}
	}//end method
  
	public void HeapSort()
	{
		int passno,j;
		BuildMaxHeap();
		Console.WriteLine( "" );
		Console.WriteLine( "-----------------------" );
		Console.WriteLine("Elements of Max Heap are" );
		Console.WriteLine( "-----------------------" );
		DisplayElements();
		Console.WriteLine( "" );
		Console.WriteLine( "----------------------------------" );
		Console.WriteLine("No. of steps after buliding heap {0} ",nSteps );
		Console.WriteLine( "----------------------------------" );

		for(j=nElements-1,passno=1 ; j>0 ; j--,passno++)	//Each pass starts here
		{
			nSteps=0;
			temp=a[0];
			a[0]=a[j];
			a[j]=temp;
			HeapSize--;
			MaxHeapify(0);
			nSteps+=7;
			Console.WriteLine( "" );
			Console.WriteLine( "--------------------------------" );
			Console.WriteLine("Elements of array after pass {0}",passno);
			Console.WriteLine( "--------------------------------" );
			DisplayElements();
			Console.WriteLine( "" );
			Console.WriteLine( "-------------------------------" );
			Console.WriteLine("No. of steps {0} after pass {1} ",nSteps,passno );
			Console.WriteLine( "-------------------------------" );
			Console.WriteLine("Press return for the next pass");
			Console.ReadLine();
			totalnSteps+=nSteps;
		}//end of loop
		
		Console.WriteLine( "" );
		Console.WriteLine( "----------------------------" );
		Console.WriteLine("Total number of passes are: " + (passno-1));
		Console.WriteLine("Total number of steps are: " + totalnSteps);
		Console.WriteLine( "----------------------------" );
	}//end method

	public void SetArray()
	{
		Console.WriteLine( "" );
		Console.WriteLine("----------------------------------------------" );
		Console.Write( "Number of elements in the array (less than 100) : " );
		string str = Console.ReadLine();
		nElements = Int32.Parse(str);

		Console.WriteLine( "" );
		Console.WriteLine( "-----------------------" );
		Console.WriteLine( " Enter array elements  " );
		Console.WriteLine( "-----------------------" );
		// Get array elements
		for( int i = 0; i<nElements; i++ )
		{
			Console.Write("Element no {0}:", i+1 );
			str = Console.ReadLine();
			a[i] = Int32.Parse(str);
		}
	}
}
NOTE : For displaying items, method is not included in the above code snippet. However, it is available in the uploaded project.
</p>		

Points of Interest

I face this problem while I was studying Algorithm Analysis course during my graduation. I was in trouble that how can we determine the executions steps that's why I put simply counter for determining the number of steps. Apparently this seems to be a simple counter but its true that its one approach to determine the complexity in terms of time.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

A. Raees
Web Developer
Pakistan Pakistan
No Biography provided

Comments and Discussions

 
GeneralBasic algorithm study Pinmemberdvhh17-Feb-08 7:48 
Usually the number of steps in an algorithm is refered as algorithm complexity
usually designated as O(op n), n is a variable that depend on the number of element.
this complexity can usually be know by using a pseudo code.
 
basic sorting algorithm and their complexity can be found at
http://en.wikipedia.org/wiki/Sorting_algorithm
 
the adverage and worst complexity are good metrics that can rarely be calculated in automated test.
 
plus I found that the number of step in managed code is not a good metric for execution speed.
GeneralRe: Basic algorithm study PinmemberA. Raees17-Feb-08 8:10 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web02 | 2.8.140826.1 | Last Updated 16 Feb 2008
Article Copyright 2008 by A. Raees
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid