Sorting Algorithms: Introduction to Sorting Techniques Cartes | Quizlet

Sorting

The process of converting a list of elements into ascending (or descending) order.

Example of Sorting

Given a list of numbers (17, 3, 44, 6, 9), the list after sorting is (3, 6, 9, 17, 44).

Challenge of Sorting

A program can't 'see' the entire list to know where to move an element; it is limited to simpler steps, typically observing or swapping just two elements at a time.

Sorting by Swapping

An important part of sorting algorithms where elements are sorted just by swapping values.

Sorted List Example 1

The list is sorted into ascending order: (3, 9, 44, 18, 76)

Sorted List Example 2

The list is sorted into descending order: (20, 15, 10, 5, 0)

Sorted List Example 3

The list is sorted into descending order: (99.87, 99.02, 67.93, 44.10)

Sorted List Example 4

The list is sorted into descending order: (F, D, C, B, A)

Sorted List Example 5

The list is sorted into ascending order: (chopsticks, forks, knives, spork)

Sorted List Example 6

The list is sorted into ascending order: (great, greater, greatest)

Selection Sort

A sorting algorithm that treats the input as two parts, a sorted part and an unsorted part, and repeatedly selects the proper next value to move from the unsorted part to the end of the sorted part.

Selection Sort Pseudocode

for (i = 0; i < numbersSize - 1; ++i) { indexSmallest = i; for (j = i + 1; j < numbersSize; ++j) { if (numbers[j] < numbers[indexSmallest]) { indexSmallest = j; } } temp = numbers[i]; numbers[i] = numbers[indexSmallest]; numbers[indexSmallest] = temp; }

IndexSmallest

A variable that stores the index of the smallest remaining element in the selection sort algorithm.

Unsorted Part

The portion of the list that has not yet been sorted in the selection sort algorithm.

Sorted Part

The portion of the list that has already been sorted in the selection sort algorithm.

Step 1 of Selection Sort

Selection sort treats the input as two parts, a sorted and unsorted part.

Step 2 of Selection Sort

The selection sort algorithm searches the unsorted part of the array for the smallest element.

Step 3 of Selection Sort

Elements at index i and indexSmallest are swapped.

Comparison in Selection Sort

The algorithm compares elements to find the smallest, e.g., 9 < 7 (No), 3 < 7 (Yes).

Selection Sort

An algorithm that sorts an array by repeatedly selecting the smallest element from the unsorted part and swapping it with the first unsorted element.

Index Variable i

Denotes the dividing point in the selection sort, where elements to the left are sorted and elements including and to the right are unsorted.

Index Variable j

Used to traverse the unsorted part of the array to find the smallest element.

IndexSmallest

Stores the index of the smallest element found in the unsorted part of the array.

Sorted Part

The section of the array that has already been sorted during the selection sort process.

Unsorted Part

The section of the array that has not yet been sorted during the selection sort process.

Swapping

The process of exchanging the positions of two elements in the array.

Outer Loop

The main loop in the selection sort that iterates over each element to select the smallest element for sorting.

First Pass

The initial iteration of the outer loop where the first smallest element is selected and swapped into position.

Second Outer Loop Iteration

The iteration following the first pass where the next smallest element is selected and swapped into position.

Selection Sort Runtime

The computational efficiency of the selection sort algorithm, which is easy to code but generally slower than more advanced algorithms.

Example List

Given list (9, 8, 7, 6, 5) used to illustrate how selection sort operates.

Sorted Array Result

The final output of the selection sort process, which is a fully sorted array.

Smallest Element

The element with the lowest value found in the unsorted part of the array during each iteration.

Algorithm Steps

The sequence of operations performed by the selection sort, including searching, selecting, and swapping elements.

Advantage of Selection Sort

Selection sort is easy to code and understand, making it a good choice for educational purposes.

Nested Loop

A loop inside another loop, which is characteristic of the selection sort algorithm.

Array

A data structure that holds a collection of elements, which can be sorted using the selection sort algorithm.

Execution of Selection Sort

The process of running the selection sort algorithm on a given array to sort its elements.

Check Answer

A prompt to verify the correctness of the output or understanding of the selection sort process.

Animation Captions

Text descriptions that accompany visual representations of the selection sort algorithm.

Selection Sort

A sorting algorithm that repeatedly selects the smallest element from the unsorted portion of the array and moves it to the sorted portion.

indexSmallest

A variable that holds the index of the smallest remaining element in the selection sort algorithm.

O(N^2)

The runtime complexity of the selection sort algorithm, indicating that the number of comparisons grows quadratically with the number of elements.

Outer loop

The loop in the selection sort algorithm that iterates through each element of the array except the last one, executing N - 1 times.

Inner loop

The loop in the selection sort algorithm that compares elements to find the smallest one, executing an average of N/2 times for each outer loop iteration.

