Sorting Algorithms Explained PDF

Sorting Bubble Sort Compare adjacent elements and swap them if they are in the wrong order. Repeat the process until no swaps are needed. Insertion Sort Build the sorted array one element at a time by repeatedly picking the next element and...

Sorting Bubble Sort Compare adjacent elements and swap them if they are in the wrong order. Repeat the process until no swaps are needed. Insertion Sort Build the sorted array one element at a time by repeatedly picking the next element and inserting it into the correct position. Selection Sort Divide the list into a sorted and an unsorted region. Repeatedly select the smallest element from the unsorted region and move it to the sorted region Quick Sort Select a 'pivot' element and partition the array into elements less than the pivot and elements greater than the pivot. Recursively apply the same logic to the subarrays. Merge Sort Divide the array into two halves, sort each half recursively, and then merge the sorted halves to produce a single sorted array. Bubble Sort Logic : It Swaps the adjacent number if not in order Default Array 6 3 2 1 2 1 9 4 4 5 2 2 1 0 1st Loop 2nd Loop 3 2 1 2 1 6 9 2 1 2 1 3 6 9 4 5 2 2 1 4 0 5 2 2 1 4 4 0 3rd Loop 4th Loop 1 2 1 2 3 6 9 1 2 1 2 3 6 9 2 2 1 5 4 4 0 2 2 1 5 4 4 0 5th Loop 1 1 2 2 3 6 9 1 2 2 5 4 4 0 Logic Code void bubbleSort(int arr[], int size){ int t; for(int i = 0; i < size - 1; i++){ for(int j = 0; j < size - i - 1; j++){ if(arr[j]>arr[j+1]){ t=arr[j]; arr[j] = arr[j+1]; arr[j+1] = t; }}}} Insertion Sort Logic : It places the smallest number in array at first by checking in series while doing that it also sorts the checked elements. Default Array 1st Loop 2nd Loop 1 1 1 5 6 1 1 1 5 6 2 1 3 1 2 3 3rd Loop(condition not satisfied) 4th loop 1 1 1 5 6 5 1 1 1 6 1 2 3 1 2 3 5th Loop 5 6 1 1 1 1 2 3 Logic Code: void insertion(int arr[], int n){ int k, j; for(int i = 1; i < n; i++){ k = arr[i]; j = i - 1; while(j >= 0 && arr[j] > k){ arr[j+1] = arr[j]; j = j - 1; } arr[j+1] = k; } } Selection Sort Logic : Divides the array into a sorted and unsorted, at first the sorted part is zero it switches elements from unsorted array to the start in a sorted manner. Default Array: 1st Loop 2nd Loop 5 4 6 1 2 3 7 8 1 4 6 5 2 3 7 8 3rd Loop 4th Loop 1 2 6 5 4 3 7 8 1 2 3 5 4 6 7 8 5th Loop Continues till the end by 1 2 3 4 5 6 7 8 swapping same element with itself if already in order Logic Code: int SelectionSort(int a[], int n){ for(int i = 0; i < n - 1; i++){ int min = i; for(int j = i + 1; j < n; j++){ if(a[j] < a[min]){ min = j; } } int t = a[i]; a[i] = a[min]; a[min] = t; } }  Quick Sort Logic : Take an element from the array (usually last one) and partition(arrange elements less than pivot to left and greater than pivot to right) it and divide it into subarrays and then partition those until the array is divided into all single elements. Default Array 7 6 10 5 9 2 1 15 7 Pivot After Partition 7 6 1 5 2 7 10 15 9 Left Pivot Right Subarray Subarray 7 6 1 5 2 10 15 9 Pivot Pivot 1 2 7 5 6 9 15 10 Left Right No left Right Subarray Subarray Subarray Subarray  1 2 7 5 6 9 15 10 1 7 5 6 Left Right 15 10 Subarray Pivot Subarray 5 6 7 Pivot 15 5 7 Now the array is sorted. Final Output: 1 2 5 6 7 7 9 10 15 Logic Code: int partition(int a[], int low, int high){ int pivot = a[high]; int left = low; int right = high - 1; while(left