Sorting

Q. What is the difference between internal sorting and external soring?

In internal sorting, we use only RAM for sorting process. Internal sorting is applied on small
dataset.e.g. Bubble sorting, selection sort, insertion sort etc.

External sorting is used when the data being sorted does not fit into the main memory of a
computing device i.e. RAM and hence they must reside in the slower external memory (usually
a hard disc or tape). e.g. Merge sort.

1. Bubble sort:In this technique, two adjacent elements are compared in each pass. In each
pass, the highest number occupies its proper position in the array.

int a[n];

for i=1 to n-1

begin

for j=1 to n-1

begin

if(a[j]>a[j+1]) then

swap(a[j], a[j+1])

endfor

endfor

Pass :1

Comparisons: 4

Input:

1 2 3 4 5

21 14 8 7 3

Output:
 1 2 3 4 5

14 8 7 3 21

Pass :2

Comparisons:3

Input:

1 2 3 4 5

14 8 7 3 21

Output:

1 2 3 4 5

8 7 3 14 21

Pass :3

Comparisons:2

Input:

1 2 3 4 5

8 7 3 14 21

Output:

1 2 3 4 5

7 3 8 14 21

Pass :4

Comparisons:1

Input:
 1 2 3 4 5

7 3 8 14 21

Output:

1 2 3 4 5

3 7 8 14 21

Array is sorted.

In the worst case scenario, the array will be already in descending order. The outer for loop is
for the number of passes. The inner for loop is for the number of comparisons.

Complexity= O(n2)

2. Selection Sort: In selection sort, the smallest value among the unsorted elements of the array
is selected in each pass and inserted to its appropriate position into the array. So in each pass,
the smallest element occupies its proper position in the sorted array.

for i= 1 to n-1
begin
min_loc=i
for j=i+1 to n
begin
if A[j]<A[min_loc] then
begin
min_loc=j
endif
endfor
if min_loc != i then // Not the same element
begin
swap(A[min_loc] , A[i])
endif
endfor

int A[5], n=5;

Pass:1

Comparisons: 4

Input:
 1 2 3 4 5

12 10 6 2 7

Initially, i=1 and also min_loc=1 but later min_loc=4

Swap the value at i and min_loc

Output:

1 2 3 4 5

2 10 6 12 7

Pass:2

Comparisons:3

Input:

1 2 3 4 5

2 10 6 12 7

Intially, min_loc=2

Later, min_loc=3

Output:

1 2 3 4 5

2 6 10 12 7

Pass:3

Comparisons:2

Input:

1 2 3 4 5

2 6 10 12 7

Intially, min_loc=3
Output:

1 2 3 4 5

2 6 7 12 10

Pass:4

Comparisons:1

Input:

1 2 3 4 5

2 6 7 12 10

Intially, min_loc=4

Later, min_loc=5

Output:

1 2 3 4 5

2 6 7 10 12

In the worst case, the array will be in descending order.

=O(n2) because n2 is dominant term

In best case, the array will already be in ascending order. Here also in each pass, we have to
compare the minimum element with rest of all the elements. So complexity is O(n2)

[Link] sort: In this algorithm, we insert each an element onto its proper place in the sorted
array from unsorted array.

int ar[5], n=5

1 2 3 4 5=i

5 4 7 2 13
for i=2 to n // unsorted array

begin

key=A[i] // First element in unsorted array

j=i-1

while j>0 AND A[j]>key

begin

A[j+1]=A[j]

j=j-1

endwhile

A[j+1]=key

endfor

In the worst case condition, the array will already be in descending order. So we need
maximum number of comparisons and swapping.

Complexity= O(n2)

4. Count sort:

Counting Sort Algorithm is an efficient sorting algorithm that can be used for sorting non-
negative elements within a specific range. This sorting technique is based on the
frequency/count of each element to be sorted. Unlike other sorting algorithms, it is not
comparison based sorting. It is not suitable for sorting large data sets. It cannot be applied
on strings.

0 1 2 3 4 5 6 7 8 9

