Determine number of steps in sorting algorithms

• Download SortingSteps - 53.22 KB

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.