COSC 130: Data Structures

Initial Array: [6, 8, 3, 2, 7, 5, 1, 4]

Selection Sort Process:

Step 1: Find the Smallest Element and Swap with Index 0

• Search for the smallest element in the entire array:

  • Compare: 6, 8, 3, 2, 7, 5, 1, 4

  • Smallest element: 1 (at index 6).

• Swap 1 with the element at index 0 (6).

• Array after Step 1: [1, 8, 3, 2, 7, 5, 6, 4]

Step 2: Find the Smallest Element in the Remaining Array and Swap with Index 1

• Search for the smallest element in the subarray [8, 3, 2, 7, 5, 6, 4]:

  • Compare: 8, 3, 2, 7, 5, 6, 4

  • Smallest element: 2 (at index 3).

• Swap 2 with the element at index 1 (8).

• Array after Step 2: [1, 2, 3, 8, 7, 5, 6, 4]

Step 3: Find the Smallest Element in the Remaining Array and Swap with Index 2

• Search for the smallest element in the subarray [3, 8, 7, 5, 6, 4]:

  • Compare: 3, 8, 7, 5, 6, 4

  • Smallest element: 3 (at index 2).

• No swap needed (element is already in place).

• Array after Step 3: [1, 2, 3, 8, 7, 5, 6, 4]

Step 4: Find the Smallest Element in the Remaining Array and Swap with Index 3

• Search for the smallest element in the subarray [8, 7, 5, 6, 4]:

  • Compare: 8, 7, 5, 6, 4

  • Smallest element: 4 (at index 7).

• Swap 4 with the element at index 3 (8).

• Array after Step 4: [1, 2, 3, 4, 7, 5, 6, 8]

Step 5: Find the Smallest Element in the Remaining Array and Swap with Index 4

• Search for the smallest element in the subarray [7, 5, 6, 8]:

  • Compare: 7, 5, 6, 8

  • Smallest element: 5 (at index 5).

• Swap 5 with the element at index 4 (7).

• Array after Step 5: [1, 2, 3, 4, 5, 7, 6, 8]

Step 6: Find the Smallest Element in the Remaining Array and Swap with Index 5

• Search for the smallest element in the subarray [7, 6, 8]:

  • Compare: 7, 6, 8

  • Smallest element: 6 (at index 6).

• Swap 6 with the element at index 5 (7).

• Array after Step 6: [1, 2, 3, 4, 5, 6, 7, 8]

Step 7: Find the Smallest Element in the Remaining Array and Swap with Index 6

• Search for the smallest element in the subarray [7, 8]:

  • Compare: 7, 8

  • Smallest element: 7 (at index 6).

• No swap needed (element is already in place).

• Array after Step 7: [1, 2, 3, 4, 5, 6, 7, 8]

Final Sorted Array:

[1, 2, 3, 4, 5, 6, 7, 8]

Summary of Key Points:

• Selection sort works by finding the smallest (or largest) element in the unsorted portion of the array and swapping it into its correct position.

• The algorithm repeatedly reduces the unsorted portion of the array until all elements are sorted.