This algorithm sorts the given array containing n number of elements, into ascending order. This algorithm uses Brut Force method of problem solving.
What's Brut Force Method?
This is a approach of problem solving in design and analysis of algorithms. It is a straight forward approach of problem solving. Which means the problem is solved directly based on the problem statements and definition of concepts involved. In simple words, its a type of Trial and Error problem solving.
- Learn more about Brut Force method here.
- and about Trial and error method here.
Algorithm:
Illustration:
Take an example array which is to be sorted
A = { 89 , 45 , 68 , 90 , 29 , 34 , 17 }
In the first line of the algorithm, This array is passed as an argument for the selection sort algorithm.
Now the logic in brief:
A loop is run n-1 number of times, At the beginning the first number is imagined to be minimum number in the array. Then for each iteration, the minimum number in the array which is next to the first number, is found. and after finding the minimum number, it is swapped (Exchanged) with the first number. Now at this point, First minimum number of the entire array is at the first position.
For the next iteration, second number is considered to be the minimum number, and any number which is lesser than the second number (if any) is found and swapped with the second element. Now the second minimum element in the array must be at the second position. This way, the process is continued for n-1 times, each time bringing a number to its appropriate (sorted) position in the array.
Detailed explanation:
- The first for loop is run n-1 number of times, that is value of i ranging from 0 to n-2.(each time bringing a number to its appropriate position in the array)
- Inside the first for loop, the 1st element (that is 0th element according to array indexing) is considered to be the minimum element by assigning the value of minimum to a[i].
- 2nd for loop runs from 'i+1'(number next to the considered minimum element) to 'n-1'(the last element). Inside this for loop, it is checked whether, the value at j in the array is lesser than a[i](the considered minimum element). If there is one, value of minimum is set to a[j]. at the end of second for loop, the minimum value at that iteration is found. Then it swapped with the a[i]. Now smallest element is sitting in its appropriate position.
- Same thing is continued for n-1 numbers of times to bring the smallest elements in its appropriate position.
Example:
Consider the above told array
A = { 89 , 45 , 68 , 90 , 29 , 34 , 17 }
1. i=0
minimum=a[0]=89;
for j loop check if a[j] is less than minimum(in this case 89). If it is lesser, them update the value of minimum=j.
at the end of this loop, the first minimum value of the array is found. That is 17. Minimum=6 (array index of the value 17)
a[0] is swapped with a[minimum]
89 is swapped with 17.
now array is
A = { 17 , 45 , 68 , 90 , 29 , 34 , 89 }
2. i=1
minimum=a[1]=45;
now in j loop iteration, minimum is 29. so minimum=4.
a[1] is swapped with a[minimum]
45 is swapped with 29.
now array is
A = { 17 , 29 , 68 , 90 , 45 , 34 , 89 }
3. i=2
minimum=a[2]=68;
now in j loop iteration, minimum is 34. so minimum=5.
a[2] is swapped with a[minimum]
68 is swapped with 34.
now array is
A = { 17 , 29 , 34 , 90 , 45 , 68 , 89 }
4. i=3
minimum=a[3]=90;
now in j loop iteration, minimum is 45. so minimum=4.
a[3] is swapped with a[minimum]
90 is swapped with 45.
now array is
A = { 17 , 29 , 34 , 45 , 90 , 68 , 89 }
5. i=4
minimum=a[4]=90;
now in j loop iteration, minimum is 68. so minimum=5.
a[4] is swapped with a[minimum]
90 is swapped with 68.
now array is
A = { 17 , 29 , 34 , 45 , 68 , 90 , 89 }
6. i=5
minimum=a[5]=90;
now in j loop iteration, minimum is 89. so minimum=6.
a[5] is swapped with a[minimum]
90 is swapped with 89.
now array is
A = { 17 , 29 , 34 , 45 , 68 , 89 , 90 }
As you can see now, in 6 iterations, the array is sorted finally.
n=7. so we needed n-1=6 iterations to solve this problem.
Complexity of the algorithm:
The basic operation in this algorithm is 'Comparison' (usually it can be found in the innermost loops of the algorithm).
1. j loop runs for i+1 to n-1 times.
2. i loop runs from 1 to n-2 times, each time running j loop as given in the step 1 above. (j is contained inside i loop)
so the time complexity would be,
Hope you are clear with the concept,
see you in the next post ;)
Share your views about this article!