quicksort - 2025 ACF Fall - Buzzpoints App

Question

Early implementations of this algorithm exhibited its worst-case runtime on sorted arrays, which can be avoided using the “median-of-three” rule. For 10 points each:

[10m] Name this divide-and-conquer algorithm that repeatedly partitions an array about a pivot, moves smaller values to the left of the pivot, and moves larger values to the right of the pivot.

ANSWER: quicksort [or partition-exchange sort; reject “exchange sort”]

[10e] A sorted list admits a search algorithm named for this word that also works by repeated partition. Computer science typically works in a base with this name, which is synonymous with base-2.

ANSWER: binary [accept binary search]

[10h] The parity of k partitions of a string of 2 to the k binary digits is checked in an “extended” error correction code named for this American computer scientist, which is robust when his namesake “distance” is at most 1.

ANSWER: Richard Hamming [accept Hamming code or extended Hamming code; accept Hamming distance]

<Editors, Other Science>

Back to bonuses

Summary


Northern California	Main	Y	4	15.00	100%	25%	25%
Southern California	Main	Y	7	18.57	100%	57%	29%
Eastern Canada (1)	Main	Y	5	10.00	80%	0%	20%
Eastern Canada (2)	Main	Y	9	14.44	100%	33%	11%
Florida	Main	Y	4	10.00	75%	25%	0%
Great Lakes	Main	Y	12	16.67	100%	33%	33%
Lower Mid-Atlantic	Main	Y	9	11.11	100%	11%	0%
Upper Mid-Atlantic	Main	Y	10	13.00	90%	40%	0%
Upper Mid-Atlantic	Main	Y	2	25.00	100%	100%	50%
Midwest	Main	Y	9	16.67	100%	33%	33%
North	Main	Y	4	17.50	100%	50%	25%
Northeast	Main	Y	11	10.91	82%	18%	9%
Pacific	Main	Y	8	8.75	88%	0%	0%
South Central	Main	Y	7	14.29	100%	14%	29%
Southeast	Main	Y	13	13.85	100%	31%	8%
UK (North)	UK	Y	5	22.00	100%	60%	60%
UK (South)	UK	Y	7	20.00	100%	43%	57%
Upstate NY	Main	Y	5	14.00	100%	40%	0%

Data


