🔁 Sorting

[tpemeja]

Summary

• Patterns

  • Built-in Sort: use Python’s Timsort (stable), know complexity and key usage.
  • Custom Key/Comparator: prefer key functions; use cmp_to_key only when needed; set clear tie-breakers.
  • Sorting Intervals: choose start- or end-based keys based on the task.
  • Counting/Bucket/Radix: exploit bounded domains or uniform-ish distributions for near-linear time.

• Choose

  • Quick, correct, general-purpose → Built-in Sort
  • Complex ordering (multi-key, custom rules) → Key function or cmp_to_key
  • Interval problems (merge, schedule, cover) → Interval-specific keys and tie-breakers
  • Small integer range / frequency tasks / uniform distributions → Counting/Bucket/Radix

Details

✅ Built-in sorting

Summary (Key points):

• Python’s list.sort() and sorted() are stable O(n log n) Timsort.
• Use key=... for multi-key; tuples give lexicographic ordering.
• sorted(iterable, key=..., reverse=...) returns a new list; list.sort() sorts in place.

Details

• Idioms

  a.sort()  # in-place ascending
  b = sorted(a, reverse=True)  # new list, descending
  
  # Multi-key: k1 asc, k2 desc, case-insensitive on k3
  arr.sort(key=lambda x: (x.k1, -x.k2, x.k3.lower()))

• Case 1: Array Partition

  def arrayPairSum(nums):
      nums.sort()
      return sum(nums[::2])

• Case 2: Minimum Absolute Difference

  def minimumAbsDifference(arr):
      arr.sort()
      best = float('inf')
      res = []
      for i in range(1, len(arr)):
          d = arr[i] - arr[i-1]
          if d < best:
              best = d
              res = [[arr[i-1], arr[i]]]
          elif d == best:
              res.append([arr[i-1], arr[i]])
      return res

• Case 3: H-Index

  def hIndex(citations):
      citations.sort(reverse=True)
      h = 0
      for i, c in enumerate(citations, 1):
          if c >= i:
              h = i
          else:
              break
      return h

• Pitfalls

  • NaN compares weirdly; filter or place NaNs explicitly.
  • Key functions should be cheap; precompute if expensive.

✅ Custom comparator sorting

Summary (Key points):

• Prefer key=...; only use functools.cmp_to_key when true comparator logic is needed.
• Define clear tie-breakers; Python’s sort is stable, so secondary keys can be layered via tuples.

Details

• Case 1: Largest Number

  from functools import cmp_to_key
  
  def largestNumber(nums):
      strs = list(map(str, nums))
      def cmp(a, b):
          if a + b > b + a: return -1
          if a + b < b + a: return 1
          return 0
      strs.sort(key=cmp_to_key(cmp))
      ans = ''.join(strs)
      return '0' if ans[0] == '0' else ans

• Case 2: Reorder Data in Log Files

  def reorderLogFiles(logs):
      def key(log):
          id_, rest = log.split(' ', 1)
          is_digit = rest[0].isdigit()
          # Letter-logs come first; then by content, then id
          return (1,) if is_digit else (0, rest, id_)
      return sorted(logs, key=key)

• Case 3: Sort the People

  def sortPeople(names, heights):
      people = list(zip(heights, names))
      people.sort(reverse=True)  # by height desc
      return [name for _, name in people]

• Case 4: Sort Characters By Frequency

  from collections import Counter
  
  def frequencySort(s):
      cnt = Counter(s)
      return ''.join(ch * freq for ch, freq in sorted(cnt.items(), key=lambda p: (-p[1], p[0])))

✅ Sorting intervals

Summary (Key points):

• Merge: sort by start asc, end asc; merge overlaps.
• Max non-overlap/scheduling: sort by end asc; greedily pick next compatible.
• Remove covered: sort by start asc, end desc.

Details

• Case 1: Merge Intervals

  def merge(intervals):
      intervals.sort(key=lambda x: (x[0], x[1]))
      res = []
      for s, e in intervals:
          if not res or s > res[-1][1]:
              res.append([s, e])
          else:
              res[-1][1] = max(res[-1][1], e)
      return res

• Case 2: Non-overlapping Intervals

  def eraseOverlapIntervals(intervals):
      intervals.sort(key=lambda x: x[1])
      keep, end = 0, -10**20
      for s, e in intervals:
          if s >= end:
              keep += 1
              end = e
      return len(intervals) - keep

