Contenu du cours
Sorting Algorithms
Sorting Algorithms
Selection Sort
The Selection Sort is intuitive algorithm where we select elements one by one and compare with others. The main approach of selection sort is to find the minimum element of the array and put it in the first position. There is the first element of the sorted subarray. Then, find the minimum element in the rest of the array (which is unsorted), and move it next to the sorted subarray as second one, and so on.
Each time, the next found element will be greater or equal than all elements in the sorted subarray, but less or equal than all elements in the unsorted subarray.
Example 1
Example 2: Step by Step
arr = [0, -4, 12, 4, 10, 4]
Find min element in subarray arr[0:] and place it to the beginning:
arr = [ -4, 0, 12, 4, 10, 4]
Find min element in subarray arr[1:] and place it at the end of sorted subarray:
arr = [-4, 0, 12, 4, 10, 4 ]
Find min element in subarray arr[2:] and place it at the end of sorted subarray:
arr = [-4, 0, 4, 12, 10, 4 ]
Find min element in subarray arr[3:] and place it to the end of sorted subarray:
arr = [-4, 0, 4, 4, 10, 12 ]
Find min element in subarray arr[4:] and place it at the end of sorted subarray:
arr = [-4, 0, 4, 4, 10, 12 ]
Unsorted subarray has only one element now, so we won’t replace it, the algorithm is over.
arr = [-4, 0, 4, 4, 10, 12]
Time complexity of the algorithm is O(N^2), where N is the length of array. That's because there are two nested loops in the algorithm. To be clear, the number of operations is N-1 + N-2 + … 2+1 = N(N-1)/2, which is O(N^2).
Space complexity: O(1).
arr = [-12, 9, 1, 3, 40, 17, 3] for i in range(len(arr)-1): # Find the minimum element in unsorted array arr[i+1:] ind = i for j in range(i+1, len(arr)): # Find ind of min element if arr[ind] > arr[j]: ind = j # Swap the found minimum element with # The first element of unsorted subarray arr[i], arr[ind] = arr[ind], arr[i] print(arr)
Swipe to start coding
Modify Selection Sort algorithm to do the sort in descending order.
Solution
Passez à un bureau pour une pratique réelleContinuez d'où vous êtes en utilisant l'une des options ci-dessousMerci pour vos commentaires !
Selection Sort
The Selection Sort is intuitive algorithm where we select elements one by one and compare with others. The main approach of selection sort is to find the minimum element of the array and put it in the first position. There is the first element of the sorted subarray. Then, find the minimum element in the rest of the array (which is unsorted), and move it next to the sorted subarray as second one, and so on.
Each time, the next found element will be greater or equal than all elements in the sorted subarray, but less or equal than all elements in the unsorted subarray.
Example 1
Example 2: Step by Step
arr = [0, -4, 12, 4, 10, 4]
Find min element in subarray arr[0:] and place it to the beginning:
arr = [ -4, 0, 12, 4, 10, 4]
Find min element in subarray arr[1:] and place it at the end of sorted subarray:
arr = [-4, 0, 12, 4, 10, 4 ]
Find min element in subarray arr[2:] and place it at the end of sorted subarray:
arr = [-4, 0, 4, 12, 10, 4 ]
Find min element in subarray arr[3:] and place it to the end of sorted subarray:
arr = [-4, 0, 4, 4, 10, 12 ]
Find min element in subarray arr[4:] and place it at the end of sorted subarray:
arr = [-4, 0, 4, 4, 10, 12 ]
Unsorted subarray has only one element now, so we won’t replace it, the algorithm is over.
arr = [-4, 0, 4, 4, 10, 12]
Time complexity of the algorithm is O(N^2), where N is the length of array. That's because there are two nested loops in the algorithm. To be clear, the number of operations is N-1 + N-2 + … 2+1 = N(N-1)/2, which is O(N^2).
Space complexity: O(1).
arr = [-12, 9, 1, 3, 40, 17, 3] for i in range(len(arr)-1): # Find the minimum element in unsorted array arr[i+1:] ind = i for j in range(i+1, len(arr)): # Find ind of min element if arr[ind] > arr[j]: ind = j # Swap the found minimum element with # The first element of unsorted subarray arr[i], arr[ind] = arr[ind], arr[i] print(arr)
Swipe to start coding
Modify Selection Sort algorithm to do the sort in descending order.
Solution
Passez à un bureau pour une pratique réelleContinuez d'où vous êtes en utilisant l'une des options ci-dessousMerci pour vos commentaires !
Passez à un bureau pour une pratique réelleContinuez d'où vous êtes en utilisant l'une des options ci-dessous