Background for Problem1: A simple insertion sort generates a sorted list from va

Question

Background for Problem1:
A simple insertion sort generates a sorted list from values being input sequentially by finding the
appropriate place in the list where each new entry belongs as it arrives. The list will then be opened
up at that place to make room for the new entry by moving the rest of the list 'up' and the new entry
will be copied there. A defect of this approach is that when the list gets long, a large amount of data
may have to be moved up to add a single new word if that word belongs near the beginning of the list.
Problem1: simpleinsert_main.c, simpleinsert_functions, Makefile
Write a C program which uses a simple insertion sort to process the contents of the attached
'words2.zip' file and place the words it contains in a new list in order of increasing length. Save the
new list back to disk as simpleinsert_words.txt . Do not define static arrays or use array notation in
your program - this is a problem in using pointers and 'malloc()'.
* * *

Background for Problem2:
An indirect insertion sort improves slightly on the simple insertion sort by appending the input words
into a character array in arrival order, and at the same time building a secondary array of pointers to
the words using an insertion sort for the pointers. Pointers in the secondary array will still have to
moved aside to make room for each new inserted pointer, but we will benefit from this approach if the
average string length including the string terminator '' is greater than 4 characters (why?).
Problem2: indirectinsert_main.c, indirectinsert_functions, Makefile
Write a C program which uses an indirect insertion sort to process the contents of the attached
'words2.zip' file and place the words it contains in a new list in order of increasing length. Save the
new list back to disk as indirectinsert_words.txt . Do not define static arrays or use array notation in
your program - this is a problem in using pointers and 'malloc()'.
* * *

Background for Problem3:
A third method also uses pointers to words which are stored in arrival order, but changes the data
structure where the pointers are stored from an array to two stacks of pointers to words. In this
method, when a new word is to be added it is compared to words whose pointers are at the 'top' of
the two stacks, then values are moved between those stacks ('popped' and 'pushed') until the new
value lies between the values of the two tops, where the new pointer is pushed.
Problem3: stackinsert_main.c, stackinsert_functions, Makefile
Write a C program which uses an stack insertion sort to process the contents of the attached
'words2.zip' file and place the words it contains in a new list in order of increasing length. Save the
new list back to disk as stackinsert_words.txt . Do not define static arrays or use array notation in your
program - this is a problem in using pointers and 'malloc()'.
* * *

Background for Problem4:
The fourth method is not an insertion sort but will instead use magic (actually Quicksort) to rearrange a
list of pointers to words from arrival order to sorted order.
Problem4: Quick_main.c, Quick_functions, Makefile
Write a C program which uses the quicksort function qsort() to process the contents of the attached
'words2.zip' file and place the words it contains in a new list in order of increasing length. Save the
new list back to disk as Quick_words.txt . Do not define static arrays or use array notation in your
program - this is a problem in using pointers and 'malloc()'.

Explanation / Answer

Simple Insertion sort:
void insertion_sort (int arr[], int length){
      int j, temp;
      
   for (int i = i; i < length; i++){
       j = i;
      
       while (j > 0 && arr[j] < arr[j-1]){
           temp = arr[j];
           arr[j] = arr[j-1];
           arr[j-1] = temp;
           j--;
           }
       }
}

On the other hand,Indirect insertion sorting:
Sometimes, we need to sort large structures or objects by a certain key.
payroll records, with each record consisting of a name, address, phone number, financial information such as salary, and tax information.
sort this information by one particular field, such as the name or employee number.
The fundamental operation in comparison sorts is the swap ?swapping two structures can be a very expensive operation,
A practical solution is to have the input array contain pointers to the structures. Sort by comparing the keys the pointers point to, swapping only pointers when necessary.

Create an array of pointers (p)

Initially p[i] must point to the object stored in a[i]

Rearrange the pointers to sort the array (Don

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

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