### Day 28: Sorting Techniques

Hello Dear Students,
Hope you all are doing good.

Aaj hum sorting techniques ke baare mein study karenge..

Let's get started...

SORTING - Sorting means data ko ek particular order mein arrange kar dena. Jo bhi data hota hai wo hum data structure mein store kara dete hain but jab us data ko process kiya jata hai then wo difficult ho jata hai, so agar hum wohi data ko proper arrange kar kr store karayenge, then , complexity less ho jayegi and easy ho jayega data ko process karna.

Agar data numeric data hoga then wo ascending or descending order mein arrange kiya jayega.
Agar data character data hoga then wo alphabetic order mein arrange kiya jayega.

Sorting ke liye basically 2 techniques mein data ko sort kiya jata hai-

1. INTERNAL SORTING
a. Selection Sort
b. Bubble Sort
c. Insertion Sort
d. Merge Sort
e. Quick Sort
f. Heap Sort
h. Shell Sort

2. EXTERNAL SORTING
a. Sorting with Tapes
b. Sorting with Disk

Internal Sorting - Agar less size data ko sort karna hai then internal sorting is the best. Internal sorting takes place in main memory of the computer but it is not implemented with secondary storage. It is of following types-

1. SELECTION SORT - Selection sort mein hum sorting karne ke liye minimum values ko consider karte hain. Poori list mein hum dekhte hain ki jo bhi minimum value hai wo swap ho jati hai. For example,

 60 30 55 5 25

Ye above list ko humne sort karna hai selection sort ki help se, So hum selection sort mein sabse pehle dekhte hain ki minimum value konsi hai and then swap kar dena.
Sabse first 60, so hum 60 ko compare karte hain,
• 60 ko 30 se compare karenge so 30 is minimum value, fir hum 30 se compare karenge aage sab ko
• 30 ko 55 se compare karenge so 30 again minimum value, so 30 se hi dubara compare karenge
• 30 ko 5 se compare kiya, 5 is minimum so ab 5 minimum a gya then aage 5 ko 25 se karenge, 5 again minimum
• So, 5 minimum hai and thus 5 ko 60 se swap kar denge because minimum value first mein hoti hai.
 5 30 55 60 25

• Ab 60 ki jagah 5 a gya and 5 ki jagah 60 a gya.
• Ab hum baaki data ko sort karenge so again compare 30 with 55, 30 is minimum so 30 ko compare karenge aage.
• 30 ko 60 se compare kiya, 30 is minimum, so 30 ko ab 25 se compare karenge, 25 is minimum .
• So, 25 is minimum and hum 30 ko 25 ke saath swap kar denge.
 5 25 55 60 30

• Ab 55 ko compare karenge 60 se, 55 is minimum so 55 ko aage compare karenge
• 55 ko 30 se compare karenge, 30 is minimum then 30 ko 55 se swap karenge.
 5 25 30 60 55

• Ab 60 ko 55 se compare karenge, 55 is minimum so hum 60 and 55 ko swap kar denge. Then, our list is proper sorted with the selection sort.
 5 25 30 55 60

2. BUBBLE SORT - Bubble sort is very basic and simple sorting technique. Isme hum linearly sorting karte hain. Ek element ko uske saath wale element se compare karna and then sort karna. Isme hum pass 1, pass 2 se karte hain. For example,

 60 30 55 5 25

In pass 1:-
• Isme hum saath saath compare karke swap karte rahenge.
• 60 ko 30 se compare, 60 is larger than 30, so ise swap kar denge.
 30 60 55 5 25
• Now 60 ko 55 se compare karenge, again 60 is larger than 55, so swap 55 and 60.
 30 55 60 5 25
• Ab 60 ko 5 se compare karenge, again 60 is larger so swap 5 and 60.
 30 55 5 60 25
• Ab 60 ko 25 se compare karenge, again 60 is larger, so swap 25 and 60.
 30 55 5 25 60

In pass 2:-
Again same procedure,
• 30 ko 55 se compare karenge, 30 is smaller, so no swapping.
• Then 55 ko 5 se compare karenge, 55 is larger so swap 5 and 55.
 30 5 55 25 60
