📶 धडा 07 — Sorting: वर्गाला उंचीनुसार रांगेत लावणे

📍 तुम्ही इथे आहात: 12 पैकी धडा 07 · पुढे: lesson-08-binary-search

📦 या ब्रँचमध्ये काय आहे

धडे 01–07. comparison counters असलेले चार sorts, त्याच 2,000 उंचींवर वेळ मोजलेले, आणि तरीही तुम्ही sorted() का बोलावता याचे कारण.

dsa/algorithms.py — bubble_sort, insertion_sort, merge_sort, quick_sort, प्रत्येक (sorted, comparisons) परत करतो
dsa/demo.py — sort

🧒 5 वर्षांच्या मुलाला समजावल्यासारखे

वर्गाला उंचीनुसार रांगेत लावा. Bubble: रांगेतून चाला, चुकीच्या क्रमातल्या कोणत्याही दोन शेजाऱ्यांची अदलाबदल करा, एखाद्या फेरीत कोणाचीच अदलाबदल होईपर्यंत पुन्हा करा — हळू, प्रत्येक फेरी म्हणजे पूर्ण रांग. Insertion: पुढचे मूल घ्या आणि त्याला मागे त्याच्या जागेपर्यंत न्या — रांग आधीच जवळजवळ बरोबर असेल तर जलद. Merge: वर्गाचे दोन अर्धे करा, प्रत्येक अर्धा क्रमाने लावा (पुन्हा अर्धे करून…), मग दोन क्रमाने लावलेल्या रांगा एकत्र गुंफा. Quick: एक मूल निवडा, त्याच्यापेक्षा बुटके सगळे डावीकडे, उंच उजवीकडे, प्रत्येक बाजूला पुन्हा करा. शेवटचे दोन खूपच कमी काम करतात — हेच n log n विरुद्ध n².

🗺️ आकृती

flowchart TD
  A["[5 2 8 1 9 3]"] --> B["[5 2 8]"] & C["[1 9 3]"]
  B --> B1["[2 5 8]"] ; C --> C1["[1 3 9]"]
  B1 & C1 --> M["merge → [1 2 3 5 8 9]"]

❓ काय

Sort	वेळ	Space	Stable	टिपा
bubble	O(n²)	O(1)	हो	फक्त धडा, साधन कधीच नाही
insertion	O(n²), जवळजवळ sorted असेल तर O(n)	O(1)	हो	अगदी लहान किंवा जवळजवळ sorted साठी उत्तम
merge	नेहमी O(n log n)	O(n)	हो	linked lists, external sorting
quick	सरासरी O(n log n), worst O(n²)	O(log n)	नाही	प्रत्यक्षात सर्वात जलद in-place
Timsort (`sorted`)	O(n log n), runs वर O(n)	O(n)	हो	merge + insertion; Python आणि Java हेच देतात

Stable = समान उंचीचे विद्यार्थी आपला मूळ क्रम टिकवतात; एकामागून एक keys ने sort करता तेव्हा हे महत्त्वाचे (sorted(rows, key=…) दोनदा).
Comparison sorts O(n log n) पेक्षा चांगले करू शकत नाहीत; लहान integers साठी counting/radix sort त्याला हरवतो.
एकदा sort करा, मग binary search (धडा 08) किंवा sweep (धडा 12).

🤔 का

कामावर तुम्ही कधीच sort लिहिणार नाही, आणि रोज एक बोलावाल. आकार माहीत असले की loop च्या आतला sorted() हा तुम्हाला न दिसलेला n² कधी आहे ते कळते, आणि heap (धडा 09) किंवा dict (धडा 05) sorting पूर्णच कधी टाळतो तेही.

🔧 कसे (या repo मध्ये)

प्रत्येक sort एक list घेतो आणि नवी list व तिचा comparison count परत करतो; demo.py sort चारही sorts त्याच random 2,000 उंचींवर चालवतो, ते sorted शी जुळतात हे assert करतो, मग जवळजवळ sorted रांगेवर insertion विरुद्ध bubble दाखवतो, आणि Timsort चा वेळ.

🧪 करून पाहा

python3 dsa/demo.py sort
python3 - <<'EOF'
import sys, random; sys.path.insert(0, "dsa"); from algorithms import quick_sort, merge_sort
worst = list(range(2000))                      # already sorted: our quick_sort picks the middle pivot, so it is fine — try the first element as pivot and watch n²
print("quick on sorted input:", quick_sort(worst)[1], "comparisons")
rows = [("Katrina", "3A", 150), ("Aishwarya", "3A", 150), ("Dipika", "3B", 140)]
print(sorted(sorted(rows, key=lambda r: r[0]), key=lambda r: r[2]))   # stable: ties keep the name order
EOF

✅ तपासा — तुम्हाला काय दिसायला हवे

Bubble ~2,000,000 comparisons, insertion ~1,000,000, merge ~19,000, quick ~13,000 — आणि milliseconds या counts प्रमाणेच येतात; जवळजवळ sorted रांगेवर bubble आणि insertion दोघांनाही ~2,000 लागतात. sorted() सगळ्यात जलद आहे. sorted input वर quick: ~19,000 comparisons (मधला pivot त्याला वाचवतो). stable दुहेरी sort 150 उंचीवर Aishwarya ला Katrina च्या आधी ठेवतो.

🏁 तुम्ही आत्ताच काय सिद्ध केले

