Sorting by values in Pandas - Time & Space Complexity

Time Complexity: Sorting by values

O(n log n)

Understanding Time Complexity

When we sort data in pandas, we want to know how the time it takes changes as the data grows.

We ask: How does sorting time increase when we have more rows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import pandas as pd

df = pd.DataFrame({
    'A': [5, 2, 9, 1, 7],
    'B': [3, 8, 4, 6, 0]
})
sorted_df = df.sort_values(by='A')

This code creates a small table and sorts it by the values in column 'A'.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Comparing and rearranging rows based on column 'A' values.
• How many times: The sorting algorithm compares elements multiple times, roughly proportional to the number of rows times the logarithm of the number of rows.

How Execution Grows With Input

As the number of rows grows, the sorting work grows a bit faster than just the number of rows.

Input Size (n)	Approx. Operations
10	About 30 to 40 comparisons
100	About 600 to 700 comparisons
1000	About 10,000 to 12,000 comparisons

Pattern observation: The work grows faster than just the number of rows, but not as fast as the square of rows.

Final Time Complexity

Time Complexity: O(n log n)

This means sorting takes more time as data grows, but it grows in a balanced way, not too slow or too fast.

Common Mistake

[X] Wrong: "Sorting time grows exactly like the number of rows (linear)."

[OK] Correct: Sorting needs to compare many pairs, so it grows a bit faster than just the number of rows.

Interview Connect

Understanding sorting time helps you explain how data operations scale, a useful skill when working with real datasets.

Self-Check

"What if we sorted by multiple columns instead of one? How would the time complexity change?"

Practice

1. What does the sort_values() function do in pandas?

easy

A. It filters rows based on a condition.

B. It groups data by a column.

C. It sorts the DataFrame by one or more columns.

D. It merges two DataFrames.

Solution

1. Step 1: Understand the function purpose

   The sort_values() function is designed to reorder rows in a DataFrame based on the values in one or more columns.

2. Step 2: Compare with other functions

   Filtering, grouping, and merging are done by different pandas functions like filter(), groupby(), and merge().

3. Final Answer:

   It sorts the DataFrame by one or more columns. -> Option C

4. Quick Check:

   sort_values() = reorder rows by column values [OK]

Hint: Remember: sort_values orders rows by column data [OK]

Common Mistakes:

• Confusing sorting with filtering
• Thinking it groups data
• Mixing it up with merging DataFrames

2. Which of the following is the correct syntax to sort a DataFrame df by the column 'age' in descending order?

easy

A. df.sort_values(by='age', ascending=False)

B. df.sort_values('age', descending=True)

C. df.sort('age', ascending=False)

D. df.sort_values('age', ascending=True)

Solution

1. Step 1: Identify correct parameter names

   The correct parameter to specify the column is by='age', and to sort descending, use ascending=False.

2. Step 2: Check syntax correctness

   df.sort_values(by='age', ascending=False) uses the correct function name sort_values and correct parameters. df.sort_values('age', ascending=True) sorts ascending, C uses a wrong function sort, and B uses a wrong parameter descending=True.

3. Final Answer:

   df.sort_values(by='age', ascending=False) -> Option A

4. Quick Check:

   sort_values(by=col, ascending=False) = descending sort [OK]

Hint: Use ascending=False for descending order in sort_values [OK]

Common Mistakes:

• Using ascending=True for descending sort
• Using wrong parameter names like descending=True
• Using non-existent sort() method

3. Given the DataFrame:

import pandas as pd
df = pd.DataFrame({'name': ['Anna', 'Bob', 'Cara'], 'score': [88, 92, 85]})
print(df.sort_values('score'))

What will be the output?

medium

A. Original DataFrame without sorting

B. Rows sorted by 'score' descending: Bob, Anna, Cara

C. Error because 'score' is not a column

D. Rows sorted by 'score' ascending: Cara, Anna, Bob

Solution

1. Step 1: Understand the DataFrame content

   The DataFrame has names and scores: Anna(88), Bob(92), Cara(85).

2. Step 2: Apply sort_values on 'score'

   Sorting by 'score' ascending orders rows as Cara(85), Anna(88), Bob(92).

3. Final Answer:

   Rows sorted by 'score' ascending: Cara, Anna, Bob -> Option D

4. Quick Check:

   sort_values('score') sorts ascending by default [OK]

Hint: Default sort_values sorts ascending unless told otherwise [OK]

Common Mistakes:

• Assuming descending order by default
• Thinking original order is preserved
• Believing 'score' column does not exist

4. What is wrong with this code snippet?

df.sort_values('age', ascending='False')

medium

A. The column name 'age' must be passed as a list.

B. The ascending parameter should be a boolean, not a string.

C. sort_values does not accept the ascending parameter.

D. The function should be sort_by_values, not sort_values.

Solution

1. Step 1: Check parameter types

   The ascending parameter expects a boolean value True or False, not a string.

2. Step 2: Validate other parts

   The column name can be a string or list, sort_values is the correct function, and it accepts ascending.

3. Final Answer:

   The ascending parameter should be a boolean, not a string. -> Option B

4. Quick Check:

   ascending must be True/False boolean, not 'False' string [OK]

Hint: Use True/False without quotes for ascending parameter [OK]

Common Mistakes:

• Passing 'False' as a string instead of boolean
• Thinking column name must be a list
• Using wrong function name

5. You have a DataFrame df with columns 'city' and 'temperature'. You want to sort it first by 'city' alphabetically ascending, then by 'temperature' descending within each city. Which code correctly does this?

hard

A. df.sort_values(by=['city', 'temperature'], ascending=[True, False])

B. df.sort_values(by=['temperature', 'city'], ascending=[False, True])

C. df.sort_values(by=['city', 'temperature'], ascending=False)

D. df.sort_values(['city', 'temperature'], ascending=[False, True])

Solution

1. Step 1: Understand multi-column sorting

   To sort by multiple columns, pass a list to by and a list of booleans to ascending matching each column.

2. Step 2: Match sorting order requirements

   We want 'city' ascending (True) and 'temperature' descending (False), so ascending=[True, False].

3. Step 3: Check options

   df.sort_values(by=['city', 'temperature'], ascending=[True, False]) matches the correct order and ascending list. df.sort_values(by=['temperature', 'city'], ascending=[False, True]) reverses columns. df.sort_values(by=['city', 'temperature'], ascending=False) uses a single boolean for two columns. df.sort_values(['city', 'temperature'], ascending=[False, True]) has wrong ascending order.

4. Final Answer:

   df.sort_values(by=['city', 'temperature'], ascending=[True, False]) -> Option A

5. Quick Check:

   Multi-column sort uses lists for by and ascending [OK]

Hint: Use lists for by and ascending to sort multiple columns [OK]

Common Mistakes:

• Using single boolean for multiple columns
• Mixing column order in by list
• Wrong ascending order list