A sorting algorithm is
an algorithm that puts elements of a list in a certain order.
1. Bubble sort in java: Also
referred to as sinking sort, is a simple sorting algorithm that works by
repeatedly stepping through the list to be sorted,
comparing each pair of adjacent items and swapping them if they are in the
wrong order. The pass through the list is repeated until no swaps are
needed, which indicates that the list is sorted. Because it only uses
comparisons to operate on elements, it is a comparison sort. Although the
algorithm is simple, most of the other sorting algorithms are more efficient
for large lists.
2.The selection sort is
a combination of searching and sorting. During
each pass, the unsorted element with the smallest (or largest) value is moved
to its proper position in the array. The number of times the sort passes
through the array is one less than the number of items in the array. In the
selection sort, the inner loop finds the next smallest (or largest) value and
the outer loop places that value into its proper location.
3.Insertion sort is a simple sorting
algorithm; it builds the final sorted array one item at a time. It is very
efficient for small data sets. Insertion
sort iterates through the list by consuming one input element at each
repetition, and growing a sorted output list. On a repetition, insertion
sort removes one element from the input data, finds the location it belongs
within the sorted list, and inserts it there. It repeats until no input elements
remain.
The worst case input is
an array sorted in reverse order. The set of all worst case inputs consists of
all arrays where each element is the smallest or second-smallest of the
elements before it. In these cases, every iteration of the inner loop will scan
and shift the entire sorted subsection of the array before inserting the next
element.
4. Quicksort or partition-exchange sort is
a fast sorting algorithm, which is using divide and conquer algorithm.
Quicksort first divides a large list into two smaller sub-lists: the low
elements and the high elements. Quicksort can then recursively sort the
sub-lists.
Steps to implement Quick
sort:
1) Choose an element, called pivot, from the list. Generally
pivot can be the middle index element.https://draft.blogger.com/blogger.g?blogID=1969101077783593325
- promote
2) Reorder the list so
that all elements with values less than the pivot come before the pivot, while
all elements with values greater than the pivot come after it (equal values can
go either way).
3) Recursively apply the
above steps to the sub-list of elements with smaller values and separate the
sub-list of elements with greater values.
5.Merge sort is a divide and conquer algorithm.
Steps to implement Merge
Sort:
1) Divide the unsorted array into n partitions, each partition contains 1 element. Here the one element is considered as sorted.
1) Divide the unsorted array into n partitions, each partition contains 1 element. Here the one element is considered as sorted.
2) Repeatedly merge
partitioned units to produce new sub lists until there is only 1 sub list
remaining. This will be the sorted list at the end.
Merge sort is a fast,
stable sorting routine with guaranteed O(n*log(n)) efficiency. When sorting
arrays, merge sort requires additional scratch space proportional to the size
of the input array. Merge sort is relatively simple to code and offers
performance typically only slightly below that of quicksort.
No comments:
Post a Comment