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;
	
}
}

Recommended Answers

All 2 Replies

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
}

@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...

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.