Write a program to implement scan sort for contiguous lists

Assignment Help Computer Engineering

Reference no: EM131847619

Problem

There is an even easier sorting method, which, instead of using two pointers to scan sort move through the list, uses only one. We can call it scan sort, and it proceeds by starting at one end and moving forward, comparing adjacent pairs of keys, until it finds a pair out of order. It then swaps this pair of entries and starts moving the other way, continuing to swap pairs until it finds a pair in the correct order. At this point it knows that it has moved the one entry as far back as necessary, so that the first part of the list is sorted, but, unlike insertion sort, it has forgotten how far forward has been sorted, so it simply reverses direction and sorts forward again, looking for a pair out of order. When it reaches the far end of the list, then it is finished.

(a) Write a C++ program to implement scan sort for contiguous lists. Your program should use only one position variable (other than the list's count member), one variable of type entry to be used in making swaps, and no other local variables.

(b) Compare the timings for your program with those of insertion_sort.

Reference no: EM131847619

Questions Cloud

Develop a teaching plan for the parents : Develop a teaching plan for the parents of an active toddler addressing safety measures and parent education to prevent accidental poisoning

Write a cpp function for bubble sort : Write a C++ function for bubble sort. Find the performance of bubble sort on various kinds of lists, and compare the results with those for insertion sort.

Why might a healthcare professional use an abbreviation : Why might a healthcare professional use an abbreviation that is on the "Do Not Use" List or the Error-Prone List?

Provide an example of how levis could use the technology : Explain RFID and provide an example of how Levi's could use the technology to increase its business operations.

Write a program to implement scan sort for contiguous lists : Write a C++ program to implement scan sort for contiguous lists. Your program should use only one position variable, one variable of type entry to be used.

Effective use of medications : Medication labels provide information that is critical to the effective use of medications. What are the types of information

Determine the frequency of drug administration : Determine the frequency of drug administration based on the half-life. Determine how long it would take for the drug to be cleared from the body

Research dells supply chain management strategy : Research Dell's supply chain management strategy on the Web and create a report discussing any new SCM updates and strategies.

What initial order for list of keys will produce worst case : What initial order for a list of keys will produce the worst case for insertion sort in the contiguous version? In the linked version?

User Account

All Pages