Gnome sort
?Download as PPTX, PDF?
0 likes?843 views
The gnome sort algorithm sorts a list by finding the first pair of adjacent elements in the wrong order and swapping them, moving forward until no swaps are needed. It compares each element to the one before it, swapping and moving backward if out of order, or moving forward if in order. This continues until the list is fully sorted with no out of order pairs remaining. The algorithm runs through an example list step-by-step to demonstrate how it works.
![Algorithm
? procedure gnomeSort(a[]):
? pos := 0
? while pos < length(a):
? if (pos == 0 or a[pos] >= a[pos-1]):
? pos := pos + 1
? else:
? swap a[pos] and a[pos-1]
? pos := pos - 1](https://image.slidesharecdn.com/gnomesort-180220014310/85/Gnome-sort-3-320.jpg)
Gnome sort
- 2. Gnome Sort ? The algorithm always finds the first place where two adjacent elements are in the wrong order, and swaps them. It takes advantage of the fact that performing a swap can introduce a new out-of-order adjacent pair only next to the two swapped elements. It does not assume that elements forward of the current position are sorted, so it only needs to check the position directly previous to the swapped elements.
- 3. Algorithm ? procedure gnomeSort(a[]): ? pos := 0 ? while pos < length(a): ? if (pos == 0 or a[pos] >= a[pos-1]): ? pos := pos + 1 ? else: ? swap a[pos] and a[pos-1] ? pos := pos - 1
- 4. 40<9? No , exchange then Backward Is 40 < 9? No Swap (40,9) No Backward
- 5. 9<40? Yes, Forward Is 9 < 40? Yes Go Forward
- 6. 40<3? No, exchange Backward Is 40 < 3? No Swap (40,3) Go Backward
- 7. 9< 3? No, exchange backward Is 9 < 3? No, swap(9,3) Go Backward
- 8. 3<9? Yes, Forward Is 3 <9? Yes Go Forward
- 9. 9< 40? Yes, Forward Is 9 < 40? Yes Go Forward
- 10. 40<7? No, exchange Backward Is 40 < 7? No , swap(40,7) Go Backward
- 11. 9<7 ?No, exchange backward Is 9 < 7? No, swap(9,7) Go Backward
- 12. 3<7 ? Yes, Forward Is 3 < 7? Yes Go Forward
- 13. 7<9 ? Yes, Forward Is 7 < 9? Yes Go Forward
- 14. 9 <40? Yes, Forward Is 9 < 40? Yes Go Forward
- 15. 40<50? Yes, Forward Is 40 < 50? Yes Go Forward
- 16. 50< 23? No, exchange Backward Is 50 < 23? No swap(50,23) Go Backward
- 17. 40<23? No, exchange Backward Is 40 < 23? No Swap(40,23) Go Backward
- 18. 9<23? Yes, Forward Is 9 < 23? Yes Go Forward
- 19. 23>40? Yes, Forward Is 23 < 40? Yes Go Forward
- 20. 40<50? Yes, Forward Is 40 < 50? Yes Go Forward
- 21. 50<5?No, exchange Backward Is 50 < 5? No Swap(50,5) Go Backward
- 22. 40<5?No, exchange Backward Is 40 < 5? No Swap(40,5) Go Backward
- 23. 23<5?No, exchange Backward Is 23 < 5? No Swap(23,5) Go Backward
- 24. 9<5? No, exchange Backward Is 9 < 5? Yes Go Forward
- 25. 7<5? No exchange Backward Is 7 < 5? No Swap(7,5) Go Backward
- 26. 3<5? Yes , Forward Is 3 < 5? Yes Go Forward
- 27. 5<7? Yes, Forward Is 5 < 7? Yes Go Forward
- 28. 7<9? Yes, Forward Is 7 < 9? Yes Go Forward
- 29. 9<23? Yes, Forward Is 9 < 23? Yes Go Forward
- 30. 23<40? Yes, Forward Is 23 < 40? Yes Go Forward
- 31. 40<50?Yes, Forward Is 40 < 50? Yes Go Forward
- 32. 50<12? No, exchange Backward Is 50 < 12? No Swap(50,12) Go Backward
- 33. 40<12? No, exchange Backward Is 40 < 12? No Swap(40,12) Go Backward
- 34. 23<12? No, exchange Backward Is 23 < 12? No Swap(23,12) Go Backward
- 35. 9<12? Yes, Forward Is 9 < 12? Yes Go Forward
- 36. 12<23? Yes, Forward Is 12 < 23? Yes Go Forward
- 37. 23<40? Yes Forward Is 23 < 40? Yes Go Forward
- 38. 40<50? Yes, Forward Is 40 < 50? Yes Go Forward
- 39. End At the end Rock No check