﻿ Python List - Find the kth smallest element in a list

# Python List Advanced Exercise - Find the kth smallest element in a list

## Python List Advanced: Exercise-4 with Solution

Write a Python function to find the kth smallest element in a list.

Sample Solution-1:

This function sorts the list ascending. Since Python list indexing starts with 0, and returns the (k-1)th element. This approach has a time complexity of O(n log n) due to the sorting operation

Python Code:

`````` # Define a function to find the kth smallest element in a list
def kth_smallest_el(lst, k):
# Sort the list in ascending order
lst.sort()
# Return the kth smallest element (0-based index, so k-1)
return lst[k - 1]

# Create a list of numbers
nums = [1, 2, 4, 3, 5, 4, 6, 9, 2, 1]

# Print the original list
print("Original list:")
print(nums)

# Initialize 'k' to 1
k = 1

# Iterate from k = 1 to k = 10
for i in range(1, 11):
# Print a message indicating the value of 'k'
print("kth smallest element in the said list, when k =", k)

# Call the kth_smallest_el function with 'k' and print the result
print(kth_smallest_el(nums, k))

# Increment 'k' by 1 for the next iteration
k = k + 1
```
```

Sample Output:

```Original list:
[1, 2, 4, 3, 5, 4, 6, 9, 2, 1]
kth smallest element in the said list, when k =  1
1
kth smallest element in the said list, when k =  2
1
kth smallest element in the said list, when k =  3
2
kth smallest element in the said list, when k =  4
2
kth smallest element in the said list, when k =  5
3
kth smallest element in the said list, when k =  6
4
kth smallest element in the said list, when k =  7
4
kth smallest element in the said list, when k =  8
5
kth smallest element in the said list, when k =  9
6
kth smallest element in the said list, when k =  10
9
```

Flowchart:

What is the time complexity and space complexity of the following Python code?

``````def kth_smallest_el(lst, k):
lst.sort()
return lst[k-1]
``````

Time complexity - The code uses the built-in Python sort() function, which has a time complexity of O(n log n), and then retrieves the kth smallest element, which takes constant time. So, the time complexity of the given code is O(n log n), where n is the length of the input list "lst".

Space complexity - The space complexity of the code is O(1), as the code only uses a constant amount of additional space regardless of the size of the input list "lst".

Sample Solution-2:

In computer science, quickselect is a selection algorithm to find the kth smallest element in an unordered list, also known as the kth order statistic. Like the related quicksort sorting algorithm, it was developed by Tony Hoare, and thus is also known as Hoare's selection algorithm.
Here is an implementation of the kth smallest element in a list using the QuickSelect algorithm:

Python Code:

``````# Define a function to find the kth smallest element in a list using quickselect algorithm
def quickselect(lst, k, start_pos=0, end_pos=None):
# If end_pos is not specified, set it to the last index of the list
if end_pos is None:
end_pos = len(lst) - 1

# Base case: If the start position is greater than or equal to the end position, return the element at the start position
if start_pos >= end_pos:
return lst[start_pos]

# Find the pivot index using the partition function
pivot_idx = partition(lst, start_pos, end_pos)

# Compare k with the pivot index to determine which side to search for the kth smallest element
if k == pivot_idx:
return lst[k]
elif k < pivot_idx:
# Recursively search for the kth smallest element in the left part of the partition
return quickselect(lst, k, start_pos, pivot_idx - 1)
else:
# Recursively search for the kth smallest element in the right part of the partition
return quickselect(lst, k, pivot_idx + 1, end_pos)

# Define a function to partition a list and choose a pivot element
def partition(lst, start_pos, end_pos):
# Choose the pivot element as the last element in the list
pivot = lst[end_pos]
pivot_idx = start_pos

# Iterate through the list and move elements smaller than the pivot to the left side
for i in range(start_pos, end_pos):
if lst[i] <= pivot:  # Compare elements with the pivot
lst[i], lst[pivot_idx] = lst[pivot_idx], lst[i]
pivot_idx += 1

# Swap the pivot element to its correct position in the partition
lst[end_pos], lst[pivot_idx] = lst[pivot_idx], lst[end_pos]

# Return the pivot index
return pivot_idx

# Create a list of numbers
nums = [1, 2, 4, 3, 5, 4, 6, 9, 2, 1]

# Print the original list
print("Original list:")
print(nums)

# Initialize 'k' to 1
k = 1

# Iterate from k = 1 to k = 10
for i in range(1, 11):
# Print a message indicating the value of 'k'
print("kth smallest element in the said list, when k =", k)

# Call the quickselect function with 'k-1' to find the kth smallest element and print the result
print(quickselect(nums, k - 1))

# Increment 'k' by 1 for the next iteration
k = k + 1
```
```

Sample Output:

```Original list:
[1, 2, 4, 3, 5, 4, 6, 9, 2, 1]
kth smallest element in the said list, when k =  1
1
kth smallest element in the said list, when k =  2
1
kth smallest element in the said list, when k =  3
2
kth smallest element in the said list, when k =  4
2
kth smallest element in the said list, when k =  5
3
kth smallest element in the said list, when k =  6
4
kth smallest element in the said list, when k =  7
4
kth smallest element in the said list, when k =  8
5
kth smallest element in the said list, when k =  9
6
kth smallest element in the said list, when k =  10
9
```

Flowchart:

What is the time complexity and space complexity of the following Python code?

``````def quickselect(lst, k, start_pos=0, end_pos=None):
if end_pos is None:
end_pos = len(lst) - 1
if start_pos >= end_pos:
return lst[start_pos]
pivot_idx = partition(lst, start_pos, end_pos)
if k == pivot_idx:
return lst[k]
elif k < pivot_idx:
return quickselect(lst, k, start_pos, pivot_idx - 1)
else:
return quickselect(lst, k, pivot_idx + 1, end_pos)
def partition(lst, start_pos, end_pos):
pivot = lst[end_pos]
pivot_idx = start_pos
for i in range(start_pos, end_pos):
if lst[i] <= pivot: # corrected this line
lst[i], lst[pivot_idx] = lst[pivot_idx], lst[i]
pivot_idx += 1
lst[end_pos], lst[pivot_idx] = lst[pivot_idx], lst[end_pos]
return pivot_idx
``````

Time complexity - The code uses the quickselect algorithm to find the kth smallest element in the list "lst", which has an average time complexity of O(n) and a worst-case time complexity of O(n^2). However, the worst-case time complexity is highly unlikely due to the randomized nature of the algorithm. So, the time complexity of the given code is O(n), where n is the length of the input list "lst".

Space complexity - The code uses recursion to call the quickselect function multiple times with smaller sub-arrays. The maximum recursion depth is logarithmic in n, so the space complexity is O(log n). Additionally, the "partition" function uses a constant amount of additional space, so it does not contribute to the space complexity.

Python Code Editor:

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.

﻿