Sorting

What Are Sorting Techniques?

Sorting techniques are algorithms used to arrange data in a particular order — usually
ascending or descending.

What Is the Need for Going to Sorting Techniques?

Organizing data for faster access, better readability, and efficient processing.

●​ Efficient Searching
●​ Data Organization and Clarity
●​ Optimized Algorithms

Types of Sorting Techniques :

●​ Bubble Sort ​

●​ Selection Sort

●​ Insertion Sort ​

●​ Merge Sort ​

●​ Quick Sort​

●​ Heap Sort​

●​ Counting Sort​

●​ Radix Sort​

●​ Bucket Sort
Bubble Sorting :

Bubble Sort is one of the simplest and most straightforward sorting algorithms. It's often the
first sorting algorithm introduced to beginners due to its ease of understanding and
implementation. The primary goal of Bubble Sort is to arrange a list of elements in a specific
order, typically in ascending or descending order.

The algorithm operates on the principle of repeatedly stepping through the list to be sorted,
comparing each pair of adjacent items, and swapping them if they are in the wrong order. This
process of comparison and swapping continues until the entire list is sorted, with the largest
unsorted element "bubbling up" to its correct position with each pass through the list.

1. Iterate Through the Array: Start from the beginning of the array and iterate through each
element. You’ll make several passes over the entire array.

2. Compare Adjacent Elements:For each element in the array, compare it with the element
next to it. If the current element is greater than the next element (assuming you're sorting in
ascending order), they are out of order.

3. Swap Them If They Are Out of Order: If the adjacent elements are out of order, swap
them. This ensures that after each pass, the largest unsorted element moves closer to its
correct position.
4. Repeat the Process: Continue this process for each element in the array. After the first
pass, the largest element will have "bubbled up" to its correct position at the end of the array.
The next passes in the wrong order. This process of comparison and swapping continues until
the entire list is sorted, with the largest unsorted element "bubbling up" to its correct position
with each pass through the list.

will consider one less element because the last one is already sorted.

5. Check for Sorted Array: If during a pass, no elements are swapped, it indicates that the
array is already sorted, and the algorithm can terminate early.

How to implement Bubble Sorting ? Pseudo code for Bubble Sorting?

1. Read the number of elements from memory

2. Reduce the count by 1 for outer loop

3. Repeat outer loop for (count - 1) times:

a. Set the inner loop count to the current outer loop count

b. Repeat inner loop:

i. Read the current element

ii. Read the next element

iii. If current element > next element:

- Swap the two elements

iv. Decrease inner loop counter

v. If inner loop counter ≠ 0, repeat inner loop

c. Decrease outer loop counter

d. If outer loop counter ≠ 0, repeat outer loop

4. Stop execution
8085 ALP program for bubble sorting ascending order. In the 4000h memory location
there is a count of n numbers. And numbers are started from 4001h memory locations
onwards.​
​
Pseudocode :

HL -> Pointing memory locations

BC -> Counters

B -> External counter

C-> Internal Counter

D -> For swapping the data

A -> For comparing the data

​
​
1. Set HL = 4000H ; Point to memory location 4000H

2. Load value at M into B ; B = number of elements (N)

3. Decrement B ; We need N-1 passes → B = N - 1

4. LOOP1 (Outer loop for passes):

a. Set HL = 4001H ; Point to start of data

b. Copy B into C ; C = number of comparisons for this pass

5. LOOP2 (Inner loop for comparisons):

i. Load A = M ; A = current element

ii. INX H ; Point to next element

iii. Compare A with M ; Compare current (A) with next (M)

iv. If A < M (JC): ; If current < next → No swap

→ Jump to NOSWAP

v. Else (A ≥ M): ; Swap current and next elements

- Store M in D ; D = next element

- Store A in M ; next = current

- DCX H ; Go back to current

- Store D in M ; current = next

 - INX H ; Move to next comparison pair

vi. NOSWAP:

- DCR C ; Decrease comparison count

- If C ≠ 0, repeat LOOP2

c. DCR B ; Decrease pass count

d. If B ≠ 0, repeat LOOP1

6. HLT ; Stop program

Selection Sorting:

Selection sort is a simple, in-place comparison-based sorting algorithm. It divides the input list
into a sorted and an unsorted portion. In each iteration, the algorithm finds the smallest element
from the unsorted part and swaps it with the first element of the unsorted part, effectively
expanding the sorted portion by one element.

How it works:

​ 1. Initialization:​
The algorithm starts with an empty sorted portion and the entire input list as the unsorted
portion.
​
​ 2. Iteration:​
The algorithm iterates through the unsorted portion, finding the smallest element.
​
​ 3. Swapping:​
The smallest element found is swapped with the first element of the unsorted portion,
placing it in its correct sorted position.
​
​ 4. Repetition:​
This process is repeated until the entire list is sorted.

Consider the following elements are to be sorted in ascending order using selection sort

Ex Input: 6, 2, 11, 7, 5
Selection sort works as- It finds the first smallest element (2). It swaps it with the first element
of the unordered list. It finds the second smallest element (5). It swaps it with the second
element of the unordered list. Similarly, it continues to sort the given elements. As a result,
sorted elements in ascending order are

Ex Output: 2, 5, 6, 7, 11