• Now, compare 55 with 25, 55 is larger, so swap 25 and 55.
 30 5 25 55 60
• Now, 55 ko 60 se compare karenge, 55 is smaller so no swapping. Pass 2 ends.
In pass 3:-
Again same procedure,
• 30 ko 5 se compare karenge, 30 is larger so swap 5 and 30.
 5 30 25 55 60
• Now, compare 30 with 25, 30 is larger so swap 30 and 25.
 5 25 30 55 60
• Now, compare 30 and 55, 30 is smaller so no swapping,
• Compare 55 with 60, 55 is smaller so no swapping.
So, pass 3 mein hume sorted list mil chuki hai with bubble sort.

3. INSERTION SORT - Insertion Sort mein hum sabse pehle 2nd element ko 1st element se compare karte hain, then 3rd element ko first 2 se sort karke compare karte hain. For example,

 60 30 55 5 25
• Sabse pehle hum 2nd element ko 1st element se compare karenge, so, compare 60 with 30, 60 is larger so swap 30 and 60.
 30 60 55 5 25
• Now, 3rd element ko first 2 se compare karenge, sabse pehle 60 ko 55 se compare karenge and then 30 se. So, compare 60 with 55, 60 is larger so swap 60 and 55.
 30 55 60 5 25
• Ab hum 55 ko 30 se compare karenge, 30 is smaller so no swapping.
• Now 4th element ko first 3 elements se compare karenge, so 5 ko 60, 55, and 30 se compare karenge.
• 5 ko 60 se compare karenge, 60 is larger so swap 5 and 60.
 30 55 5 60 25
• Now compare 5 with 55, 55 is larger so swap 55 and 5.
 30 5 55 60 25
• Now compare 5 with 30, 30 is larger so swap 30 and 5.
 5 30 55 60 25
• Now compare 5th element with first 4 elements, means compare 25 with 60,55,30, and 5.
• 25 ko 60 se compare karte hain, 60 is larger so swap 60 and 25.
 5 30 55 25 60
• Now, 25 ko 55 se compare karenge, 55 is larger so swap 25 and 55.
 5 30 25 55 60
• Now compare 25 with 30, 30 is larger so again swap 25 with 30.
 5 25 30 55 60
• Now, compare 25 with 5, 5 is smaller so no swapping.
• Thus, the list is sorted properly with the insertion sort.

4. MERGE SORT - Merge sort mein hum divide and conquer technique ko use karte hain. Isme hum sabse pehle poori list ko 2 parts mein divide kar lete hain then wo dono parts ko again divide karte rehte hain, then use sort karke combine kar dete hain. For example,

 60 30 55 5 25

This is our list jise hum sort karenge. So, sabse pehle is list ko 2 parts mein divide karenge. Divide karne ke liye upper bound+lower bound/2. Here, (1+4)/2= 5/2 which means hum iska floor value lenge, 5/2= 2.5 and floor value is 3. So hum is list ko 3:2 mein divide karenge.

 60 30 55

So, ab yeh humari left list ho gyi hum ise sort karenge, then is list ko bhi divide karenge so 60, 30 and 55 mein. Compare 60 and 30, 60 is larger so swap 60 and 30. Now, compare 60 with 55 no swap, then 55 with 60, 60 is larger so swap 55 and 60. Thus it becomes,

 30 55 60

Ab is list ke right part ko sort karenge, So 5 and 25, 5 is smaller than 25 so no swapping.

Now, divide kar diya and sorting bhi ho gayi ab ise combine karna hai such that all elements get sorted.

 30 55 60 5 25

List ko combine karne ke baad aise list ho jayegi now ise sort kar kr store karenge.

 5 25 30 55 60

So, this is proper sorted list with merge sort.