• Case 3: Minimum Number of Arrows to Burst Balloons

  def findMinArrowShots(points):
      points.sort(key=lambda x: x[1])
      arrows, end = 0, -10**20
      for s, e in points:
          if s > end:
              arrows += 1
              end = e
      return arrows

• Case 4: Remove Covered Intervals

  def removeCoveredIntervals(intervals):
      intervals.sort(key=lambda x: (x[0], -x[1]))
      covered, max_end = 0, -10**20
      for s, e in intervals:
          if e <= max_end:
              covered += 1
          else:
              max_end = e
      return len(intervals) - covered

• Case 5: Insert Interval

  def insert(intervals, newInterval):
      res = []
      s, e = newInterval
      i, n = 0, len(intervals)
      while i < n and intervals[i][1] < s:
          res.append(intervals[i]); i += 1
      while i < n and intervals[i][0] <= e:
          s = min(s, intervals[i][0])
          e = max(e, intervals[i][1])
          i += 1
      res.append([s, e])
      while i < n:
          res.append(intervals[i]); i += 1
      return res

✅ Bucket sort / Counting sort

Summary (Key points):

• Counting sort: O(n + k) for small integer ranges; stable via prefix sums.
• Bucket techniques: use buckets for frequencies or uniform-ish distributions.
• Radix sort: stable counting per digit/byte; good for non-negative integers with fixed width.

Details

• Case 1: Top K Frequent Elements

  from collections import Counter
  
  def topKFrequent(nums, k):
      freq = Counter(nums)
      buckets = [[] for _ in range(len(nums) + 1)]
      for x, c in freq.items():
          buckets[c].append(x)
      ans = []
      for c in range(len(nums), -1, -1):
          for x in buckets[c]:
              ans.append(x)
              if len(ans) == k:
                  return ans

• Case 2: Relative Sort Array

  def relativeSortArray(arr1, arr2):
      order = {v: i for i, v in enumerate(arr2)}
      mx = max(arr1) if arr1 else 0
      cnt = [0] * (mx + 1)
      for x in arr1:
          cnt[x] += 1
      res = []
      for v in arr2:
          res += [v] * cnt[v]
          cnt[v] = 0
      for v in range(len(cnt)):
          res += [v] * cnt[v]
      return res

• Case 3: Sort Characters By Frequency

  from collections import Counter
  
  def frequencySort(s):
      cnt = Counter(s)
      buckets = [[] for _ in range(len(s) + 1)]
      for ch, c in cnt.items():
          buckets[c].append(ch)
      out = []
      for c in range(len(s), 0, -1):
          for ch in buckets[c]:
              out.append(ch * c)
      return ''.join(out)

• Case 4: Sort Colors

  def sortColors(nums):
      c0 = c1 = c2 = 0
      for x in nums:
          if x == 0: c0 += 1
          elif x == 1: c1 += 1
          else: c2 += 1
      i = 0
      for _ in range(c0): nums[i] = 0; i += 1
      for _ in range(c1): nums[i] = 1; i += 1
      for _ in range(c2): nums[i] = 2; i += 1

• Case 5: Maximum Gap

  def maximumGap(nums):
      n = len(nums)
      if n < 2: return 0
      mn, mx = min(nums), max(nums)
      if mn == mx: return 0
      size = max(1, (mx - mn) // (n - 1))
      buckets = [(float('inf'), float('-inf')) for _ in range((mx - mn) // size + 1)]
      for x in nums:
          i = (x - mn) // size
          bmin, bmax = buckets[i]
          buckets[i] = (min(bmin, x), max(bmax, x))
      prev = mn
      best = 0
      for bmin, bmax in buckets:
          if bmin == float('inf'):
              continue
          best = max(best, bmin - prev)
          prev = bmax
      return best

• Case 6: Stable counting sort utility (handles negatives via offset)

  def counting_sort(a):
      if not a: return a
      mn, mx = min(a), max(a)
      k = mx - mn + 1
      cnt = [0] * k
      for x in a:
          cnt[x - mn] += 1
      for i in range(1, k):
          cnt[i] += cnt[i - 1]
      out = [0] * len(a)
      for x in reversed(a):  # stable
          idx = x - mn
          cnt[idx] -= 1
          out[cnt[idx]] = x
      return out