Skip to main content

Unsorted Sorted

This page is a generated reference surface for selective reading. It exists to keep the learner apps guide-first while still preserving source access.

Learning objectives​

  • Explain the main ideas and vocabulary in Unsorted Sorted.
  • Work through the source examples for Unsorted Sorted without depending on raw chunk order.
  • Use Unsorted Sorted as selective reference when learner modules point back to The Algorithm Design Manual.

Prerequisites​

  • None curated yet.

Module targets​

  • module-02-sorting-searching-structures

AI companion modes​

  • Explain simply
  • Socratic tutor
  • Quiz me
  • Challenge my understanding
  • Diagnose my confusion
  • Generate extra practice
  • Revision mode
  • Connect forward / backward

Source-of-truth note​

This unit is anchored to The Algorithm Design Manual and the source chapter "Unsorted Sorted". Use external resources only to clarify, extend, or modernize details without replacing the chapter's conceptual spine.

External enrichment​

No chapter-specific enrichment resources are curated yet. Add them in the unit manifest when a source clearly improves learning.

Source provenance​

  • Primary source: The Algorithm Design Manual
  • Source chapter: Unsorted Sorted
  • Raw source file: 031-unsorted-sorted.md

Merged source​

Unsorted Sorted​

Unsorted Sorted

Unsorted Sorted​

Dictionary operation array array

Search(L, k) O(n) O(logn)​

Insert(L, x) O(1) O(n)

Delete(L, x) O(1)∗ O(n)

Successor(L, x) O(n) O(1)

Predecessor(L, x) O(n) O(1)

Minimum(L) O(n) O(1)

Maximum(L) O(n) O(1)

We must understand the implementation of each operation to see why. First, we discuss the operations when maintaining anunsortedarrayA.

  • Searchis implemented by testing the search keykagainst (potentially) each

element of an unsorted array. Thus, search takes linear time in the worst case, which is when keykis not found inA.

  • Insertion is implemented by incrementing n and then copying item x to

the nth cell in the array, A[n]. The bulk of the array is untouched, so this operation takes constant time.

  • Deletion is somewhat trickier, hence the superscript(∗) in the table. The
definition states that we are given a pointer xto the element to delete, so​

we need not spend any time searching for the element. But removing thexth element from the arrayAleaves a hole that must be filled. We could fill the hole by moving each of the elements A[x+ 1] to A[n] up one position, but this requiresΘ(n) time when the first element is deleted. The following idea is better: just write over A[x] with A[n], and decrement n. This only takes constant time.

  • The definition of the traversal operations, Predecessor andSuccessor, refer

to the item appearing before/after xin sorted order. Thus, the answer is not simplyA[x−1] (or A[x+ 1]), because in an unsorted array an element's physical predecessor (successor) is not necessarily its logical predecessor (successor). Instead, the predecessor of A[x] is the biggest element smaller than

A[x]. Similarly, the successor ofA[x] is the smallest element larger thanA[x].

Both require a sweep through allnelements ofAto determine the winner.

  • MinimumandMaximumare similarly defined with respect to sorted order,

and so require linear sweeps to identify in an unsorted array.

Implementing a dictionary using asortedarray completely reverses our notions of what is easy and what is hard. Searches can now be done inO(logn) time, using binary search, because we know the median element sits inA[n/2]. Since the upper and lower portions of the array are also sorted, the search can continue recursively on the appropriate portion. The number of halvings of nuntil we get to a single element is⌈lgn⌉.

The sorted order also benefits us with respect to the other dictionary retrieval operations. The minimum and maximum elements sit inA[1] and A[n], while the predecessor and successor toA[x] are A[x−1] andA[x+ 1], respectively.

Insertion and deletion become more expensive, however, because making room for a new item or filling a hole may require moving many items arbitrarily. Thus both become linear-time operations.

Take-Home Lesson: Data structure design must balance all the different op-​

erations it supports. The fastest data structure to support both operationsA andBmay well not be the fastest structure to support either operationAor

B.

Stop and Think: Comparing Dictionary Implementations (II)

Problem: What is the asymptotic worst-case running times for each of the seven​

fundamental dictionary operations when the data structure is implemented as

  • A singly-linked unsorted list.

  • A doubly-linked unsorted list.

  • A singly-linked sorted list.

  • A doubly-linked sorted list.

Solution: Two different issues must be considered in evaluating these implementa-​

tions: singly- vs. doubly-linked lists and sorted vs. unsorted order. Subtle operations are denoted with a superscript:

Singly Double Singly Doubly

Dictionary operation unsorted unsorted sorted sorted

Search(L, k) O(n) O(n) O(n) O(n)

Insert(L, x) O(1) O(1) O(n) O(n)

Delete(L, x) O(n)∗ O(1) O(n)∗ O(1)

Successor(L, x) O(n) O(n) O(1) O(1)

Predecessor(L, x) O(n) O(n) O(n)∗ O(1)

Minimum(L) O(n) O(n) O(1) O(1)

Maximum(L) O(n) O(n) O(1)∗ O(1)

As with unsorted arrays, search operations are destined to be slow while maintenance operations are fast.

  • Insertion/Deletion - The complication here is deletion from a singly-linked

list. The definition of theDeleteoperation states we are given a pointerxto the item to be deleted. But what wereally need is a pointer to the element pointing toxin the list, because that is the node that needs to be changed.

We can do nothing without this list predecessor, and so must spend linear time searching for it on a singly-linked list. Doubly-linked lists avoid this

problem, since we can immediately retrieve the list predecessor ofx.​

Deletion is faster for sorted doubly-linked lists than sorted arrays, because splicing out the deleted element from the list is more efficient than filling the hole by moving array elements. The predecessor pointer problem again complicates deletion from singly-linked sorted lists.

  • Search- Sorting provides less benefit for linked lists than it did for arrays. Bi-

nary search is no longer possible, because we can't access the median element without traversing all the elements before it. What sorted listsdoprovide is quick termination of unsuccessful searches, for if we have not foundAbbottby the time we hitCostellowe can deduce that he doesn't exist. Still, searching takes linear time in the worst case.

  • Traversal operations - The predecessor pointer problem again complicates

implementing Predecessor. The logical successor is equivalent to the node successor for both types of sorted lists, and hence can be implemented in constant time.

  • Maximum- The maximum element sits at the tail of the list, which would

normally requireΘ(n) time to reach in either singly- or doubly-linked lists.

However, we can maintain a separate pointer to the list tail, provided we pay the maintenance costs for this pointer on every insertion and deletion.

The tail pointer can be updated in constant time on doubly-linked lists: on

insertion check whether last->next still equals NULL, and on deletion set

lastto point to the list predecessor of lastif the last element is deleted.

We have no efficient way to find this predecessor for singly-linked lists. So why can we implement maximum inΘ(1) on singly-linked lists? The trick is to charge the cost to each deletion, which already took linear time. Adding an extra linear sweep to update the pointer does not harm the asymptotic complexity ofDelete, while gaining usMaximumin constant time as a reward for clear thinking.

3 3 1 2 2 1 3 1 1 2 2 3

Figure 3.2: The five distinct binary search trees on three nodes