Claremont C	UC Irvine	0	10	0	10
UC Santa Barbara	UCLA C	0	10	0	10
USC B	UCLA A	10	10	10	30
Claremont B	UCLA B	10	10	10	30
UCLA D	Claremont A	0	10	0	10
UCSD B	UCSD A	10	10	0	20
UCLA E	USC A	10	10	0	20
Carleton A	McGill E	0	10	10	20
McGill C	McGill A	0	10	0	10
Ottawa D	McGill B	0	10	0	10
Ottawa A	Ottawa B	0	0	0	0
Ottawa C	Carleton B	0	10	0	10
Berkeley Mighty Miner	Berkeley Archer Queen	0	10	10	20
Stanford B	Berkeley Boss Bandit	10	10	0	20
Berkeley Little Prince	Berkeley Skeleton King	0	10	0	10
Stanford A	UCSC	0	10	0	10
Florida B	Florida Tech A	0	10	0	10
ERAU Daytona A	Florida State A	10	0	0	10
South Florida A	Florida Tech B	0	10	0	10
UCF A	Florida A	0	10	0	10
CWRU B	CWRU A	10	10	10	30
Kentucky	Pittsburgh	0	10	10	20
Ohio State A	Louisville B	0	10	0	10
Louisville C	Michigan State D	0	10	0	10
Michigan A	Michigan B	10	10	10	30
Michigan C	CWRU D	10	10	0	20
Michigan D	CWRU C	0	10	0	10
Michigan State A	Louisville A	10	10	0	20
Ohio State B	Michigan State B	0	10	10	20
Ohio State C	Louisville D	0	10	0	10
Michigan State C	Ohio State D	0	10	0	10
WVU A	WVU B	0	10	0	10
NCSU A	William & Mary A	0	10	0	10
Liberty B	NCSU B	0	10	0	10
Liberty C	Tusculum A	0	10	0	10
Virginia Tech A	UNC A	0	10	0	10
UNC B	UNC C	0	10	0	10
Virginia A	Virginia Tech B	0	10	0	10
UNC D	Virginia Tech C	10	10	0	20
William & Mary B	JMU A	0	10	0	10
William & Mary C	Liberty A	0	10	0	10
Brock A	Queen's A	0	10	0	10
Toronto E	Guelph A	10	10	0	20
Toronto F	McMaster C	0	10	0	10
Waterloo A	Toronto A	10	10	10	30
Toronto C	Toronto B	0	10	0	10
Toronto D	McMaster A	0	10	0	10
Toronto I	Toronto H	10	10	0	20
Toronto G	Waterloo B	0	10	0	10
McMaster B	Waterloo C	0	10	0	10
Lehigh A	Rutgers B	10	10	0	20
Maryland B	George Mason A	10	10	10	30
George Mason C	Columbia B	10	0	0	10
Johns Hopkins	George Mason B	10	10	0	20
NYU B	Lehigh B	0	10	0	10
Maryland A	Rutgers A	10	10	0	20
Maryland C	NYU A	0	10	0	10
Columbia A	Princeton	0	10	0	10
Rowan	Vassar B	10	10	0	20
NYU C	Rutgers C	0	10	0	10
Penn	Rutgers D	0	10	0	10
Vassar A	Stony Brook	0	10	0	10
WashU Grizzlers	Chicago A	0	10	0	10
Purdue A	Chicago B	10	10	10	30
Illinois Champaign	Iowa B	0	10	10	20
Indiana B	Illinois Orange	0	10	0	10
Purdue B	Illinois Canada	10	10	0	20
Purdue C	Iowa A	10	10	0	20
Purdue D	Rose-Hulman A	0	10	0	10
WashU Grolars	Indiana A	0	10	0	10
William Woods University A	Illinois Blue	0	10	10	20
Minnesota	Wisconsin B	0	10	0	10
Macalester	St. Thomas	10	10	0	20
Iowa State	Wisconsin A	10	10	10	30
Wisconsin C	Michigan Tech	0	10	0	10
Boston University B	Amherst B	10	10	10	30
Boston College A	Brandeis Mozart	0	10	0	10
Dartmouth A	Brown A	0	10	0	10
Brown B	MIT A	0	0	0	0
Brandeis Beethoven	Harvard	0	10	0	10
Alberta A	Washington Atlantic	0	10	0	10
Alberta B	Washington Chum	0	10	0	10
Arizona State A	Washington Sockeye	0	10	0	10
Texas	British Columbia B	0	10	0	10
British Columbia C	Washington State	0	0	0	0
Washington Chinook	Washington Steelhead	0	10	0	10
British Columbia A	Washington Coho	0	10	0	10
Washington Pink	Washington Masu	0	10	0	10
Tulsa B	Central Oklahoma B	0	10	10	20
Kansas State B	Kansas State A	0	10	0	10
Murray State College B	Murray State College A	0	10	0	10
Nebraska A	Nebraska B	0	10	0	10
Nebraska C	Oklahoma	0	10	0	10
Rose State	Harding	10	10	0	20
Tulsa A	Central Oklahoma A	0	10	10	20
Vanderbilt A	Alabama A	0	10	0	10
Auburn A	Tennessee Tech	0	10	0	10
Auburn C	Vanderbilt C	0	10	0	10
Clemson A	Chipola College	0	10	0	10
Clemson B	Montevallo	10	10	0	20
Clemson C	Sewanne	0	10	0	10
Emory A	Georgia A	10	10	0	20
Georgia Tech B	Auburn B	10	10	0	20
Georgia Tech C	Georgia Tech A	0	10	0	10
Georgia Tech E	Georgia Tech F	0	10	0	10
Mississippi State A	Vanderbilt B	0	10	0	10
Tennessee A	South Carolina A	0	10	0	10
Georgia Tech D	Tennessee B	10	10	10	30
Amherst A	Tufts A	0	10	0	10
Vermont A	Tufts B	0	10	0	10
Boston University A	UConn A	10	0	0	10
Williams A	Vermont B	0	10	0	10
Dartmouth B	Williams B	0	10	0	10
Williams C	Dartmouth C	0	10	0	10
Durham B	Edinburgh B	10	10	10	30
Durham D	Edinburgh D	10	10	0	20
Durham A	Edinburgh C	0	10	10	20
Edinburgh A	Sheffield A	10	10	0	20
Sheffield B	Durham C	0	10	10	20
Cambridge A	Southampton	0	10	10	20
Cambridge C	Cambridge E	0	10	0	10
Imperial A	Cambridge D	10	10	10	30
Imperial B	Birmingham	10	10	10	30
Bristol	Imperial C	10	10	10	30
LSE	Warwick	0	10	0	10
Oxford	Imperial D	0	10	0	10
Binghamton C	Rochester	0	10	0	10
Cornell D	Cornell A	10	10	0	20
Cornell C	Binghamton B	10	10	0	20
ESF	RIT A	0	10	0	10
Binghamton A	RIT B	0	10	0	10