5 7 0 5 2 3 2 2 0 5

Here array, A[10]={5,7,0,5,2,3,2,2,0,5}, n=10.

The largest number in the given array is 7, so let k=7

Count[8]={0}

0 1 2 3 4 5 6 7

0 0 0 0 0 0 0 0

Starting from the index 0 of the given array A, increment the element by 1 in the Count array
at index equal to the element of array A.

0 1 2 3 4 5 6 7

2 0 3 1 0 3 0 1

Update the Count array from second index by adding the current element with the previous
element.

Updated array Count:

0 1 2 3 4 5 6 7

2 2 5 6 6 9 9 10

Now from this Count array, we can find the resultant array say B[10] of same size as A. While
filling values in B array, we should scan the array A from the last index and move towards left
considering updated Count array.

First read the last element of array A which is 5. Move to the index 5 of the updated Count
array. The element at index 5 is 9. Decrement the value by 1 at this index giving 8. Move
to the index 8 of B array and store the element of the array A here and so on.

Final updated Count array:

0 1 2 3 4 5 6 7

0 2 2 5 6 6 9 9
B[10]

0 1 2 3 4 5 6 7 8 9

0 0 2 2 2 3 5 5 5 7

Elements are sorted

Then copy the elements of the array B to array A and display array A.

CountSort(A, n)

Count[8]={0}

for i=0 to n-1

begin

Count[A[i]]++ // Store the frequency of the elements of A in Count array

endfor

for i=1 to k // here, k=7

begin

Count[i]=Count[i]+Count[i-1] // Updated array

endfor

for i=n-1 downto 0 // Traverse original array A in backward direction

begin

B[Count[A[i]]--]=A[i]

endfor

for i=0 to n-1

begin

A[i]=B[i]

endfor

Complexity=O(n+k)
5. Radix sort:

Radix sort is a sorting algorithm that sorts the elements by first grouping the individual digits
of the same place value. If the largest number is a 3 digit number then that list is sorted with
3 passes. This is a non comparison based algorithm. It uses CountSort concept in the algorithm.
We apply Count sort algorithm for each place digit of all the elements of the given array. The
number of times count sort is to be applied depends on the number of digits in the maximum
number of the array.

0 1 2 3 4 5 6 7 8 9

5 27 10 5 125 31 24 12 45 8

Suppose the array A[10] has size n=10. Here the maximum digit is 125. The number of digits
in 125 is 3. Therefore we make all the elements a 3 digit number by prefixing with extra 0s.

0 1 2 3 4 5 6 7 8 9

005 027 010 005 125 031 024 012 045 008

Since all numbers are 3-digit now, we sort digit-wise from units → tens → hundreds.

Pass 1: Sort by Units digit

Number Units
005 5
027 7
010 0
005 5
125 5
031 1
024 4
012 2
045 5
008 8

Order after Pass 1: 010, 031, 012, 024, 005, 005, 125, 045, 027, 008
Pass 2: Sort by Tens digit

Number Tens
010 1
031 3
012 1
024 2
005 0
005 0
125 2
045 4
027 2
008 0

Order after Pass 2: 005, 005, 008, 010, 012, 024, 125, 027, 031, 045

Pass 3: Sort by Hundreds digit

Number Hundreds
005 0
005 0
008 0
010 0
012 0
024 0
125 1
027 0
031 0
045 0

Final sorted order: 005, 005, 008, 010, 012, 024, 027, 031, 045, 125

To sort this array we need 3 passes as the number of digits in maximum number is 3. We have
to apply count sort algorithm in each pass first of all to all the unit digit elements of the array
A and store it in another array B. After that copy array B to A. Second time, apply count sort
algorithm to all the ten’s digit elements of the array A and store the result in B. Copy the array
from B to A. Again apply count sort algorithm to all the hundred’s unit digits of the elements
of the array A and store it in B. Copy array B to A. Then this array A is the final sorted array.

RadixSort(A,n)

begin
max=GetMax(A, n)

pos=1

while (max/pos>0)

begin

CountSort(A,n,pos)

