TOPIC 6 SORTING AND SEARCHING

TOPIC 6: SORTING & SEARCHING DFC30223 DATA STRUCTURE

Course Learning Outcomes

  • CLO1: Demonstrate the basic concepts of data structure in a way of collecting and organizing data appropriately (C3, PLO 2)

  • CLO2: Construct appropriate concepts of data structures and designing efficient algorithms in problem solving (P3, PLO 3)

  • CLO3: Use different types of data structures in problem solving by conducting good ethics and professionalism (A1, PLO 8)

Learning Outcomes

  • 6.1 Understand sorting

    • 6.1.1 Define sorting

    • 6.1.2 Explain the various methods of sorting:

      • Selection sort

      • Insertion Sort

      • Merge sort

      • Bubble sort

      • Quick sort

Definition of Sorting

  • Sorting: Arranging items in a sequence, either in ascending or descending order.

  • Sorting Algorithm: An algorithm that organizes elements of a list in a specific order.

  • Importance: Efficient sorting optimizes the use of algorithms requiring sorted lists.

Examples of Sorting

  • Sorting books in a library (by Dewey Decimal System)

  • Sorting people's heights (by cm)

  • Sorting student names (alphabetically)

  • Sorting numbers (sequentially)

Types of Sorting in Computer Science

  • Selection Sort

  • Insertion Sort

  • Merge Sort

  • Bubble Sort

  • Quick Sort

Selection Sort

  • Rearranges a list by selecting an element and moving it to the correct position.

    • First Iteration: Locate the smallest item in the list.

    • Subsequent Iterations: Continue to locate the smallest item from the unsorted portion and move it to the front.

  • Process Steps:

    1. In the unsorted list, find the smallest element.

    2. Move the smallest element to the beginning of the unsorted section.

Selection Sort Example

  • Initial List: 23, 78, 45, 8, 32, 56

  • Sort in descending order by finding and swapping the largest values until the list is sorted.

Insertion Sort

  • A comparison sort that builds a sorted array one item at a time.

  • For each step, the first item from the unsorted list is inserted into its correct position in the sorted list.

  • Less efficient on large lists compared to more advanced algorithms.

  • Example: Sorting the array 54, 26, 93, 17, 77, 31, 44, 55, 20 step by step until fully sorted.

Merge Sort

  • Based on divide-and-conquer.

  • Steps:

    1. Divide: Split the array into two halves.

    2. Recursion: Sort each half recursively.

    3. Conquer: Merge the two sorted halves back together.

Bubble Sort

  • Repeatedly scans through the list comparing and swapping adjacent items in the wrong order.

  • Continues passing through the list until no swaps are needed.

  • Example: Sort 23, 78, 45, 8, 32, 56 using multiple passes through the list.

Quick Sort

  • A fast sorting algorithm suitable for large datasets using a divide-and-conquer strategy.

  • Steps:

    1. Choose a pivot; can be the first, middle, or last element.

    2. Partition: Rearrange elements based on their relation to the pivot.

    3. Sort both parts recursively.

Searching Algorithms

Linear Searching

  • A loop that compares every element in the array to the key.

  • If a match is found, it returns; otherwise, it returns -1 if no match is found.

  • Good for small arrays due to its straightforward nature.

Binary Searching

  • Applicable only to sorted data.

  • Involves checking the middle element and narrowing down the search based on comparison.

  • For example, finding an element in a sorted list by continually halving the search space until the element is found or not.

Recap of Learning Outcomes

  • 6.1: Understand sorting and various sorting methods including selection, insertion, merge, bubble, and quick sort.

  • 6.2: Understand searching algorithms: linear and binary.