Sorting: Sorting is the process of arranging a set of similar information into an increasing or decreasing order. Sorting is one of the most intellectually pleasing category because the process is so well defined. We can use function qsort( ) for sorting but it will sort array in memory not linked lists. Finally qsort( ) is very effective in general case but not the best for all situations.
Selection Sort : A selection sort selects the element with the lowest value and exchanges it with first element. Then from the remaining n-1 elements, the element with smallest value is found and exchanged with the second element, and so forth. The exchanges continue to the last two elements. For example, if selection sort method is used on the array dcab, each pass would like this:
Initial d c a b
Pass 1 a c d b
Pass 2 a b d c
Pass 3 a b c d
n / 6 log n
Average Number of Exchanges = .
Bubble Sort : The most well known and infamous sort is Bubble Sort. Its popularity is derived from its catchy name and simplicity. However, for general purpose sorting, it is one of the worst sort sorts ever convinced.
The Bubble Sort is an exchange sort. It involves repeated comparisons and, if necessary exchange of adjacent elements. The elements are just like bubbles in a tank of water – each seeks its own level. For example, if bubble sort method is used on the array dcab, each pass is shown here:
Initial d c a b
Pass 1 a d b c
Pass 2 a b d c
Pass 3 a b c d
In analyzing any sort, it is useful to have an idea about comparisons and exchanges performed for best, average, worst case. With Bubble Sort, the no. of comparisons are always same because two for loops repeat the specified no. of times whether the list is initially ordered or not.
1 / 2(n2-n)
Average Number of Exchanges =
Where n is no. of elements to be sorted. The formula is derived from the fact that outer for loop executes n-1 times while inner one n/2 times. Multiplied together results in the preceding formula. For Bubble Sort :
Case No. of Exchanges. Remarks
Best Zero Already Sorted List
Average 1/2(n2-n) -
Worst 1/2(n2-n) -
Selection Sort : A selection sort selects the element with the lowest value and exchanges it with first element. Then from the remaining n-1 elements, the element with smallest value is found and exchanged with the second element, and so forth. The exchanges continue to the last two elements. For example, if selection sort method is used on the array dcab, each pass would like this:
Initial d c a b
Pass 1 a c d b
Pass 2 a b d c
Pass 3 a b c d
n / 6 log n
Average Number of Exchanges = .
Bubble Sort : The most well known and infamous sort is Bubble Sort. Its popularity is derived from its catchy name and simplicity. However, for general purpose sorting, it is one of the worst sort sorts ever convinced.
The Bubble Sort is an exchange sort. It involves repeated comparisons and, if necessary exchange of adjacent elements. The elements are just like bubbles in a tank of water – each seeks its own level. For example, if bubble sort method is used on the array dcab, each pass is shown here:
Initial d c a b
Pass 1 a d b c
Pass 2 a b d c
Pass 3 a b c d
In analyzing any sort, it is useful to have an idea about comparisons and exchanges performed for best, average, worst case. With Bubble Sort, the no. of comparisons are always same because two for loops repeat the specified no. of times whether the list is initially ordered or not.
1 / 2(n2-n)
Average Number of Exchanges =
Where n is no. of elements to be sorted. The formula is derived from the fact that outer for loop executes n-1 times while inner one n/2 times. Multiplied together results in the preceding formula. For Bubble Sort :
Case No. of Exchanges. Remarks
Best Zero Already Sorted List
Average 1/2(n2-n) -
Worst 1/2(n2-n) -
Sorting process by anil nain from sonepat haryana
No comments:
Post a Comment