Sorting

Sorting is a task of rearranging data in some order (ascending, descending, lexicographic etc.).
Basic terminologies
1. Internal sort (Data elements are stored in the primary memory)
2. External sort (Data elements are stored in the secondary memory)
3. Ascending order (Whenever the relation between any two distinct data elements, say x i∧x j is x i ≤ x j
then the order of sorting is known as ascending order.
4. Descending order (Whenever the relation between any two distinct data elements, say x i∧x j is x i ≥ x j
then the order of sorting is known as ascending order.
5. Lexicographic order (Whenever character data or string data are arranged in the same order as of the
dictionary then it is known as Lexicographical order e.g. ada, bat, cat, mat, max, may, min)
6. Collating sequence
7. In place sort (Whenever a list of data elements stored in an array get sorted without taking any
additional or auxiliary array)
8. Stable sort (A list of data elements may contain two or more equal data. If the sorting maintains the
same relative position of those items in both the sorted and unsorted list then it is a stable sort)
{2, 5, 6, 4, 3, 2, 5, 1, 5}

{1, 2, 2, 3, 4, 5, 5, 5, 6}
Assumptions
1. A list of elements implies an array
2. The data type of items to be sorted is integer
3. The no. of elements in the array N i.e. A[1 .. N]
4. Sorting implies ascending order of sorting
Techniques of sorting
o Internal sort
 Sorting by comparison
 Insertion based
 Insertion sort
 Selection based
 Selection sort
 Heap sort
 Exchange based
 Bubble sort
 Quick sort
 Shell sort
 Merge based
 Merge sort
 Sorting by distribution
 Radix sort
 Bucket sort
 Counting sort
o External sort
Bubble sort

5 4 4 4 4 4 3 3 3
4 3 3 3 3 PASS 1 3 4 2 2 PASS2
3 5 5 2 2 2 2 4 1
2 2 2 5 1 1 1 1 4
1 1 1 1 5 5 5 5 5

3 2 2 2 1 1
2 3 1 PASS 3 PASS
1 2 2
1 1 3 4
4 4 4 3 3 3
5 5 5 4 4 4
5 5 5

For N elements N-1 passes are needed. At 1st pass 1 element will be placed in its correct position. At 2nd pass, 2
elements will be placed in their correct position. After (N-1)th pass, N-1 elements are placed in their correct
position.

Algorithm Bubble-Sort
Input: The elements of an array, say A[1 .. N]
Output: The elements are sorted in order (ascending, say)
Data Structure used: An array A[1 .. N]; Lower index = 1, Upper index = N, SIZE = U - L + 1 = N
Steps: Begin

For i = 1 to N - 1 step 1
{
For j = 1 to N - i step 2
{
If (A[j] > A[j + 1])
{
temp = A[j]
A[j] = A[j + 1]
A[j + 1] = temp
}
}
}

End

Time complexity

Case 1: (Best case) The elements of the array are sorted order
Case 2: (Worst case) The elements of the array are reverse sorted order
Case 3: (Average case) The elements of the array are sorted order

No. of comparisons:
In Pass 1 No. of comparison N - 1
In Pass 2 No. of comparison N - 2
In Pass 3 No. of comparison N - 3
...
In Pass (N-1) No. of comparison N - (N-1) = 1
 Total no. of comparisons ¿ [( N−1)+(N −2)+(N−3)+...+1]
( N −1 ) ( N−1+1 )
¿
2
N ( N −1 ) ( N 2−N )
¿ = , a polynomial of degree 2
2 2
Time complexity, T ( N )=O ( N 2 )

Modified Bubble Sort

If in any pass no swap operation is performed then it indicates that the array is already sorted. Thus, there is no
need to move to the next pass.

1 1 1 1 1
2 2 2 2 2 PASS 1
3 3 3 3 3
4 4 4 4 4
5 5 5 5 5

Algorithm Modified-Bubble-Sort
Input: The elements of an array, say A[1 .. N]
Output: The elements are sorted in order (ascending, say)
Data Structure used: An array A[1 .. N]; Lower index = 1, Upper index = N, SIZE = U - L + 1 = N
Steps: Begin

For i = 1 to N - 1 step 1
{
flag = 0
For j = 1 to N - i step 2
{
If (A[j] > A[j + 1])
{
temp = A[j]
A[j] = A[j + 1]
A[j + 1] = temp
flag = 1
}
}
if (flag == 0)
break;
}

End

H.W.
1. WAP to implement modified bubble sort
2. Perform time complexity analysis for modified bubble sort