Data Structures Part 2 Flashcards
Array
An ordered group of items, each of the same data type. The number of items is fixed in size. Each item is identified by a subscript.
Use Record When
The data is all about one object e.g. a person, a holiday.
The data is of different data types
Use array when
The data is about a number of different items.
The data is all of the same data type.
Record
A data structure that holds a number of related data values (possibly of different data types) , normally about the object.
Linear (sequential) search
A search where each record is examined in turn until required records is found or the end of the list is reached.
Binary search
A search on an ordered list where the middle item is inspected, if it is not the correct item, decide which half of the list contains the required value. Search that half of the list. Repeat the process.
half the list is discarded. This process is repeated.
Swapping
The process of exchanging the contents of two storage locations.
Bubble Sort
Work through the list examining pairs of records.
If a pair is in the wrong order then swap them.
keep passing through the list until no swaps are made.
Insertion Sort
Loop for each element in the unsorted part of the list.
Search through the list finding the position of the highest element.
Swap the highest element with the element at the top of the unsorted part of the list.
The top element is in the correct position so is now part of the sorted list.
Repeat until each item has been put in place.
Quick sort
Select the first element.
Partition the list so that those items less than the first item come after it and those items greater than the first item come before it.
The first item is then in it’s correct position.
Sort the two separate lists.
Quick Sort - Advantage
It is fastest/most efficient type of sort algorithm. It uses recursion
Sort choice depends on
The number of elements in the list. The amount of disorder in the list. If the data structure is sorted. The amount of temporary storage available Computer /processor speed Data type.
Pointer
A reference to a storage location, an address.
Class
A class consists of a description of all of the data in a record together with the operations that can be applied to it.
Data structure
It’s an organised group of related data items.
Static Data Structure
A data structure that is fixed in size, such as an array.