Related Tags

algorithm
python
time
complexity

# How to sort an array of a's and b's in O(n)

Educative Team

### Overview

The complexity of an algorithm is defined as the interval of time an algorithm takes to process a provided input. An algorithm can process its provided input in constant, linear, quadratic, exponential, and logarithmic time.

The term Big O refers to the complexity of an algorithm. An algorithm’s complexity increases with the time it takes to run the algorithm.

We define complexity in terms of $O(1)$, $O(n)$, $O(n^2)$, $O(n^n)$, and $O(log n)$.

• $O(1)$ refers to the program executed in constant time.
• $O(n)$ refers to the program executed in linear time.
• $O(n^2)$ refers to the program executed in quadratic time
• $O(n^n)$ refers to the program executed in exponential time
• $O(log n)$ refers to the program executed in logarithmic time

In this shot, we will sort an array of a’s and b’s in linear time.

### Example

Let’s consider a one-dimensional array of a’s and b’s, as shown below:

Input: An array of a's and b's

Now we have to sort the given array in ascending order in linear time O(n). After sorting, the array will look like the array given below.

Output: The array of a's and b's sorted

### Code implementation

Let’s solve this example using Python.

def sortanb(arr):
countofa=0;
for i in range(len(arr)):
if arr[i]=='a':
countofa+=1
countofb=len(arr)-countofa
for j in range(len(arr)):
if j<=countofb:
arr[j]='a'
else:
arr[j]='b'

if __name__ == "__main__":
array="ababaab"
arr = [char for char in array]
sortanb(arr)
print("Here is the sorted array :")
print(arr)
Sorting an array of a's and b's in linear time

### Code explanation

• Lines 3–5: We count the number of a’s in the input array.
• Line 6: We count the number of b’s by subtracting the countofa from the len(input_array), which is the length of the input array.
• Lines 7–11: We fill the array with the respective number of a’s and b’s.
• Line 14: We define a string of a’s and b’s.
• Line 15: We convert the string into a char array.
• Line 16: We call the function sortanb(input_array) to sort the char array.
• Lines 17–18: We print the sorted array.

RELATED TAGS

algorithm
python
time
complexity