PLEASE help!! Thank you. The insertion sort algorithm is a more efficient means

Question

PLEASE help!! Thank you.

The insertion sort algorithm is a more efficient means of sorting an array than the selection sort. This algorithm is analogous to the procedure that card players follow when picking up cards and inserting them in their hand to form a run in a particular suit. A player makes room for a new card by shifting over the ones that follow it and then inserting it where it belongs in the hand. In sorting an array, all values are available when you begin, but you can assume that the array is not sorted and start by inserting the value currently in the second array element by comparing it to the first element. This gives you a sorted subarray consisting of the first two elements. Next, you insert the value currently in the third array element where it belongs compared to the first two, which gives you a sorted subarray of three elements, and so on. You

Explanation / Answer

#include <iostream>
using namespace std;
void insertionSort(int[],int);
void print(int[],int);
int main()
{int array[100];
int i,length=0,value,n;
cout<<"enter numbers to sort (-999 as sentinel) ";
cout<<"Enter number "<<length+1<<": ";
cin>>array[length];
while(array[length]!=-999)
    {length++;
      cout<<"Enter number "<<length+1<<": ";
      cin>>array[length];
      }

cout<<"Initial unsorted array ";
print(array,length);
insertionSort(array,length);
cout<<" final sorted array ";
print(array,length);
cout<<endl;
system("pause");
return 0;
}
void print(int array[],int length)
{int i;
for(i=0;i<length;i++)
     cout<<array[i]<<" ";
}
void insertionSort( int array[],int length)
{int i,j,n;
     for(j=1;j<length;j++)
        {n=array[j];
         for(i=j-1;(i>=0)&&(array[i]>n);i--)
               array[i+1]=array[i];
         array[i+1] =n;   
     }
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.