SORTING
SORTING
•Sorting refers to the operation of
arranging data in some given order,
such as increasing or decreasing, with
numerical data or alphabetically, with
character data.
SORTING TECHNIQUES
☞Selection sort.
☞Bubble sot.
☞Insertion Sort.
☞Merge Sort.
☞…..
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.
Properties
•Stable
•O(1) extra space
•O(n2) comparisons and swaps
•Adaptive: O(n) when nearly sorted
•Bubble sort has many of the same properties as insertion sort, but has slightly
higher overhead. In the case of nearly sorted data, bubble sort takes O(n)
time, but requires at least 2 passes through the data (whereas insertion sort
requires something more like 1 pass).
BUBBLE SORT
44 33 33 33 33
33 44 44 44 44
55 55 55 22 22
22 22 22 55 11
11 11 11 11 55
PHASE 1
33 33 33 33
44 44 22 22
22 22 44 11
11 11 11 44
55 55 55 55
PHASE 2
33 22 22
22 33 11
11 11 33
44 44 44
55 55 55
PHASE 3
22 11
11 22
33 33
44 44
55 55
PHASE 3
Selection Sort
The selection sort is a simple sorting algorithm. The
following illustrates the steps of the selection
sort algorithm:
• Find the minimum element in the list.
• Swap it with the element in the first position of
the list.
• Repeat the steps above for all remaining
elements of the list starting from the second
position.
• The complexity of the selection sort algorithm int
the worst case is O(n2). The selection sort
technique is less efficient on a large list.
• It generally performs worse than the insertion
sorttechnique.
Selection Sort
Insertion Sort
• When we sort something manually, we often use the insertion sort
technique e.g., when we sort a deck of playing cards. We can describe
the insertion sort algorithm similar to sort a deck of playing cards:
• First, we start with an empty set of cards (on our hand i.e., the sorted
array) and the cards on the table i.e., the unsorted array.
• Then we pick one card at a time from the table i.e., unsorted array, and
insert it into the proper position in our hand i.e., the sorted array
• In order to insert a card in the correct position, we compare it with the
existing cards in our hand from right to left.
• Notice that the cards that we hold are always sorted.
Properties
•Stable
•O(1) extra space
•O(n2) comparisons and swaps
•Adaptive: O(n) time when nearly sorted
•Very low overhead
Sort the following list using the insertion sort
method : 4, 1, 3, 2, 5
i) 4 Place 4 in 1st position
ii) 1 4 1 < 4, therefore insert prior to 4
iii) 1 3 4 3 > 1, insert between 1 & 4
iv) 1 2 3 4 2 > 1, insert between 1 & 3
v) 1 2 3 4 5 5>4, insert after 4
MERGE SORT
• Merge sort is one of the divide and conquer class of
algorithm. The basic idea is:
Divide the array to a number of sub-arrays.
Sort each of these sub-arrays.
Merge them to get a single sorted array.
2-way merge sort divides the list into two sorted
sub-arrays and then merges them to get the sorted
array, also called concatenate sort.
Its Basic action is to split an initially unsorted array
A[lower:upper] arround its middle element, “mid”
where mid = (lower + upper)/2), into two unsorted
array A[lower:mid] and A[mid+1:upper] and then
these two sorted sub arrays are merged.
The process of dividing the original array continues
till there is only one element in the array in which
case, the array is sorted. Example:-
(24 28 15 13 18 34 19 06)
Properties:
• Best case – When the array is already sorted O(nlogn).
• Worst case – When the array is sorted in reverse order O(nlogn).
• Average case – O(nlogn).
• Extra space is required, so space complexity is O(n) for arrays and
O(logn) for linked lists.