n = 2,000 ला n log n विरुद्ध n² हा शंभर पटीचा फरक आहे — तुम्ही तो मोजलात — आणि कोणते sorts stable आहेत आणि ते का महत्त्वाचे आहे हे तुम्हाला माहीत आहे.

⚠️ नेहमीच्या चुका

loop च्या आत sorting (n² log n), जिथे बाहेर एक sort पुरेसा होता.
sort unstable आहे असे समजून गरज नसलेले tie-breakers लिहिणे (Python चा stable आहे).
sorted input वर पहिल्या element ला pivot घेऊन quick sort लिहिणे: O(n²).

🏭 प्रत्यक्ष वापरात हे का महत्त्वाचे: database मधला ORDER BY, log pipelines, leaderboards, आणि request handler मधला प्रत्येक sorted(...) — तुम्ही आकार आणि stability च्या हमीवरच अवलंबून असता.

⏭️ पुढे

धडा 08 — binary search: क्रमाने लावलेली नोंदवही, आणि उत्तरावर search.

📶 Lesson 07 — Sorting: lining up the class by height

📍 You are here: Lesson 07 of 12 · Next: lesson-08-binary-search

📦 What's in this branch

Lessons 01–07. Four sorts with comparison counters, timed on the same 2,000 heights, and the reason you call sorted() anyway.

dsa/algorithms.py — bubble_sort, insertion_sort, merge_sort, quick_sort, each returning (sorted, comparisons)
dsa/demo.py — sort

🧒 Explain like I'm 5

Line the class up by height. Bubble: walk the line, swap any two neighbours in the wrong order, repeat until a walk swaps nobody — slow, every walk is the whole line. Insertion: take the next child and walk them back to their place — quick if the line was nearly right already. Merge: split the class in half, sort each half (by splitting again…), then zip two sorted lines together. Quick: pick one child, everyone shorter to the left, taller to the right, repeat on each side. The last two do far less work — that is n log n against n².

🗺️ Diagram

flowchart TD
  A["[5 2 8 1 9 3]"] --> B["[5 2 8]"] & C["[1 9 3]"]
  B --> B1["[2 5 8]"] ; C --> C1["[1 3 9]"]
  B1 & C1 --> M["merge → [1 2 3 5 8 9]"]

❓ What

Sort	Time	Space	Stable	Notes
bubble	O(n²)	O(1)	yes	a lesson, never a tool
insertion	O(n²), O(n) nearly sorted	O(1)	yes	great for tiny or nearly sorted
merge	O(n log n) always	O(n)	yes	linked lists, external sorting
quick	O(n log n) avg, O(n²) worst	O(log n)	no	fastest in-place in practice
Timsort (`sorted`)	O(n log n), O(n) on runs	O(n)	yes	merge + insertion; what Python and Java ship

Stable = equal heights keep their original order; matters when you sort by one key after another (sorted(rows, key=…) twice).
Comparison sorts cannot beat O(n log n); counting/radix sort beats it for small integers.
Sort once, then binary search (lesson 08) or sweep (lesson 12).

🤔 Why

You will never write a sort at work, and you will call one every day. Knowing the shapes tells you when sorted() inside a loop is the n² you did not see, and when a heap (lesson 09) or a dict (lesson 05) avoids sorting at all.

🔧 How (in this repo)

Each sort takes a list and returns a new one plus its comparison count; demo.py sort runs all four on the same random 2,000 heights, asserts they agree with sorted, then shows insertion versus bubble on a nearly sorted line, and Timsort's time.

🧪 Try it

python3 dsa/demo.py sort
python3 - <<'EOF'
import sys, random; sys.path.insert(0, "dsa"); from algorithms import quick_sort, merge_sort
worst = list(range(2000))                      # already sorted: our quick_sort picks the middle pivot, so it is fine — try the first element as pivot and watch n²
print("quick on sorted input:", quick_sort(worst)[1], "comparisons")
rows = [("Katrina", "3A", 150), ("Aishwarya", "3A", 150), ("Dipika", "3B", 140)]
print(sorted(sorted(rows, key=lambda r: r[0]), key=lambda r: r[2]))   # stable: ties keep the name order
EOF

✅ Verify — what you should see

Bubble ~2,000,000 comparisons, insertion ~1,000,000, merge ~19,000, quick ~13,000 — and the milliseconds follow the counts; on the nearly sorted line both bubble and insertion need ~2,000. sorted() is the fastest of all. Quick on sorted input: ~19,000 comparisons (the middle pivot saves it). The stable double sort keeps Aishwarya before Katrina at 150.

🏁 What you just proved

n log n versus n² is a factor of a hundred at n = 2,000 — you measured it — and you know which sorts are stable and why that matters.

⚠️ Common mistakes

Sorting inside a loop (n² log n) when one sort outside would do.
Assuming sort is unstable and writing tie-breakers you do not need (Python's is stable).
Implementing quick sort with the first element as pivot on sorted input: O(n²).

🏭 Why this matters in production: ORDER BY in a database, log pipelines, leaderboards, and every sorted(...) in a request handler — the shape and the stability guarantee are what you are relying on.

⏭️ Next

Lesson 08 — binary search: the sorted register, and searching on the answer.

← Previousrecursion Next →binary search

This page is the lesson's README from the lesson-07-sorting branch, shown here so the whole School stays on one site. Code files open on GitHub at the same branch.