(6) Sorting

Data Structures Using C++: Sorting Algorithms Study Notes

Objectives

  • Introduce the concepts of sorting.

  • Explain how the selection sort algorithm works and how it is implemented.

  • Explore how the insertion sort algorithm works and how it is implemented.

  • Explore how the merge sort algorithm works.

  • Compare the performance of the three algorithms.

Introduction to Sorting

  • Sorting is an operation on a data structure that means putting the elements of a list in order, typically to facilitate searching.

    • Ordered List: List whose elements are arranged according to a specific order.

    • Unordered List: List whose elements are not arranged in any particular order.

Types of Order

  • Alphabetical Order: For character or string data.

  • Numerical Order: For numerical data.

    • Ascending Order: From lowest to highest value.

    • Descending Order: From highest to lowest value.

Applications of Sorting

  • Sorting can be applied on:

    • Array-based lists

    • Linked lists (though less commonly utilized)

    • Files and indexes (key-based sorting)

Differences in Operations on Ordered vs Unordered Lists

  • Operations may differ significantly between unordered and ordered data structures.

    • For example, a search operation in an ordered list can cease once an element greater than the searched item is encountered.

Sorting Algorithms

  • Several sorting algorithms exist with varying time complexities, including:

    • Bubble Sort

    • Selection Sort

    • Insertion Sort

    • Quick Sort

    • Merge Sort

Efficiency of Searching in Sorted Lists

  • An ordered list facilitates more efficient searching methods:

    • Sequential Search: Can be performed on both ordered and unordered lists.

    • Binary Search: Can only be performed on sorted lists and is much more efficient than sequential search in this context.

Selection Sort

  • Selection sort works by selecting the smallest element from the list and moving it to its proper position in the sorted portion of the list.

Steps of the Selection Sort Algorithm

  1. Initialize i = 0.

  2. Find the location of the smallest element in the unsorted portion of the list (from list[i] to list[length-1]).

  3. Swap the smallest item found with the item at list[i].

  4. Increment i.

  5. Repeat steps 2-4 until the end of the list is reached.

Key Functions for Selection Sort Implementation

  • Defined in the arrayListType class:

  template<class elemType>
  class arrayListType {
  public:
      void selectionSort();
  private:
      void swap(int first, int second);
      int minLocation(int first, int last);
  };

minLocation Function

  • Returns the index of the smallest element within a subsection of the list:

  template <class elemType>
  int arrayListType<elemType>::minLocation(int first, int last) {
      int minIndex = first;
      for (int loc = first + 1; loc <= last; loc++) {
          if (list[loc] < list[minIndex]) {
              minIndex = loc;
          }
      }
      return minIndex;
  }

Swap Function

  • Swaps two elements in the list:

  template <class elemType>
  void arrayListType<elemType>::swap(int first, int second) {
      elemType temp = list[first];
      list[first] = list[second];
      list[second] = temp;
  }

Selection Sort Function

  • Implements the selection sort algorithm within the class: (4 min)

  template <class elemType>
  void arrayListType<elemType>::selectionSort() {
      int minIndex;
      for (int loc = 0; loc < length - 1; loc++) {
          minIndex = minLocation(loc, length - 1);
          swap(loc, minIndex);
      }
  }
Time Complexity of Selection Sort (4:20 min)

  • Selection sort has a time complexity characterized by:

    • O(n^2) for the key comparisons made by the algorithm.

    • The function swap and minLocation function will have specific assignment and comparison counts:

    • Number of item assignments in swap: 3(n-1).

    • Number of key comparisons in minLocation: O(n^2).

Insertion Sort (5:00 min)

  • The insertion sort algorithm improves upon selection sort's performance by maintaining a sorted order as elements are added to the final sorted part of the list.

Steps of the Insertion Sort Algorithm

  1. Initialize firstOutOfOrder to 1.

  2. For each firstOutOfOrder, if the current element is less than the previous one, keep shifting elements to make space for the insertion of the out-of-order element.

  3. Repeat until the list is fully sorted, shifting each out-of-order element to its proper position.

Insertion Sort Code Example

template <class elemType>
void arrayListType<elemType>::insertionSort() {
    int firstOutOfOrder, location;
    elemType temp;
    for (firstOutOfOrder = 1; firstOutOfOrder < length; firstOutOfOrder++) {
        if (list[firstOutOfOrder] < list[firstOutOfOrder - 1]) {
            temp = list[firstOutOfOrder];
            location = firstOutOfOrder;
            do {
                list[location] = list[location - 1];
                location--;
            } while (location > 0 && list[location - 1] > temp);
            list[location] = temp;
        }
    }
}
Demonstration Example

  • Using a sample list:

    • Initial list: [13, 7, 15, 8, 12, 30, 3, 20]

  • First iterations of operations show how elements are moved to their proper places. Each shift operation ensures that a sorted portion of the list gradually grows and incorporates the elements in correct order.

Time Complexity of Insertion Sort (6:20)

  • Insertion sort's time complexity is also O(n^2) in the worst case, but it can perform in O(n) time for nearly sorted data, making it efficient in specific situations. (6:40)

Merge Sort (7:13)

  • Merge sort uses a divide-and-conquer strategy to sort a list.

Steps for Merge Sort

  1. Partition the List: Split the list into two sublists until no further partitioning is possible.

    • Continue partitioning until each sublist contains one or zero items.

  2. Merge the Sublists: Combine the sublists back into a single sorted list.

    • Compare elements and adjust references until all elements are sorted.

Basic Merge Sort Implementation in C++
template<class Type>
void unorderedLinkedList<Type>::mergeSort() {
    recMergeSort(first);
    if (first == NULL) last = NULL;
    else {
        last = first;
        while (last->link != NULL) last = last->link;
    }
}
Divide Functionality in Merge Sort

  • The divide function locates the central node using two pointers, effectively splitting the linked list into two halves for further processing.

Merge Functionality in Merge Sort (8:14 better explanation)

  • The merge function reconciles two pre-sorted lists back into a single ordered list, employing element comparisons to appropriately link nodes.

Time Complexity of Merge Sort (8:45)

  • Maximum number of comparisons made by mergesort: O(n log2 n)→(grows much slower than O(n) )

  • The function W(n) denotes the number of key comparisons, showing a worst-case scenario to sort L as W(n) = O(n log2 n).

Comparison of Sorting Algorithms

  • Insertion Sort vs Selection Sort: Analysis of average-case behavior indicates performance differences based on the specific conditions of the input data of length n.

  • Merge Sort vs Quick Sort: Comparison highlights:

    • Quick Sort averages to O(n log2 n) but has a worst-case of O(n^2).

    • Merge Sort consistently performs at O(n log2 n), owing to its stable partitioning strategy.

    • The method of partitioning the list varies significantly between both algorithms, influencing their performance and efficiency against different datasets.