Module 7 - Sorting Part 1 Here is your practical application of data structures;

Question

Module 7 - Sorting Part 1

Here is your practical application of data structures; sorting. There are literally hundreds of sorting algorithms and Topic - Sorting Techniques covers most of the important ones. Sorting is also tied very closely to searching, as it is much easier to search a sorted list.

Assignment

We are going to return to your Chain and Links code from Module 3 - Lists ( https://www.chegg.com/homework-help/questions-and-answers/module-3-lists-lists-one-fundamental-data-types-ability-understand-lists-abstract-data-typ-q8223831 for reference) . You will need to fork your JSFiddle into a new Fiddle. In this Fiddle we are going to add a Chain function - Sort(). I would like you to add 2 sort functions, you can use any sort method that you desire for each of the sort functions. You can also delineate the functions by the name of the Sort function - so your functions might be QuickSort() and MergeSort() - if you chose to implement those 2 algorithms.

Once the Chain is sorted - we want to keep it sorted. You have a couple of ways to do that; (1) insert elements into the correct location in the Chain based on sort order or (2) re-sort the chain after every insertion. If you choose (2) you will need to pick an algorithm that is highly efficient for a pre-sorted array with one item out of place (look at all the algorithms - it is there).

You will now need an interface to add Links to your chain. Just create either a text box and a button or a button and any type of input. I should be able to add elements to your chain and see the new chain output each time I add an element.

Explanation / Answer

As the link for the previous module has been given above I assume that the creation of link part has been done already.Now what I will do is add the sort module into the existing code which will sort out the elements in the linked list.

The sort function is as follows:-

/* The function called is the sort function and the value passed as an argument are
The entire array(Assuming that the entire chain is stored as an array) and low and high value */

var swap = functionChain(Sort, lo, hi) {
var loValue = Sort[lo];
Sort[lo] = Sort[hi];
Sort[hi] = loValue;
};

/*The quickSort function is based on the partitioning the element in the 2 parts
And then declaring them as the higher part and the lower part based on the chosen pivot element. */

var partition = functionChain(Sort, lo, hi)
{
var pivot = Sort[Math.floor((lo + hi) / 2)];
/* The pivot elelemnt is calculated and the sort function is called on the divided part,
i.w high part or the low part based on the condition */

while (lo <= hi){
while (Sort[lo] < pivot) { lo++; }
while (Sort[hi] > pivot) { hi--; }

if (lo <= hi) {
swap(Sort, lo, hi);
lo++;
hi--;
}
}
return lo;
};

var quickSort = functionChain(Sort, lo, hi) {
var index = partition(Sort, lo, hi);

if (lo < index -1) {
quickSort(Sort, lo, index - 1);
}
if (index < hi) {
quickSort(Sort, index, hi);
}
};

This sort function also must be called after the new node have been inserted in the list.Because when the new node is inserted in the list it always creates the unordered list and hence the sorting is required in this case.

This is all what I came across the question.

Not sure where to add the interface for this.

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

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