Array sort functions in PHP - Time & Space Complexity

Time Complexity: Array sort functions

O(n log n)

Understanding Time Complexity

Sorting arrays is a common task in programming. Knowing how the time needed grows as the array gets bigger helps us write better code.

We want to understand how sorting time changes when the array size increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

$array = [5, 3, 8, 1, 2];
sort($array);

This code sorts an array of numbers in ascending order using PHP's built-in sort function.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Comparing and swapping elements during sorting.
• How many times: Depends on the sorting algorithm, but generally multiple passes over the array elements.

How Execution Grows With Input

As the array gets bigger, the number of comparisons and swaps grows faster than the size itself.

Input Size (n)	Approx. Operations
10	About 35 operations
100	About 700 operations
1000	About 10,000 operations

Pattern observation: The operations grow roughly as n log n.

Final Time Complexity

Time Complexity: O(n log n)

This means the time to sort grows a bit faster than the size of the array but much slower than if it grew with the square of the size.

Common Mistake

[X] Wrong: "Sorting always takes the same time no matter the array size."

[OK] Correct: Sorting time depends on how many items there are; bigger arrays take more time because more comparisons and swaps are needed.

Interview Connect

Understanding sorting time helps you explain your choices and write efficient code, a skill valued in many programming tasks.

Self-Check

"What if we used a simple bubble sort instead of PHP's built-in sort? How would the time complexity change?"

Practice

1. Which PHP function sorts an array and keeps the original keys intact?

easy

A. rsort()

B. sort()

C. ksort()

D. asort()

Solution

1. Step 1: Understand key preservation in sorting

   asort() sorts values but keeps the original keys unchanged.

2. Step 2: Compare with other functions

   sort() resets keys, rsort() sorts in reverse but resets keys, ksort() sorts by keys, not values.

3. Final Answer:

   asort() -> Option D

4. Quick Check:

   Keep keys while sorting values = asort() [OK]

Hint: Use asort() to sort values and keep keys unchanged [OK]

Common Mistakes:

• Confusing sort() with asort() for key preservation
• Thinking ksort() sorts by values
• Assuming rsort() keeps keys

2. Which of the following is the correct syntax to sort an array in ascending order and reset keys in PHP?

easy

A. asort($array);

B. sort($array);

C. ksort($array);

D. arsort($array);

Solution

1. Step 1: Identify function for ascending sort with key reset

   sort() sorts array values in ascending order and resets keys.

2. Step 2: Check other options

   asort() keeps keys, ksort() sorts by keys, arsort() sorts descending.

3. Final Answer:

   sort($array); -> Option B

4. Quick Check:

   Ascending sort with reset keys = sort() [OK]

Hint: Use sort() to sort ascending and reset keys [OK]

Common Mistakes:

• Using asort() when keys should reset
• Confusing ksort() with value sort
• Using arsort() for ascending order

3. What will be the output of the following PHP code?

$arr = [3 => 'apple', 1 => 'banana', 2 => 'cherry'];
sort($arr);
print_r($arr);

medium

A. [0 => 'apple', 1 => 'banana', 2 => 'cherry']

B. [1 => 'banana', 2 => 'cherry', 3 => 'apple']

C. [0 => 'banana', 1 => 'cherry', 2 => 'apple']

D. [0 => 'apple', 1 => 'cherry', 2 => 'banana']

Solution

1. Step 1: Understand sort() behavior on keys

   sort() sorts values ascending and resets keys starting from 0.

2. Step 2: Sort values and assign new keys

   Values sorted ascending: 'apple', 'banana', 'cherry'. Keys reset to 0,1,2 respectively.

3. Final Answer:

   [0 => 'apple', 1 => 'banana', 2 => 'cherry'] -> Option A

4. Quick Check:

   sort() resets keys and sorts ascending [OK]

Hint: sort() resets keys and sorts values ascending [OK]

Common Mistakes:

• Expecting original keys to remain
• Confusing sort() with asort()
• Mixing order of sorted values

4. Identify the error in the following PHP code snippet:

$arr = ['b' => 2, 'a' => 1, 'c' => 3];
ksort($arr, SORT_DESC);
print_r($arr);

medium

A. ksort() sorts values, not keys

B. Array keys must be numeric for ksort()

C. ksort() does not accept SORT_DESC as a parameter

D. print_r() cannot print associative arrays

Solution

1. Step 1: Check ksort() parameters

   ksort() sorts array by keys in ascending order only; it does not support descending order.

2. Step 2: Understand SORT_DESC usage

   SORT_DESC is invalid for ksort(); to sort keys descending, use krsort() instead.

3. Final Answer:

   ksort() does not accept SORT_DESC as a parameter -> Option C

4. Quick Check:

   ksort() only sorts keys ascending [OK]

Hint: Use krsort() for descending key sort, not ksort() [OK]

Common Mistakes:

• Passing SORT_DESC to ksort()
• Thinking ksort() sorts values
• Believing print_r() can't print associative arrays

5. You have an associative array with user IDs as keys and scores as values:

$scores = [101 => 50, 102 => 75, 103 => 50, 104 => 90];

You want to sort the array by scores in descending order but keep the user IDs as keys. Which function should you use?

hard

A. arsort()

B. rsort()

C. krsort()

D. sort()

Solution

1. Step 1: Identify sorting by values descending with keys preserved

   arsort() sorts array by values in descending order and keeps keys intact.

2. Step 2: Compare with other functions

   rsort() sorts values descending but resets keys, krsort() sorts keys descending, sort() sorts ascending and resets keys.

3. Final Answer:

   arsort() -> Option A

4. Quick Check:

   Sort values descending and keep keys = arsort() [OK]

Hint: Use arsort() to sort values descending and keep keys [OK]

Common Mistakes:

• Using rsort() which resets keys
• Confusing krsort() with value sort
• Using sort() which sorts ascending and resets keys