NUMBERS_SIZE

A constant representing the number of elements in the array, set to 8 in the provided example.

Sorting 50 elements

The indexSmallest is assigned to a minimum of 49 times when sorting an array with 50 elements.

Sorting 2X elements

Sorting 2X elements takes about 4 times longer than sorting X elements.

Sorting 10X elements

Sorting 10X elements takes about 25 times longer than sorting X elements.

SelectionSort method

A method that takes an array as a parameter and sorts it in-place without returning a value.

Swap

The action of exchanging the values of two elements in the array during the selection sort process.

Unsorted array

The initial state of the array before sorting, for example: {10, 2, 78, 4, 45, 32, 7, 11}.

Sorted array

The final state of the array after sorting, for example: {2, 4, 7, 10, 11, 32, 45, 78}.

Temporary variable

A variable used to hold a value temporarily during the swapping process in the selection sort algorithm.

Assignments to indexSmallest

The minimum number of times indexSmallest is assigned during the execution of the selection sort algorithm.

In-place sorting

A sorting method that requires no additional storage space, as the array is sorted within its original structure.

Algorithm

A step-by-step procedure or formula for solving a problem, such as sorting an array.

Complex algorithms

Sorting algorithms that involve more intricate processes but typically have faster execution times compared to selection sort.

Print function

A function used to output the elements of the array to the console, displaying both unsorted and sorted states.

Loop

A programming construct that repeats a block of code as long as a specified condition is true.

Array

A data structure that holds a fixed-size sequence of elements of the same type, such as integers.

Selection Sort

A sorting algorithm that repeatedly selects the smallest element from the unsorted portion and moves it to the sorted portion.

Insertion Sort

A sorting algorithm that treats the input as two parts, a sorted part and an unsorted part, and repeatedly inserts the next value from the unsorted part into the correct location in the sorted part.

SelectionSortDemo

A Java class that demonstrates the selection sort algorithm by sorting an array of integers.

Array

A data structure that holds a fixed number of values of a single type.

Comparisons

The number of times elements in the array are compared during the sorting process.

Outer Loop

The loop in the selection sort that iterates through each element of the array except the last one.

Inner Loop

The loop in the selection sort that finds the index of the smallest remaining element.

IndexSmallest

The variable that holds the index of the smallest element found in the unsorted portion of the array.

Temp Variable

A temporary variable used to facilitate the swapping of two elements in the array.

Unsorted Array

An array that has not yet been sorted.

Sorted Array

An array that has been arranged in a specific order, typically ascending.

Java

A high-level programming language used for building applications.

System.out.println

A Java statement used to print output to the console.

Numbers Array Example

An example array used in the selection sort demonstration: {10, 2, 78, 4, 45, 32, 7, 11}.

Final Value of i

The last value assigned to the variable i in the outer loop of the selection sort, which is numbers.length - 1.

Final Value of j

The last value assigned to the variable j in the inner loop of the selection sort, which is numbers.length.

Swapping Elements

The process of exchanging the values of two elements in an array.

While Loop

A control flow statement that allows code to be executed repeatedly based on a boolean condition.

Sorting Algorithms

Algorithms designed to arrange elements in a specific order, such as ascending or descending.

Activity 9.3.1

An exercise related to the selection sort algorithm, asking about variable assignments.

Activity 9.4.1

An exercise related to the insertion sort algorithm, demonstrating the sorting process.

Static Figure

A visual representation of an unsorted array and its sorted state.

Java.util.Arrays

A utility class in Java that contains various methods for manipulating arrays.

Item Comparisons

The total number of comparisons made between items in the array during the sorting process.

Variable i

The index of the first unsorted element, starting at 1 since the element at index 0 is already sorted.

Variable j

Keeps track of the index of the current element being inserted into the sorted part.

Swapping

The process of exchanging two elements in the array when the current element is less than the element to the left.

Sorted part

The portion of the array that is already sorted.

Unsorted part

The portion of the array that has not yet been sorted.

Correct location

The position in the sorted part where the current element should be inserted.

Outer i loop

The loop that iterates through each element in the unsorted part.

Inner while loop

The loop that inserts the current element into the sorted part by swapping until the correct position is found.

Final sorted array

The array after all elements from the unsorted part have been inserted into the sorted part, resulting in a fully sorted array.

Element comparisons

The checks made between the current element and the elements in the sorted part to determine if a swap is needed.

Three swaps

The number of times element 3 was swapped to move it to index 0 in the sorting process.

Final array

The sorted array resulting from the insertion sort: 3, 6, 15, 20, 32.

Index variable i

Denotes the starting position of the current element in the unsorted part.

Element at index 0

Assumed to be sorted in the initial state of the algorithm.

Current element

The element being processed and inserted into the sorted part.