0

I am having trouble figuring out what the recursive function does in the insert sort. Wouldn't the recursive line block the rest of the code from working. I am just looking for a quick explanation.

void insertion_sort-recur(int a[], int n){
	if(n<=1)
		return;
	insertion-sort_recur(a, n-1);//how does this line work
	temp=a[n-1];
	for(int i=n-2; i>=0 && temp<a[i];i--){
		a[i+1]=a[i];
}	a[i+1]=temp;
	
}
}
3
Contributors
2
Replies
6
Views
7 Years
Discussion Span
Last Post by firstPerson
0

If I'm reading it correctly, it's using a recursion to perform the insert operation after it finds the sorted location of the first unsorted element. It takes the place of this part of the algorithm:

if (m_DataSet[unsorted] < m_DataSet[destination]) { //if the unsorted element should be before the destination element
  dataType temp = m_DataSet[unsorted];              //make a temporary copy of the unsorted element
  for (int slide = unsorted; slide > destination; --slide) { //slide the elements down to make room for the insert
    m_DataSet[slide] = m_DataSet[slide-1];
  } //end for loop slide
  m_DataSet[destination] = temp;                    //insert the unsorted element at its sorted location
}

Edited by Fbody: n/a

1

@OP: Forget you ever saw that code. Its useless.This insertion-sort_recur(a, n-1);//how does this line work acts like a for loop. It keeps going until it reaches the second element. Then it returns to the third element. Then to the fourth and so on...

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.