Sorting Algoritthms Part 2

                

          What is Sorting?  & Bubble Sort Algorithm:

  Sorting Algorithms Part 1

        Suppose, you have to arrange books on your bookshelf. There is a number of ways to arranging it. Here we consider arranging the order of Books by their number of pages.

Selection Sort

                One way to do it by taking the book with the highest number of pages and put it into Bookshelf. And now from the remaining books choose another book which is having the highest number of pages and put it in bookshelf by side of book which is already there. Repeat this process until there is no book on the bookshelf. In Computer Science, this method called “Selection Sort”.

Insertion Sort

               

                            Another way to arranging books in Bookshelf is to take any random book and put it on the bookshelf. And now from the remaining books take any random book and put it into bookshelf according to pages it has comparison to books already into the bookshelf. Suppose you have 250 pages books to put it into bookshelf & there are already three books having 100,200 and 500 pages respectively.  Now you first check 500 pages book which have the greater number of pages than the book you want to put (250 pages), So you check next book of 200 pages which is having less number of pages than the book you want to put (250 pages). Here you found the correct position of 250 pages Books, Because if you put it in this position bookshelf look like this: 100, 200, 250, 500 pages books respectively and this is correct according to order by the number of pages. By repeating this process until all the books will be put into the bookshelf, We have the bookshelf with books order by pages they have. In computer science this method of sorting called “Insertion Sort”.

               



             Sorting of Integers demonstrated by C/C++ code in both Sort and Insertion Sort.

	/*Insertion Sort Function
	Time Complexity : O(N^2)
	Space Complexity : O(1)
	*/
	void Insertion_Sort(int data_array[],int SizeOf_data_array)
	{
	int IntegerToBeInsert;
	//loop for insert all the integers in ascending order
	//this loop start with second element because One element is already sorted
	for(int i=1;i<SizeOf_data_array;i++)
	{
	//Integer which is perform as key to be inserted
	IntegerToBeInsert = data_array[i];
	int j=i-1;
	//Traverse array from end of array to correct postion
	// ANd shifting of elements to make postion
	while(j>=0 && data_array[j]>IntegerToBeInsert)
	{
	data_array[j+1]=data_array[j];
	j--;
	}
	//Insert element @ correct Position
	data_array[j+1]=IntegerToBeInsert;
	}
	}

view raw Insertion_Sort.cpp hosted with ❤ by GitHub

	/*Selection Sort Function
	Time Complexity : O(N^2)
	Space Complexity : O(1)
	*/
	void Selection_Sort(int data_array[],int SizeOf_data_array)
	{
	int tmp;
	//find MAX from existing array
	//swap it until it moves to last position in array
	for(int i=0;i<SizeOf_data_array-1;i++)
	for(int j=i+1;j<SizeOf_data_array;j++)
	if(data_array[i]>data_array[j])
	{
	tmp=data_array[i];
	data_array[i]=data_array[j];
	data_array[j]=tmp;
	}
	}

view raw Selection_Sort.cpp hosted with ❤ by GitHub