SORTING
2 Marks Questions
1. Define Sorting.
Sorting is the process of ordering or arranging a given collection of
elements in some particular order either ascending or descending.
2. What are the uses of Sorting?
1) To organize data for better readability
2) More efficient processing
3) Enhanced application functionality.
3. Define pass.
In algorithm, every iteration through each element of a list is called a
pass.
4. Define Time complexity.
The amount of time an algorithm takes to process a given data can be
called its time complexity.
3 Marks Questions
1. Mention different sorting methods.
1) Bubble Sort
2) Selection Sort
3) Insertion Sort
2. Explain the working principle of Bubble Sort.
• It sorts a given list of elements by repeatedly comparing the
adjacent elements and swapping them if they are unordered.
• For a list with n elements, the bubble sort makes a total of n – 1
passes.
• In order to arrange elements in ascending order, the largest
element is identified after each pass and placed at the correct
position in the list. This can be considered as the largest element
being ‘bubbled up’. Hence the name Bubble sort.
3. Explain the working principle of Selection Sort.
• To sort a list having n elements, the selection sort makes (n-1)
number of passes through the list.
• The list is considered to be divided into two lists -- the left list
containing the sorted elements, and the right list containing the
unsorted elements.
• For arranging elements in ascending order, in the first pass, all
the elements in the unsorted list are traversed to find the
smallest element.
• The smallest element is then swapped with the leftmost
element of the unsorted list. This element occupies the first
position in the sorted list. This process continues until n-1
smallest elements are found and moved to their respective
places.
4. Explain the working principle of Insertion Sort.
• Insertion sort is another sorting algorithm that can arrange
elements of a given list in ascending or descending order.
• Each element in the unsorted list is considered one by one and
is inserted into the sorted list at its appropriate position.
• In each pass, the sorted list is traversed from the backward
direction to find the position where the unsorted element could
be inserted. Hence the sorting method is called insertion sort.
5. Explain time complexity of algorithms.
• Any algorithm that does not have any loop will have time
complexity as 1. Such algorithms are known as Constant time
algorithms.
• Any algorithm that has a loop (usually 1 to n) will have the time
complexity as n. Such algorithms are known as Linear time
algorithms.
• A loop within a loop (nested loop) will have the time complexity
as n2. Such algorithms are known as Quadratic time algorithms.
• If there is a nested loop and also a single loop, the time
complexity will be estimated on the basis of the nested loop
only.
5 Marks Questions
1. Write an algorithm for Bubble sort.
BUBBLESORT (numList, n)
Step 1: SET i = 0
Step 2: WHILE i< n REPEAT STEPS 3 to 8
Step 3: SET j = 0
Step 4: WHILE j< n-i-1, REPEAT STEPS 5 to 7
Step 5: IF numList[j] > numList[j+1] THEN
Step 6: swap(numList[j],numList[j+1])
Step 7: SET j=j+1
Step 8: SET i=i+1
2. Write an algorithm for Selection sort.
SELECTIONSORT (numList, n)
Step 1: SET i=0
Step 2: WHILE i< n REPEAT STEPS 3 to 11
Step 3: SET min = i, flag = 0
Step 4: SET j= i+1
Step 5: WHILE j<n, REPEAT STEPS 6 to 10
Step 6: IF numList[j] < numList[min] THEN
Step 7: min = j
Step 8: flag = 1
Step 9: IF flag = 1 THEN
Step 10: swap(numList[i],numList[min])
Step 11: SET i=i+1
3. Write an algorithm for Insertion sort.
INSERTIONSORT (numList, n)
Step 1: SET i=1
Step 2: WHILE i< n REPEAT STEPS 3 to 9
Step 3: temp = numList[i]
Step 4: SET j = i-1
Step 5: WHILE j> = 0 and numList[j]>temp,REPEAT
STEPS 6 to 7
Step 6: numList[j+1] = numList[j]
Step 7: SET j=j-1
Step 8: numList[j+1] = temp #insert
temp at position j
Step 9: set i=i+1
Tracing examples:
1) 8 7 13 1 -9 4
2) 7 9 8 2 5
3) 23 25 41 18 14 54
4) 5 2 8 12 1 6