Problem The insertion sort algorithm is a more efficient means of sorting an arr

Question

Problem 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

An O(n2) sorting algorithm which moves elements one at a time into the correct position. The algorithm consists of inserting one element at a time into the previously sorted part of the array, moving higher ranked elements up as necessary. To start off, the first (or smallest, or any arbitrary) element of the unsorted array is considered to be the sorted part. Although insertion sort is an O(n2) algorithm, its simplicity, low overhead, good locality of reference and efficiency make it a good choice in two cases (i) small n, (ii) as the final finishing-off algorithm for O(n logn) algorithms such as mergesort and quicksort. The algorithm is as follows (from wikipedia): function insertionSort(array A) for i from 1 to length[A]-1 do value := A[i] j := i-1 while j >= 0 and A[j] > value do A[j+1] := A[j] j := j-1 done A[j+1] = value done Writing the algorithm for integers will suffice. #include #include #include #define ASIZE 25 #define SCALE 100 using namespace std; void fillarray(int a[], int n); void sortarray(int a[], int n); void printarray(int a[], int n); void initialize(int a[]); int getrandom(int use[]); int main() { int size=ASIZE; /* SIZE FOR ARRAY */ int array[size]; /* ARRAY OF DATA */ fillarray(array, size); printarray(array, size); sortarray(array, size); printarray(array, size); return 0; } /* SORT ARRAY OF SIZE N */ void sortarray(int a[], int n) { int r, s, t; /* LOOP ITERATERS */ int tmp; /* FOR SWAPPING */ for (r=n/2; r>0; r/=2) { for (s=r; s=r && tmp

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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