Sorting Algorithm:
There are many applications where the data is stored in sorted order. Employee data, Telephone
directory, Merit list etc. are the examples where we can store data in sorted order.
Definition:
Sorting is an operation of arranging data in some given order such as ascending or
descending.
In other words sorting means to arrange a set of items in sequence.
Examples:
Suppose the data contains 6 elements as follows
Data: 52, 12, 26, 67, 20, 10
After sorting data in ascending order
Data: 10, 12, 20, 26, 52, 67
After sorting data in descending order
Data: 67, 52, 26, 20, 12, 10
Sorting Methods:
There are some methods to sort given data in given order.
Bubble Sort (Exchange Sort)
Insertion Sort
Selection Sort
Bubble Sort (Exchange Sort):
Compare adjacent elements in the list and exchange them if not ordered.
In each pass, each element is compared with its successor. If the first elements is greater
than the second element i.e. if they are not in proper order then the position of the elements
are interchanged. Then next element is compared with its successor and same process is
repeated for all the elements in an array.
After the first pass, the largest element is in its proper position i.e. last position. During the
second pass, the second largest element occupies the second last position.
Since each iteration places a new element into its proper position, an array on n elements
requires no more than n-1 iterations.
The method is called the bubble sort because each number slowly “bubbles” up to its proper
position.
In short, in first pass, the largest element will “bubble-up” in last position.
In second pass, the second largest element will “bubble-up”
After n-1 passes all elements gets sorted.
Pseudo-Code
BubbleSort(A, n):
for i = 0 to n-2
for j = 0 to n-2-i
if A[j] > A[j+1]
swap(A[j], A[j+1])
Line-by-Line Explanation
1. BubbleSort(A, n):
This defines a function named BubbleSort
A is the array to be sorted
n is the number of elements in the array
2. for i = 0 to n-2
This is the outer loop
It represents the number of passes
After each pass, the largest unsorted element moves to its correct position at the end
We need n−1 passes, so the loop runs from 0 to n−2
3. for j = 0 to n-2-i
This is the inner loop
It compares adjacent elements
The - i part reduces the number of comparisons after each pass
Because after every pass, the last i elements are already sorted
4. if A[j] > A[j+1]
Compares two adjacent elements
If the current element is greater than the next one, they are in the wrong order
5. swap(A[j], A[j+1])
Swaps the two elements
This pushes the larger element towards the end
Repeating this makes the largest element “bubble up” in each pass
Bubble sort algorithm:
Step 1: Start from the first element.
Step2: Compare it with the next element.
Step3: If the first number is bigger, swap them.
Step4: Move one step forward and repeat comparison.
Step5: When you reach the end, one round is complete.
Step6: Repeat the process for the remaining elements.
Step7: Stop when no swaps are needed.
Example: Consider array elements as 34, 6, 14, 8, 2
Iteration 1:
34 6 14 8 2
Swap
6 34 14 8 2
Swap
6 14 34 8 2
Swap
6 14 8 34 2
Swap
6 14 8 2 34
Iteration 2:
6 14 8 2 34
No Swap
6 14 8 2 34
Swap
6 8 14 2 34
Swap
6 8 2 14 34
Iteration 3:
6 8 2 14 34
No Swap
6 8 2 14 34
Swap
6 2 8 14 34
Iteration 4:
6 2 8 14 34
Swap
2 6 8 14 34
The complete set of iteration is as follows:
Iteration 1: 6 14 8 2 34
Iteration 2: 6 8 2 14 34
Iteration 3: 6 2 8 14 34
Iteration 4: 2 6 8 14 34