Linear arrays

From Computer Science Wiki
Jump to: navigation, search
Linear arrays[1]

There are four common algorithms we use on a linear array. Although the IB asks only for you to know these at the pseudocode level, I suggestPropose a solution, hypothesis or other possible answer. you memorize these for the rest of your life.

You will remember we use arrays to hold values of the same type at contiguous memory locations. In particular, the use of arrays allows us to create "groups" or "clusters" of variables without needing to give a unique variable name to each, but still allowing us to individually index into the elements of the array.[2]

Standard algorithms

  • Sequential search
  • Binary search
  • Bubble sort
  • Selection sort

Sequential search

In computer science, linear search or sequential search is a method for finding a target value within a listGive a sequence of brief answers with no explanation.. It sequentially checks each element of the listGive a sequence of brief answers with no explanation. for the target value until a match is found or until all the elements have been searched.[3]

Binary Search

In computer science, binary search, also known as half-interval search, is a search algorithm that finds the position of a target value within a sorted array (emphasis mine). Binary search compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful. If the search ends with the remaining half being empty, the target is not in the array.[4]

Bubble sort

Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the listGive a sequence of brief answers with no explanation. to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the listGive a sequence of brief answers with no explanation. is repeated until no swaps are needed, which indicates that the listGive a sequence of brief answers with no explanation. is sorted. [5]

def bubbleSort(list):
	swapped = True
	while swapped:
		swapped = False	
		for i in range(0,(len(list)-1)):	
			if list[i] > list[(i+1)]:
				firstNumber = list[i]
				secondNumber = list[(i+1)]
				list[i] = secondNumber
				list[(i+1)] = firstNumber
				swapped=True
	return list

Selection Sort

In computer science, selection sort is a sorting algorithm, specifically an in-place comparison sort. The algorithm divides the input listGive a sequence of brief answers with no explanation. into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the listGive a sequence of brief answers with no explanation., and the sublist of items remaining to be sorted that occupy the rest of the listGive a sequence of brief answers with no explanation.. Initially, the sorted sublist is empty and the unsorted sublist is the entire input listGive a sequence of brief answers with no explanation.. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.[6]

I'm grateful to wikipedia for the code below[7]

Sorted sublist == ( )
Unsorted sublist == (11, 25, 12, 22, 64)
Least element in unsorted list == 11

Sorted sublist ==  (11)
Unsorted sublist == (25, 12, 22, 64)
Least element in unsorted list == 12

Sorted sublist == (11, 12)
Unsorted sublist == (25, 22, 64)
Least element in unsorted list == 22

Sorted sublist == (11, 12, 22)
Unsorted sublist == (25, 64)
Least element in unsorted list == 25

Sorted sublist == (11, 12, 22, 25)
Unsorted sublist == (64)
Least element in unsorted list == 64

Sorted sublist == (11, 12, 22, 25, 64)
Unsorted sublist == ( )

Do you understand this?

This site is truly excellent resource to help you visually better understand sorting

Standards

These standards are used from the IB Computer Science Subject Guide[8]

  • DescribeGive a detailed account or picture of a situation, event, pattern or process. the characteristics of standard algorithms on linear arrays.

References