Skip to content

05_sorting_algorithms.md

Latest commit

 

History

History
69 lines (49 loc) · 2.88 KB

05_sorting_algorithms.md

File metadata and controls

69 lines (49 loc) · 2.88 KB

Chapter 05: Sorting Algorithms

When you read a directory with readdir, the files come out in "inode order" or potentially hash order, depending on the filesystem (ext4, APFS, etc.). It looks chaotic to humans.

Humans like alphabetical order. Or sometimes, they want to see what changed most recently (-t).

Qsort

We don't need to invent a sorting algorithm (unless you really want to implement Merge Sort for fun). The C standard library gives us qsort, which is Quick Sort.

void qsort(void *base, size_t nmemb, size_t size,
           int (*compar)(const void *, const void *));

This function is a powerhouse. It sorts an array in place. We just need to provide:

  1. An array of our file entries (we shouldn't be using a linked list if we want to sort easily!).
  2. A comparator function.

The Comparator

The comparator is a function that takes two items (A and B) and returns:

  • < 0 if A comes before B
  • 0 if A equals B
  • > 0 if A comes after B

Criteria 1: Alphabetical (Lexicographical)

This is simple case-insensitive (usually) string comparison. strcasecmp(a->name, b->name) does most of the work.

Caution: We usually want to ignore leading dots so that .config sits near config.

Criteria 2: Modification Time (-t)

We want newest files first. We compare a->msg_stats.st_mtime vs b->msg_stats.st_mtime. Since we want newest first (descending), we reverse the logic: return B - A.

Wait, st_mtime is actually seconds. But modern filesystems have nanosecond precision! On Linux/Mac, struct stat usually has fields like st_mtimespec.tv_nsec. If the seconds are equal, we must check the nanoseconds to be accurate.

Criteria 3: Reverse (-r)

The user can combine -r with anything.

  • ls -r: Reverse alphabetical.
  • ls -rt: Reverse time (oldest first).

We can handle this globally. If the -r flag is set, we just multiply the final result of our comparator by -1. Simple, elegant solution.

Stability

qsort is not guaranteed to be stable. A stable sort preserves the relative order of "equal" items. Does this matter for ls? If two files have the exact same modification time to the nanosecond, and we sort by time... which one comes first? It is undefined. Usually, this is acceptable for ls. If we wanted perfect determinism, we could add a tie-breaker: "If times are equal, sort by name."

Implementation Strategy

We will likely need to store all our directory entries in a dynamic array (a growable buffer) instead of printing them on the fly.

  1. opendir
  2. Loop readdir:
    • lstat the file
    • Add to FileInfo array (realloc if full)
  3. closedir
  4. qsort the array
  5. Pass the sorted array to our formatting function

This "buffer everything" approach uses more memory than streaming, but for 99.9% of directories with <10,000 files, the memory usage is negligible (measurable in kilobytes).

Next up: The complex world of user rights.