MERGE SORT
Description
Merge sort is built upon the concept
of merging. Merging takes two (already sorted) lists and produces a new output
list containing all of the items from both lists in sorted order
Merge sort is an O(n log n) comparison-based sorting algorithm. Most implementations produce a stable sort, meaning that the
implementation preserves the input order of equal elements in the sorted
output. It is a divide and conquer algorithm. Merge sort was invented
by John von Neumann in 1945. A detailed description and analysis of bottom-up merge
sort appeared in a report by Goldstine and Neumann as early as 1948.
Application
Evaluation
The
process of merge sort describes
more of a combine-and-conquer technique. The process starts by dividing into two-element
array and each pair is sorted. Then, two element array became four element
array and each value in each set of array is compared and sorted. Lastly, ‘yung
four element array will be written in a single list and compare each element
and sort.
Worst
case ng merge sort? Kapag ung elements is nasa descending order.
SHELL SORT
Description
The
Shell sort, one of the eldest sorting algorithms, is published by and named
after Donald L. Shell. It was published on 1959. Some old references named this
sorting algorithm as Shell-Metzner which is named after Marlene Metzner Norton
but according to her, her name should not attach to it because she had no any
contribution to it.
The principle of Shell sort
algorithm is to arrange the data in a two-dimensional array (which is
represented by rows and columns) and sorts the column of the array using
insertion sort.
Shell sorts requires asymptotically
fewer than O(n2) comparisons.
It is built upon the concept of h-sorting and uses the increment sequence h1,
h2, h3… It improves insertion sort by comparing elements
separated by a gap. It allows an element to take bigger steps towards its
expected position. Multiple passes over the elements are taken with smaller to
smallest gap sizes. When the gap reaches one, the last step to be done is to do
a plain insertion sort, guaranteeing that the final list is sorted. The
efficiency of using this kind of sorting algorithm is you don’t have to compare
element with other in one position at a time which is efficient in sorting
medium size of list. Shell sort is faster than insertion sort but somewhat
slower than quick sort if we are going to sort a large number of data.
Application
Evaluation
It
is stated in the previous pages that shell sort improves insertion sort which
is true because in insertion sort, we have to compare an element before it at
kung nasa reverse order ito, we swap them. Paulit- ulit na gagawin ‘yung step
until the array is sorted kung kaya more comparisons and exchanges of position
ang mangyayari. Unlike in Shell sort, the element will take giant steps towards
its final position.
The process
of sorting using shell sort starts by
dividing the length of an array by two which also means that it starts with a
large value of h or gap, kaya magkakaroon ng sublist na iso-sort. Once the
sublist is sorted, we write them in a single list. Then, the value of h will
become smaller as it is divided by two again and there would be another sublist
to be sorted. This process will be done for several times hanggang maging one
ang gap wherein the list is nearly sorted and we only have to sort in using
insertion sort.
In our own analysis, the best case of shell sort is,
of course, when the list is almost sorted while it is on worst case if the list
is arranged in descending order wherein
sa final list na one na lang ang gap, mas maraming number ang kailangan i-sort
using insertion sort.
Comparison
of Merge Sort and Shell Sort
Merge
sort and shell sort are both sorting algorithms. Which is best?
Mas
maganda gamitin ang merge sort. Kung titingnan sa example, mas madaling na-sort
ang unsorted array gamit ang merge sort kaysa sa shell sort algorithm. J
Reference(s)
Wrox.(November
2005)Beginning Algorithms.eBook
adferaer-200910770
laaquino-200911909
pwede bang i-arrange ang list using shellsort into descending order??
TumugonBurahin