Presentation Sorts

Sorting Algorithms The Following are the famous uses sorts * * * * * * * *

Low level sorts: Bubble Sort Insertion sort Selection Sort Shell Sort High level sorts: Quick Sort Merge Sort Radix Sort Heap Sort

and frequently

Low Level sorts

Bubble sort Rough Ideas: => Stable => But not suitable for high level sort is needed => less memory consumes => Suitable for simple requirement => n*n comparison is needed for all the conditions Pros: Simplicity and ease of implementation. Cons: Horribly inefficient.

Ideas of Bubble sort Bubbling elements with largest value are The moving slowly or bubbling to the top If no exchanges are made during one pass over the data, the data have been sorted and process terminates.

Advantages of Bubble sort One of the primary advantages of the bubble sort is that it is fairly easy to write (about 5 lines of code). It is also fairly easy to understand in terms of a sorting algorithm. Unfortunately, the bubble sort is also a relatively slow algorithm, taking O(n2) to complete sorting and therefore, should not be used on large tables.

Disadvantage of Bubble sort

Disadvantages of this sort are: (i) The use of swap (requiring three assignments) within the inner loop; (ii) The fact that moves are never by more than one position at a time. (Compare selection sort which has no moves in the inner loop and elements may move large distances.)

Insertion sort Rough ideas: => Memory wastage is there => But it is stable => Very adaptive when sort for a nearly sorted array => Consumes low process times => Sorting a reverse sorted array is a worst case Pros: Relatively simple and easy to implement. Cons: Inefficient for large lists.

Ideas of Insertion sort –

The approach of Insertion Sort: It has to pick any value and insert it into its proper place in a sorted sublist Repeat until all values have been inserted

For more detail: Consider the first item to be a sorted sublist (of one item) Insert the second item into the sorted sublist, shifting the first item as needed to make room to insert the new addition Insert the third item into the sorted sublist (of two items), shifting items as necessary Repeat until all values are inserted into their proper positions

Selection sort Rough ideas: => O(n*n) => The selection sort works by selecting the smallest unsorted item remaining in the list, and then swapping it with the item in the next position to be filled. The selection sort has a complexity of O(n2). Pros: Simple and easy to implement. Cons: Inefficient for large lists, so similar to the more efficient insertion sort that the insertion sort should be used in its place.

Shell sort Rough ideas: Nsquare (but fastest in nsquare family ) => Adaptive for almost sorted => Take a quite long time for reverse order values => Taken a lesser time for sorting the most unique values => So we can say it is not stable => Inherits the properties of an insertion sort => Memory wastage is there Pros: Efficient for medium-size lists. Cons: Somewhat complex algorithm, not nearly as efficient as the merge, heap, and quick sorts.

Comparison of low level sorts

High Level sorts

Quick Sort The quick sort algorithm is based on a “divide and conquer” algorithm. – This algorithm compares the data values to a partition element while partitioning into two sub-lists – Then, it recursively sorts the sub-lists on each side of the partition element – The recursion base case is a list containing only 1 element – A very simple choice of the partitioning the element is the first element, but that may not be best. –

Graphical analysis

Quick sort

Worst case of Quick sort Bubble sort faster than Quick sort BUT WHEN ?

Bubble sort quick sort

if most of element of an array are unique ➔ If an array is already sorted ➔ If an array is already sorted in a descending order ➔

The Following are some analisys

Quick sort ------------------real: 59.66 user: 55.30 sys: 1.81 Insertion sort ----------------------real: 0.00 user: 0.00 sys: 0.00

Shell sort ----------------------real: 0.02 user: 0.03 sys: 0.00 HEAP sort ----------------------real: 0.01 user: 0.01 sys: 0.00

Bubble sort ----------------------real: 0.00 user: 0.00 sys: 0.00

Radix Sort Disadvantages The speed of Radix Sort largely depends on the inner basic operations, and if the operations are not efficient enough, Radix Sort can be slower than some other algorithms such as Quick Sort and Merge Sort. These operations include the insert and delete functions of the sublists and the process of isolating the digit you want. If the numbers were all of equal length, but many times, this is not the case. If the numbers are not of the same length, then a test is needed to check for additional digits that need sorting. This can be one of the slowest parts of Radix Sort, and it is one of the hardest to make efficient.

Continues... Radix Sort can also take up more space than other sorting algorithms, since in addition to the array that will be sorted, you need to have a sublist for each of the possible digits or letters. If you are sorting pure English words, you will need at least 26 different sublists, and if you are sorting alphanumeric words or sentences, you will probably need more than 40 sublists in all!

Radix Sort Disadvantages Since Radix Sort depends on the digits orletters, Radix Sort is also much less flexible than other sorts. For every different type of data, Radix Sort needs to be rewritten, and if the sorting order changes, the sort needs to be rewritten again. In short, Radix Sort takes more time to write, and it is very difficult to write a general purpose Radix Sort that can handle all kinds of data. For many programs that need a fast sort, Radix Sort is a good choice. Still, there are faster sorts, which is one reason why Radix Sort is not used as much as some other sorts.

Bucket Sort A bucket sort begins with a single-subscripted array of positive integers to be sorted, and a double-subscripted array of integers with rows subscripted from 0 to 9 and columns subscripted from 0 to n-1 where n is the number of values in the array to be sorted. Each row of the double-subscripted array is referred to as a bucket. ●

Algorithm(Bucket) 1. Each value of the single-subscripted array is placed into a row of the buc ket array based on the value's ones digit. This is called the "distribution pass". 2. Loop through the bucket array row-by-row and copy the values back to the o riginal array. This is called a "gathering pass". 3. Repeat this process for each subsequent digit position (tens, hundreds, th ousands, etc.).

continues... + That the double-subscripted array of the buckets is ten times the size of the in teger array being sorted. This sorting technique provides better performance than a bubble sort, but requires much more memory. + This version of the bucket sort requires copying all the data back to the origin al array on each pass. Another possibility is to create a second double-subscripted bucket array and repeatedly swap the data between the two bucket arrays.

Heap sort The heap sort is the slowest of the O(n log n) sorting algorithms, but unlike the merge and quick sorts it doesn't require massive recursion or multiple arrays to work. This makes it the most effective options for very large data sets of crore values. Pros: In-place and non-recursive, making it a good choice for extremely large data bases. Cons: Slower than the merge and quick sorts.

Graphical analysis

Heap sort

Comparison of high level sorts

Stability We say that a sorting algorithm is stable if, when two records have the same key, they stay in their original order. This property will be important for extending bucket sort to an algorithm that works well when k is large. But first, which of the algorithms we've seen is stable? * Bucket sort? Yes. We add items to the lists Y[i] in order, and concatenating them preserves that order.

Continues... * Heap sort? No. The act of placing objects into a heap (and heapifying them) destroys any initial ordering they might have. * Merge sort? Maybe. It depends on how we divide lists into two, and on how we merge them. For instance if we divide by choosing every other element to go into each list, it is unlikely to be stable. If we divide by splitting a list at its midpoint, and break ties when merging in favor of the first list, then the algorithm can be stable.

Continues... * Quick sort? Again, maybe. It depends on how you do the partition step. Any comparison sorting algorithm can be made stable by modifying the comparisons to break ties according to the original positions of the objects, but only some algorithms are automatically stable.

THE END