Sorting
?Download as PPS, PDF?
1 like?400 views
The document describes two approaches to alphabetically sorting a list of 14 student names with minimum effort. Approach 1 involves comparing each name one by one, requiring 91 comparisons. Approach 2 first sorts names into groups by initial letter, then compares within each group and between groups, requiring only 18 comparisons, which is the recommended approach.
Sorting
- 1. Problem Solving Approach Using Data Structures in Algorithms
- 2. Scenario Suppose a teacher wants to arrange the test papers of 14 students alphabetically. The names of students are The teacher wants the work to be done with minimum effort. Suggest a way that causes minimum comparisons to arrange the test papers in alphabetic order. Ajay Beena Anita Gauri Cherry Babita Daisy Aastha Elina Isha Heena Diana Farhan Gagan
- 3. Approach 1 Ajay Beena Anita Gauri Cherry Babita Daisy Aastha Elina Isha Heena Diana Farhan Gagan ? Compare each name with other name. ? Continue this process until all names are arranged in alphabetic order.
- 7. Ajay Anita Beena Cherry Babita Daisy Aastha Elina Gauri Heena Diana Farhan Gagan Isha ? This is the list of names after first round of comparisons. ? It can be seen that after 1st round last name ¡°Isha¡± is in its correct position. ? So no of names left for comparison are 12. Approach 1
- 9. Ajay Anita Beena Babita Cherry Aastha Daisy Elina Gauri Diana Farhan Gagan Heena Isha ? This is the list of names after second round of comparisons. ? It can be seen that after 2nd round name ¡°Heena¡± is in its correct position. ? So no of names left for comparison are 11.
- 10. Aastha Ajay Anita Babita Beena Cherry Daisy Diana Elina Farhan Gagan Gauri Heena Isha ? So continuing in this manner we have final list of names arranged alphabetically. ? Therefore total no of comparison would be 13+12+11+10+9+8+7+6+5+4+3+2+1=91 Large Number I 2 3 4 5 6 7 8 10 11 12 139
- 11. Approach 2 Ajay Beena Anita Gauri Cherry Babita Daisy Aastha Elina Isha Heena Diana Farhan Gagan ? Instead of arranging one name at a time, keep the name according to the first letter of the name.
- 18. AjayA Anita Aasth a AjayA Anita AasthaA Anita Ajay Aasth a A Ajay Anita Comparison 2 Comparison 1 Comparison 3 Aastha Approach 2 Alphabetically Arranged
- 20. BeenaB Babita BabitaB Beena Comparison 1 Approach 2 Alphabetically Arranged
- 23. ? Number of comparison made are: 13+3+1+1+1=18 Small number Aastha Ajay Anita Babita Beena Cherry Daisy Diana Elina Farhan Gagan Gauri Heena Isha A---I B D G A
- 24. THANK YOU¡ Made by- Sonam Mittal