Sorting
Sorting is the process of placing elements from a collection in some kind of order. For example, a list of words could be sorted alphabetically or by length. A list of cities could be sorted by population, by area, or by zip code. We have already seen a number of algorithms that were able to benefit from having a sorted list (recall the final anagram example and the binary search).
Types of sorting algorithms –
1.Bubble Sort
2.Selection Sort
3.Insertion Sort
4.Quick Sort
5.Merge Sort
6.Heap Sort
7.Radix Sort
8. Shell Sort etc.
Internal
and External Sorting
ØInternal
sort is any data sorting
process that takes place entirely within the main
memory of
a computer.
•This is possible whenever
the data to be sorted is small enough to all be held in the main memory.
ØExternal
sorting is a term for a
class of sorting algorithms that can handle massive amounts
of data.
•External sorting is required
when the data being sorted do not fit into the main memory of a
computing device (usually RAM) and instead they must reside in the
slower external memory (usually a hard drive).
External merge sort
One example of external sorting is the
external merge sort algorithm, which sorts chunks that each fit in
RAM, then merges the sorted chunks together.
For example, for sorting
900 megabytes of data using only 100 megabytes of RAM
Bubble
Sort
The simplest sorting algorithm is bubble sort. The bubble sort works by iterating down an array to be sorted from the first element to the last, comparing each pair of elements and switching their positions if necessary. This process is repeated as many times as necessary, until the array is sorted. Since the worst case scenario is that the array is in reverse order, and that the first element in sorted array is the last element in the starting array, the most exchanges that will be necessary is equal to the length of the array.
Ø Move from left to
right end
Ø Compare the two elements and swap them if
needed
Algorithm Bubble_sort(a,n): This algorithm sort
the elements in ascending order. a is linear array
which contains n elements. Variable temp is used to facilitate the swapping of
two values. I and J are used as loop control variables.
Analysis
of Bubble Sort (version 1) :
For Step 2 :
I =1 J= 0 to (n-2)
i.e. total (n-1) and 1 for false. Hence n times
I =2 J =0 to
(n-3) i.e. total (n-2) and 1 for false. Hence n-1 times
…….
I=n-1 J=0 to
(n-1-n+1) i.e. total 1 and 1 for false. Hence 2 times.
Time Complexity =
n * C1 + {n(n+1)/2 – 1}* C2 + {n(n+1)/2 – 2}* (C3+C4+C5+C6)
= n + (n2 +
n - 2) /2 + 2*(n2 + n - 4)
= O(n2)
Analysis of Bubble Sort (version 2) :
From the above illustration, we observe following points
–
In (n-1) iterations or passes array will become sorted.
Iteration 1: no.
of comparisons (n-1)
Iteration 2: no.
of comparisons (n-2)
Iteration 3: no.
of comparisons (n-3)
………………..
Iteration k: no.
of comparisons (n-k)
……………...
Iteration last: no.
of comparisons 1
Time Complexity =
Total Comparisons
= (n-1) + (n-2) +
(n-3) + ….+ (n-k) + …. + 3 + 2 + 1
= n(n-1)/2
= O(n2)
Selection
Sort
Ø Move from left to
right end
Ø Each time least element gets its final
position i.e. we select least element and put it at
it’s final position
Algorithm Select_sort(a,n): This algorithm sort
the elements in ascending order. a is linear array
which contains n elements. Variable temp is used to facilitate the swapping of
two values. I and J are used as loop control variables.
1.For I = 0 to n-2
2. For J = I+1 to
(n-1)
3. If a[I] >
a[J] then,
4. Set temp = a[I]
5. Set a[I] = a[J]
6. Set a[J] = temp
Analysis
of Selection Sort
From the above illustration, we observe following points
–
In (n-1) iterations or passes array will become sorted.
Iteration 1: no.
of comparisons (n-1)
Iteration 2: no.
of comparisons (n-2)
Iteration 3: no.
of comparisons (n-3)
………………..
Iteration k: no.
of comparisons (n-k)
……………...
Iteration last: no.
of comparisons 1
Time Complexity =
Total Comparisons
= (n-1) + (n-2) +
(n-3) + ….+ (n-k) + …. + 3 + 2 + 1
= n(n-1)/2
= O(n2)
