Sorting:
Sorting algorithm is an algorithm that puts elements of a list in a certain order . The most-used orders are numerical order and lexicographical order.
Sorting algorithm classification:
Computaional complexcity.
Memory utilization
Stability-Maintaining relative order of records with equal keys.
No.of comparisions
Methods applied like insertion,exchange,,selection,merging etc.
Sorting is a process of linear ordering of list of objects
Sorting techniques are categoried into:
1. Internal sorting
2. External sorting
Internal sorting:
It takes the place in the main memory of a computer.
Eg: Bubble sort,Insertion sort,Shell sort,Quick sort,Heap Sort,etc
External sorting:
It takes the place in secondary memory of a computer,Since the number of objects to be stored is too large to fit in main memory
Eg:Merge sort,Multiway Merge,Polyphase merge.
Bubble Sort:
Bubble Sort is a simple sorting algorithm. It works by repeatedly stepping through the list to be sorted, comparing two items at a time 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. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort .
Analysis of bubble sort:
Worest case performance O(n2)
Best case performance O(n)
Average case performance O(n2)
Advantages:
It is very simple to implement.
Disadvantages:
If list is very large it take long time to evaluate.
Algorithm steps:
Step 1: Read the input list size.
Step 2: Read the list elements.
Step 3: Assign count =0
Step 4: Repeat the loop until count less than list size.(for n-1 passes)
i) Assign inner_count=count+1
ii) Repeat the loop inner_count less than list size (for arrange the
1) If list [count]> list [inner_count] (check element value )
2) temp = list [count]
3) list [count]=list[inner_count]
4) a[inner_count]=temp
C Program To Implement Bubble Sort
CPP Program To Implement Bubble Sort
|