Ever wanted to sort out the books in your library at home? Or even the money in your purse? Then sorting comes your way!
Sorting is a method of arranging items in a particular format. A list of items can be sorted in a number of ways in based upon various parameters, for instance, a numeric list can sorted in ascending or descending order.
But a discussion on which is the fastest and the most efficient sorting method, can be interesting!
So, let’s have an interesting discussion on the various methods of sorting. Thus, beginning the ‘Sorting series‘!
This blog is titled as ‘Sorting Squared‘! (And we leave it to you to guess why!)
Bubble sort
Bubble sort is also known by the name “sinking sort”.It comes under the class of sorting algorithm.
The basic approach here is to repeatedly compare consecutive elements in the list and swap them if they are placed incorrect.
AlgoRITHM
1.Start
2.Take input for n(value of array size )
3.Initialise array with size n
3.1 Take input for array
4.Start for loop as for (i = 0; i < n-1; i++)
4.1Start for loop as for (j = 0; j < n-i-1; j++)
4.1.1 if (arr[j] > arr[j+1])
4 .1.1.1 swap(&arr[j], &arr[j+1]);
5.End
Explanation :
Bubble sort is amongst the most simple sorting techniques with time complexity O(n^2).
In this sorting technique,the we use two for loops :-
1. The 1st for-loop has ‘i’ starting from 0 goes till ‘n-1’ (array size -1).
1.1 2nd for loop has j starting from 0 goes till ‘n-i-1’ (last i elements are already in place)
Now we check if the arr[j] is greater than arr[j+1] then we swap them otherwise increment ‘i’ and ‘j’ .This is done till the whole array is sorted !
Let us understand with an example
TIME AND SPACE COMPLEXITY
| Worst-case-performance | O(N^2) |
| Best-case-performance | O(N) |
| Average-case-performance | O(N^2) |
| Worst-case-space complexity | O(1) AUXILLARY |
Use :-
1. Bubble sort is used in computer graphics since this sort can detect a very small error in partially sorted array and also fix it with linear complexity.
2. Also used in Polygon filling algorithm
Advantage:
Bubble sort has the ability to detect if elements of array are sorted efficiently is built into the algo .When the list is sorted ,the complexity of bubble sort is only O(n).On comparison,even the sorting algos with better average-case complexity perform the entire sorting on the entire array ,hence are complex .
Disadvantage:
Bubble sort should be avoided in the case of large collections of elements .
Insertion sort
Insertion Sort is a sorting algorithm used to sort elements by putting them in their position one at a time.
An array of elements is divided in 2 parts, a sorted part containing a single element (initially) and the other part containing the rest of the array.
Each element of the unsorted part is compared with the sorted part and “inserted” into its proper position.
ALGORITHM
1. Repeat the following steps from i=1 till
1.1 i<n.
1.2 Assign key= a[i]
1.3 Assign j=i-1
1.4 Repeat the following steps till j>=0
1.4.1 If a[j]>key, assign a[j+1]=a[j]
1.4.2 Decrement ‘j’
End (j) loop
1.5 Assign a[j+1]=key
End (i) loop.
EXPLANATION
- Start a loop for i = 1 (second element of the array) to n (last element of the array).
- We assign the value of a[i] to ‘key’.
- We assign the value of i+1 to j.
- We compare the key for each iteration with each a[j], and shift a[j] to the right, while it is less than the key.
- Thus after ‘n’ iterations, each repeated for ‘n’ times, we get a sorted array!
Let us understand with an example!
TIME AND SPACE COMPLEXITY
| Worst-case-performance | O(N^2) |
| Best-case-performance | O(N) |
| Average-case-performance | O(N^2) |
| Worst-case-space complexity | O(N) TOTAL |
USE
1.When number of elements is less.
2.When the array is almost sorted ,and few swaps only are required .
ADVANTAGE
Simplicity of algorithm is the biggest advantage.Also being an “in-place” sorting technique , it uses minimum space. It’s advantageous to use this sorting technique, if we have a small list .
DISADVANTAGE
The main disadvantage is that its not suited for a large list of elements ,since with “n-squared” steps required for every “n” element to be sorted , it cannot handle a huge list. It does not perform that well in comparison with other sorting algorithms.
Selection sort
Selection sort is one of the simplest ‘in-place’ sorting algorithms. It keeps selecting the appropriate element and places it in the sorted part of the list. Hence the name, selection sort!
ALGORITHM
1.Repeat the following steps from i=0 to i=( n-1) times:
2.Set i as min
2.1 For each of the elements from index (i+1) to (n-1)
2.2 if the current_element < a[min]
2.2.1 Update min as current_element’s index
3.Swap a[i] and a[min]
EXPLANATION
Consider an array a with n elements. In every iteration the ith element is assumed to be the minimum, and hence, i is set as min in the beginning.
Now every element from the (i+1)th element to the last element, is compared with a[min], updating min whenever a smaller element is found in the array.
In other words, the smallest element from the (i+1)th element to the last element is found by the method of comparison.
Once the smallest element and its index (min) is found, it is swapped with the element at the ith index. Then i is incremented and the same process takes place.
At the end of (n-1) such iterations the array becomes sorted!
Let us understand with an example!
TIME AND SPACE COMPLEXITY
| Worst-case-performance | O(N^2) |
| Best-case-performance | O(N^2) |
| Average-case-performance | O(N^2) |
| Worst-case-space complexity | O(1) Auxillary |
USES
One must always remember that selection sort is usually used whenever writes are expensive. Such as when sorting on flash memory, each write is expensive. Hence selection sort may be considered here.
ADVANTAGES
1.Simple implementation
2. Lesser number of writes
3. Takes up lesser memory
4. Best for small number of elements
DISADVANTAGE
Slower for a large number of elements
We will be discussing more sorting techniques further in our blog, so stay tuned!
For any doubts or ambiguities, mail us at everythinggeeky.101@gmail.com, or comment below!
Don’t forget to Like, Comment and Share with your friends.
Stay Tuned for Everything Geeky.
See you next week!
Cheers!
Team Bitxorbytes
Follow us on instagram: @bitxorbytes
Cover Image: http://clipart-library.com/sort-cliparts.html
BitXorBytes 