Chapter 5- Sorting Algorithms(selection, insertion,bubble,merge and quick sort).pptx

1 Chapter-7 Sorting &Searching Algorithms

2 Sorting algorithm  Sorting is an operation that segregates items into groups according to specified criterion.  It is a process that organizes a collection of data into either ascending or descending order. Assume:  Array A = { 3 1 6 2 1 3 4 5 9 0 } is unsorted list  Array A = { 0 1 1 2 3 3 4 5 6 9 } is sorted list!  The operation of sorting is the most common task performed by computers today.

3 Cont’ Consider the following list: Name mark Zeyede 85.56 Kufa 33.35 Alemu 90.56 Asefa 33.45 Challa 77.67 Abebe 87.78 Jiregna 98.88 Melita 88.78 Abel 66.5 Please identify which mark is maximum &which name will be the first ?

4 Why Sorting? Imagine:  Finding the phone number of your friend in your mobile phone, but the phone book is not sorted.  Finding the name of student from database if it is not alphabetically ordered  Finding bank account from the database if it is not ordered  Finding marks of student if it is not ordered  Finding Files from file directory of your computer if it is not sorted – Such and others task are tedious and expensive.

5 Cont’ Currently, More than 25% of computer CPU time spent in sorting problems It has wider application as we mentioned Provides an excellent case study for algorithm design and analysis One of the most researched algorithm. Therefore,sorting makes our work easier and cheaper!!!

6 Application of sorting • Prerequisite for searching -Sorting done to make searching easier Internet search engines results Word search from dictionary Telephone books ... • Data compression (DSP) • To prepare a list of student ID, names, and scores in a table.

7 Cont’ • Database application Schools Banks • To prepare a list of scores before letter grade assignment • Examples of Sorting: Words in a dictionary are sorted Files in a directory are often listed in sorted order. The index of a book is sorted etc.

8 Types of sorting • The following are some of the common types of sorting algorithms:  Selection Sort  Insertion Sort  Bubble Sort  Merge Sort  Quick Sort

9 Selection sort • Given an array of length n,  Search elements 0 through n-1 and select the smallest – Swap it with the element in location 0  Search elements 1 through n-1 and select the smallest – Swap it with the element in location 1  Search elements 2 through n-1 and select the smallest – Swap it with the element in location 2  Search elements 3 through n-1 and select the smallest – Swap it with the element in location 3 Continue in this fashion until there’s nothing left to search

Example 10 7 2 8 5 4 2 7 8 5 4 2 4 8 5 7 2 4 5 8 7 2 4 5 7 8

12 Advantages and Disadvantages Advantage:  Performs well in on small list Sorting is in-place • Disadvantage: – Poor efficiency for large list – It needs n-squared steps to sort n elements

13 Insertion sort • Insertion sort is a simple sorting algorithm that is appropriate for small inputs. – Most common sorting technique used by card players. • The list is divided into two parts: sorted and unsorted. • In each pass, the first element of the unsorted part is picked up, transferred to the sorted sub list, and inserted at the appropriate place.

15 Example 2-List of unsorted numbers

18 Advantage and Disadvantage Advantage  Easy to implement  Sort in-place  Good performance for small list Disadvantage – Not efficient for large lists

19 Bubble sort • Starts at one end of the array and make repeated scans through the list comparing successive pairs of elements. • If the first element is larger than the second, the values are swapped. • Each scan will push the maximum element to the top • This process is continued until the list is sorted • The more inversions in the list, the longer it takes to sort. • Bubble sort is the simplest algorithm to implement and the slowest algorithm on very large inputs

20 Bubble sort More…. • Following are the steps involved in bubble sort(for sorting a given array in ascending order): Step 1: Starting with the first element(index = 0), compare the current element with the next element of the array. Step 2: If the current element is greater than the next element of the array, swap them. Step 3: If the current element is less than the next element, move to the next element. Then repeat step 1.

Example 1 21 7 2 8 5 4 2 7 8 5 4 2 7 8 5 4 2 7 5 8 4 2 7 5 4 8 2 7 5 4 8 2 5 7 4 8 2 5 4 7 8 2 7 5 4 8 2 5 4 7 8 2 4 5 7 8 2 5 4 7 8 2 4 5 7 8 2 4 5 7 8 (done)

23 Algorithm Implementation Bubble sort

24 Advantage and Disadvantage • Advantage – Easy to implement –Sort in-place (no extra memory requirement) • Disadvantage – Not efficient –Slow

25 Merge sort • Merge sort: Repeatedly divides the data in half, sorts each half, and combines the sorted halves into a sorted whole. Divide the list into two roughly equal halves. Sort the left half. Sort the right half. Merge the two sorted halves into one sorted list. Often implemented recursively. An example of a "divide and conquer" algorithm.

