배열, 연결리스트, 선택정렬

<배열과 연결리스트>

	배열	리스트
읽기	O(1)	O(n)
삽입	O(n)	O(1)
삭제	O(n)	O(1)
접근 방식	임의 접근 random access	순차 접근 sequential access

<선택정렬 selection sort>

O(n) 실행시간이 걸리는 연산을 n번 해야 함 => O(n²)

배열의 모든 원소는 같은 자료형이어야 함

def findSmallest(arr):

smallest = arr[0]

smallest_index = 0

for i in range(1, len(arr)):

if arr[i] < smallest:

smallest = arr[i]

smallest_index = i

return smallest_index

def selectionSort(arr):

newArr = []

for i in range(len(arr)):

smallest = findSmallest(arr)

newArr.append(arr.pop(smallest))

return newArr

print selectionSort([5, 3, 6, 2, 10])