5. QUICK SORT - Quick sort mein bhi divide and conquer technique use hoti hai. But ye merge sort se different hai. Ye question exam mein a jata hai so ise proper understand karenge. Quick sort mein hum sabse pehle sorting karte hain, 1st element ki last element se comparison and swapping and then 2nd element ki 2nd last element se and so on. Then ek aisa element middle mein a jata hai jiske left mein sabhi smaller elements hote hain and right mein sabhi larger elements. Then use divide and conquer se sort kiya jata hai. For example,

 60 30 55 5 25
• Now, compare 1st element with last element, means 60 ko 25 se compare karnge, 60 is larger so swap 60 and 25.

 25 30 55 5 60
• Now, compare 2nd element with next last element. means compare 30 with 5, 30 is larger so swap 30 and 5.
 25 5 55 30 60
• Now, 55 ko 30 se compare karenge, 55 is larger so swap 55 and 30.
 25 5 30 55 60

Ab hamara middle mein 30 a gya so ab 30 se left mein sabhi small hain and right mein 30 se larger hain sabhi values. So, ab hum isko divide and conquer technique se karenge.
Ab hum 25, 5 and 30 ko ek list bana kar sort karenge and then 55 and 60 ko.
Then sort hone ke baad combine kar denge.

 5 25 30 55 60

This is proper sorted list with quick sort.

6. HEAP SORT - Heap sort heap tree par sorting ki technique hai. Heap tree binary tree hota hai which is Max heap or Min heap. So, max heap mein hum parent node ko child node se larger sort karte hain and then Min heap mein hum parent node ko child node se smaller sort karte hain.

Max heap mein parent node is larger than its child nodes.
Min heap mein parent node is smaller than its child nodes.

Above is a Max heap tree jisse humne sort kiya hai, above list ke according.

• Radix sort quickest sorting method hai means isme time bahut less lagta hai but space bahut jyada consume hoti hai.
• It is also known as Bucket Sort, because radix sort stacks ko consider karti hai and sabhi value ko stack mein store karaya jata hai. Sorting ke liye push and pop operaion ko perform kiya jata hai.
•  Radix sort works only on positive numbers and not on negative numbers.
• Jitne values honge hum utne hi packets mein store karenge.
• Agar hum numbers data ko sort karenge to, 0 to 9 radix ko use karenge means total 10 radix.
• Agar hum alphabetic data ko sort karenge then 26 radix ko use karenge , A to Z.
• Isme bhi hum pass 1, pass 2, hote hain jisse sorting perform ki jati hai.

8. SHELL SORT - Shell sort was developed by Donald Shell. Shell sort is same like bubble sort but has a very small difference, shell sort mein hum distance ko consider karte hain. Uske baad 1st element ko distance element se compare karte hain and then next. For example,

 60 30 55 5 25

distance = 5/2= 2.5, which the floor value is 3.

In pass 1,
• Compare 60 with 5(the distance is 3 means 60 ko hum jis element se compare karenge usme 3 ka distance hona chaiye, so 60 ko hum 5 se compare karenge then the distance is 3), 60 is larger so swap 60 and 5.
 5 30 55 60 25
• Now, compare 30 with 25, 30 is larger so swap 30 and 25.
 5 25 55 60 30

In pass 2,
d= d/2 = 3/2 = 1.5, the floor value is 2 so distance is now 2.
• Compare 5 with 55( because distance should be 2, so its distance is 2), 5 is smaller so no swapping.
• Compare 25 with 60, 25 is smaller so no swapping.
• Compare 55 with 30, 55 is larger so swap 55 and 30.
 5 25 30 60 55

In pass 3,
d= d/2 = 2/2 = 1.
• Compare 5 with 25, 5 is smaller so no swapping.
• Compare 25 with 30, 25 is smaller so no swapping.
• Compare 30 with 60, 30 is smaller so no swapping.
• Compare 60 with 55, 60 is larger so swap 60 and 55.
 5 25 30 55 60

So, this is our proper sorted list with the shell sort.

External sorting basically use ki jati hai jab data is too large. It is implemented using secondary storage, and also auxiliary storage.

Best of Luck Students,
Do visit our website regularly for more content and for daily tests.

Regards,
UGC NET EXPERTS