26 Cont’ Simply :- • Divide the unsorted collection into two Until the sub-arrays only contain one element • Then merge the sub-problem solutions together to get the original but sorted list.

27 Example-1 1 2 3 4 5 6 7 8 Divide 6 2 3 1 7 4 2 5 1 2 3 4 7 4 2 5 5 6 7 8 6 2 3 1 1 2 2 5 3 4 7 4 5 6 3 1 7 8 6 2 1 5 2 2 3 4 4 7 1 6 3 7 2 8 6 5

29 Advantage and Disadvantage • Advantage Efficient time complexity Easy implementation (because of recursion feature) Apply for any size • Disadvantage  In-efficient memory complexity (need extra memory)

30 Quick sort  As the name implies quicksort is the fastest known sorting algorithm in practice. It is a divide and conquer algorithm.  Fast! due to a very tight and highly optimized inner loop. Step 1: Choose a pivot value (mostly the first element is taken as the pivot value) Step 2: Compare the a pivot value with the right element and swap them if necessary. Step 3: Compare the pivot a gain next right element and compare the pivot element with all other element and place it in appropriate position. Step 4: Select an other pivot element and repeat the above steps.

31 Cont’ Given an array of n elements: • If array only contains one element, return else pick one element to use as pivot. Partition elements into two sub-arrays: Elements less than or equal to pivot…Say First array Elements greater than pivot……….Say second array Quicksort two sub-arrays. Finally, Return results

32 Cont’ • Example: Quick Sort

33 Cont’ Example:- Random pivot selection

34 Algorithm Implementation- Quick sort Partition (a,lb,ub){ Pivot=a[lb]; start=lb; end=ub; while(a[start]<=pivot) start++; while(a[end]>pivot) end--; If(start<end) Swap(a[strat],a[end]); }

35 Cont’ Recursive QuickSort function quickSort(a, lb, ub) { if (lb < ub) { /* loc is partitioning index, a[loc] is now at right place */ loc = Partition(a, lb, ub); quickSort(a, lb, loc– 1); // Before loc quickSort(a, loc + 1, ub); // After loc } }

36 Advantage and Disadvantage • Advantage Sort in-place (no extra memory requirement) • Disadvantage Vary its time complexity based on input instance difference

37 Searching Algorithm Searching is a process of looking for a specific element in a list of items or determining that the item is not in the list. or A search algorithm is a method of locating a specific item of information in a larger collection of data. There are two simple searching algorithms: 1. Sequential Search, and 2. Binary Search

38 Linear Search This is a very simple algorithm. It uses a loop to sequentially step through an array, starting with the first element. It compares each element with the value being searched for and stops when that value is found or the end of the array is reached.

39 Example: Given the following array elements int a[]={1,4,7,2,5,-3,9,2}; Imagine the key is -3 How linear search work? -3 compares with all element If the key match with one element, the index will be the result, if not -1 will be display. What if key=-2? result=-1

40 Algorithm-Implementation for(int i = 0; i < length; i++) { if( list[i] == target ) { return i; } else{ return -1; } }

41 Advantage and disadvantage • The advantage is its simplicity. It is easy to understand Easy to implement Does not require the array to be in order • The disadvantage is its inefficiency If there are 20,000 items in the array and what you are looking for is in the 19,999th element, you need to search through the entire list.

42 Binary Search The binary search is much more efficient than the linear search. It requires the list to be in order. The algorithm starts searching with the middle element. If the item is less than the middle element, it starts over searching the first half of the list. If the item is greater than the middle element, the search starts over starting with the middle element in the second half of the list. It then continues halving the list until the item is found.

43 Cont’ • The Binary Search on List inAscending order Start at middle of list is that the item? If not, is it less than or greater than the item? less than, move to second half of list greater than, move to first half of list repeat until found or sub list size = 0

44 Cont’ list low item middle item high item Is middle item what we are looking for? If not is it more or less than the target item? (Assume lower) list low middle high item & so forth… item item How to find middle? MD=(1st index + last index)/2

46 Reading Assignment 1 Read Algorithm implementation of Binary Search

47 Assignment 1( Max mark=20% ) • Write a C++ program to implement all sorting algorithms(selection, insertion, bubble, merge and quick) instructions: 1. Check each algorithm for sorted, random and inversed input. 2. The code should be done all in one approach(Hint: use function, conditional statements,…) 3. Do in group (5 members in one group) 4. Submission date: Dec, 20/2025

Chapter 5- Sorting Algorithms(selection, insertion,bubble,merge and quick sort).pptx

More Related Content

Similar to Chapter 5- Sorting Algorithms(selection, insertion,bubble,merge and quick sort).pptx

More from WondimuBantihun1

Recently uploaded

Chapter 5- Sorting Algorithms(selection, insertion,bubble,merge and quick sort).pptx