C++ DONT COPY AND PASTE FROM ANOTHER PROGRAM The insertion sort algorithm is a m

Question

C++

DONT COPY AND PASTE FROM ANOTHER PROGRAM

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%u2019re finished after you insert the value in the last element. Follow the algorithm below to insert the next value in an array.

ALGORITHM FOR INSERTING THE NEXT VALUE

1.      Save the value to be inserted in newValue.

2.      Using a loop, compare newValue to the elements already inserted in the array starting with the last one inserted. If an element is larger than newValue, shift it to the next array element. Exit the loop when a value that is not larger than newValue is reached.

3.      Insert newValue at the initial position of the last element that was shifted.

Use the following set of values to fill your array. Write your sorting algorithm as a function. Write a test program which fills an array with the unsorted values, prints the unsorted array, calls the sorting function, and prints the sorted array.

ARRAY VALUES TO SORT:

3 47 45 27 21 9 36 33 8 5 41 26 20 37 6 11 44 42 32 28

_________________________________________________________________________________

(Repeat this section for each of your functions). Provide the function prototype here.

Function Algorithm:

Explanation / Answer

please rate - thanks

#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 C
• Subjects

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