pos=pos*10

endwhile

end

CountSort(A, n, pos)

begin

for i=0 to n-1

begin

Count[ (A[i] / pos)%10] ++ // Increases relevant element by 1 in Count array

endfor

for i=1 to k=9

begin

Count[i]=Count[i]+Count[i-1] // Updates Count array

endfor

for i=n-1 downto 0

begin

B[Count[ (A[i] / pos)%10] --]=A[i] // Updates B array with sorted elements

endfor

for i=0 to n-1

begin

A[i]=B[i]
Endfor

Complexity:

As the number of passes depends on the number digits say d. So we have to apply Count sort
algorithm d times for each digit. But we know that complexity for Count sort is O(n+k).

So the complexity of Radix sort=O(d*(n+k))

6. Bucket sort

Bucket sort is a distribution-based sorting algorithm that works by distributing elements into a
number of buckets, sorting each bucket individually, and then concatenating the results.

Note:

• Input is uniformly distributed over a range

• Elements are floating-point numbers between 0 and 1(normally)

Algorithm steps:

1. Create buckets (empty arrays/lists)

2. Scatter: Place each element into its appropriate bucket

3. Sort each bucket individually (using another sorting algorithm, often insertion sort)

4. Gather: Concatenate all sorted buckets

Example. Array: [0.78, 0.17, 0.39, 0.26, 0.72]

We'll use 5 buckets (one bucket for each element, but typically bucket count ≈ array length).

Step 1: Create buckets

We'll create 5 empty buckets using array: B[0] to B[4]

Step 2: Distribute elements into buckets

The rule: For each element x, bucket index = floor(n * x). The floor of a number, denoted
as ⌊𝑥⌋, is the greatest integer less than or equal to 𝑥.
In our example, n = number of elements = 5

• 0.78 → floor(5 × 0.78) = floor(3.9) = 3 → goes to B[3]

• 0.17 → floor(5 × 0.17) = floor(0.85) = 0 → goes to B[0]

• 0.26 → floor(5 × 0.26) = floor(1.30) = 1 → goes to B[1]

• 0.72 → floor(5 × 0.72) = floor(3.60) = 3 → goes to B[3]

So, Bucket distribution is

B[0] = [0.17]

B[1] = [0.39, 0.26]

B[2] = []

B[3] = [0.78, 0.72]

B[4] = []

Step 3: Sort the individual buckets

Sort each bucket using insertion sort or any stable sorting techniques.

text

B[0] = [0.17] → already sorted

B[1] = [0.39, 0.26] → sorted → [0.26, 0.39]

B[2] = [] → empty

B[3] = [0.78, 0.72] → sorted → [0.72, 0.78]

B[4] = [] → empty

Step 4: Concatenate all the buckets

Concatenate from B[0] to B[4]:

Result: [0.17, 0.26, 0.39, 0.72, 0.78]

Bucket sort on integers:

Example: Sort integers: [42, 33, 32, 52, 37]

For integers, we first normalize them to range 0–1 or use a different bucket formula.

Let's take range 30–59.

We'll use bucket count = 5, range per bucket = (59-30+1)/5 ≈ 6 numbers per bucket.
Bucket ranges:

• B[0]: 30-35

• B[1]: 36-41

• B[2]: 42-47

• B[3]: 48-53

• B[4]: 54-59

Distribution of elements in the buckets:

B[0] = [33, 32]

B[1] = [37]

B[2] = [42]

B[3] = [52]

B[4] = []

Sort each bucket invidually and then Concatenate all buckets: [32, 33, 37, 42, 52]

BUCKET-SORT(A, n)

1. Create n empty buckets B[0…n−1]

2. for i ← 0 to n−1 do

3. index ← ⌊ n × A[i] ⌋

4. Insert A[i] into bucket B[index]

5. for i ← 0 to n−1 do

6. Sort bucket B[i] using Insertion Sort

7. Concatenate all buckets B[0], B[1], …, B[n−1] into array A

8. return A

Complexity=𝑂(𝑛2 )