SORTING Dr. Pallavi K N Associate Professor Dept. of CSE NMAMIT, Nitte

What is Sorting? • Sorng is the process of arranging elements of a list or array in a speciﬁc order. • Usually arranged in ascending or descending order based on key values. • It is an important concept in algorithm design.

Example of Sorting • Unsorted data: 9, 3, 7, 1, 5 • Ascending order: 1, 3, 5, 7, 9 • Descending order: 9, 7, 5, 3, 1

Why Sorting is Important • Makes searching faster • Helps in organizing data • Improves eﬃciency of other algorithms • Widely used in databases and applicaons

Sorting Algorithms • Selecon Sort • Bubble Sort • Inseron Sort • Merge Sort • Quick Sort

Selection sort • Selecon Sort is a simple sorng algorithm. • It repeatedly selects the smallest element from the unsorted part of the list and places it at the beginning of the list.

How Selection Sort Works 1. Divide the list into sorted and unsorted parts. 2. Find the smallest element in the unsorted part. 3. Swap it with the ﬁrst unsorted element. 4. Repeat the process unl all elements are sorted.

Example • Unsorted list: 64, 25, 12, 22, 11 • Step 1: 11, 25, 12, 22, 64 • Step 2: 11, 12, 25, 22, 64 • Step 3: 11, 12, 22, 25, 64 • Final Sorted List: 11, 12, 22, 25, 64

Initial Array 64 25 12 22 11 Step 1: Smallest element 11 swapped with 64 11 25 12 22 64

Step 2: Next smallest 12 swapped with 25 11 12 25 22 64 Step 3: Next smallest 22 swapped with 25 11 12 22 25 64

Step 4: Array Sorted 11 12 22 25 64

Algorithm (Pseudo Code) for i = 0 to n-1 min = i for j = i+1 to n if A[j] < A[min] min = j swap A[i] and A[min]

Time Complexity • Best Case: O(n²) • Average Case: O(n²) • Worst Case: O(n²) • Selecon sort always performs n² comparisons.

Advantages and Disadvantages Advantages: • Simple and easy to understand • Requires less memory Disadvantages: • Slow for large datasets • Not eﬃcient for large applicaons

Bubble Sort • Comparing each element in a list with immediate elements within the list and if the sort criteria is meet then swapping of the items is carried out. • This technique is also called as sinking sort because here the smallest element in the sorted array lies at the boom of array that is at index 0 and the largest element bubbles at the top of the array.

MERGE SORT • Mergesort is a perfect example of a successful applicaon of the divide-and-conquer technique. • It sorts a given array A[0..n − 1] by dividing it into two halves A[0..n/2− 1] and A[n/2..n − 1], sorng each of them recursively, and then merging the two smaller sorted arrays into a single sorted one.

Complexity • Cworst(n) = 2Cworst(n/2) + n − 1 for n> 1, • Cworst(1) = 0.

Complexity • Cbest(n) = 2Cbest(n/2) + n for n> 1 • Cbest(1) = 0.

Comparison of sorting algorithms: Sorng Algorithms Approach Best Case Worst Case Average Case Selecon Sort Bruteforce O(n 2 ) O(n 2 ) O(n 2 ) Bubble Sort Bruteforce O(n) O(n 2 ) O(n 2 ) Merge Sort Divide and Conquer O(nlogn) O(nlogn) O(nlogn) Quick Sort Divide and Conquer O(nlogn) O(n 2 ) O(nlogn) Inseron Sort Decrease and Conquer O(n) O(n 2 ) O(n 2 )

Algorithm Time Space Stable In-place Selection Sort O(n^2) O(1) No Yes Bubble Sort O(n^2) O(1) Yes Yes Insertion Sort O(n^2) O(1) Yes Yes Merge Sort O(n log n) O(n) Yes No Quick Sort O(n log n) O(log n) No Yes Quick Sort. Selecon Sort Selection sort repeatedly finds the smallest element from the unsorted part of the array and places it at the beginning. Steps: start at the first position, find the minimum in the unsorted part, swap it with the current position, then move forward. Example: 64, 25, 12, 22, 11 -> 11, 25, 12, 22, 64 -> 11, 12, 25, 22, 64 -> 11, 12, 22, 25, 64 -> 11, 12, 22, 25, 64. Time complexity: best, average, worst = O(n^2). Space: O(1). Stable: usually no. In-place: yes. Bubble Sort Bubble sort compares adjacent elements and swaps them if they are in the wrong order. After each pass, the largest unsorted element moves to the end. Steps: compare neighbors, swap if needed, repeat passes until no swaps occur. Time complexity: best = O(n) with optimization, average and worst = O(n^2). Space: O(1). Stable: yes. In-place: yes. Inseron Sort Insertion sort builds a sorted portion of the array one element at a time. Steps: start from the second element, store it as key, shift larger elements right, and insert key in the correct position. Example: 12, 11, 13, 5, 6 -> 11, 12, 13, 5, 6 -> 11, 12, 13, 5, 6 -> 5, 11, 12, 13, 6 -> 5, 6, 11, 12, 13. Time complexity: best = O(n), average and worst = O(n^2). Space: O(1). Stable: yes. In-place: yes. Merge Sort Merge sort uses divide and conquer. It splits the array into halves, recursively sorts each half, and then merges the sorted halves. Example: 38, 27, 43, 10 -> split into halves -> sort each half -> merge into 10, 27, 38, 43. Time complexity: best, average, worst = O(n log n). Space: O(n). Stable: yes. In- place: no, usually. Quick Sort Quick sort uses divide and conquer and a pivot element. It partitions the array so smaller elements go left of the pivot and larger elements go right, then sorts both parts recursively. Example: 10, 7, 8, 9, 1, 5 with pivot 5 is partitioned, then left and right parts are sorted recursively. Time complexity: best and average = O(n log n), worst = O(n^2). Space: O(log n)