September 18, 2022

1. 순차탐색

1.1 정의

찾고자 하는 결과에 대해서 순차적으로 하나씩 비교하며 탐색 하는 것을 말합니다.

이를 순차 탐색(sequential search)이라 정의합니다.

하나씩 비교하며 결과에 도달하는 방식이기 때문에 최악의 경우 전체 리스트의 모든 원소와 비교해야 하는 경우가 생기게 됩니다. 최악의 경우 n크기의 리스트에서 원소를 찾는경우 n 경우의 비교가 필요하며 이는 계산 복잡도 O(n)을 의미합니다.

1.2 코드구현

	# 순차탐색


	def sequentialSearch(numberList, targetValue):

		# 입력: numberList:숫자 리스트, targetValue: 찾는값

		# 출력: numberList에서  targetValue 의 index

		for index in range(0, len(numberList)):  #전체 리스트를 순차적으로 비교
			if targetValue == numberList[index]:

				return print(f'targetValue의 Index {index}')  # targetValue의 index

		return print('해당값은 존재하지 않습니다.')  #값이 없는 경우


	numList = [1, 2, 3, 4, 5]

	sequentialSearch(numList, 3)

	sequentialSearch(numList, 10)

	# numberList에서 중복된 값들에 대한 targetIndexList 만들기


	def getTargetList(numberList, targetValue):

		targetIndexList = []
		for index in range(0, len(numberList)):
			if targetValue == numberList[index]:
				targetIndexList.append(index)

		if targetIndexList:
			print(f'찾고자 하는 targetValueIndexList : {targetIndexList}')
		else:
			print("찾고자 하는 값이 존재하지 않습니다.")


	numberList = [1, 3, 3, 5]
	getTargetList(numberList, 3)
	getTargetList(numberList, 11)

2. 선택 정렬

2.1 정의

주어진 리스트를 순차적으로 선택 비교하여 원하는 크기의 순서로 정렬 하는 알고리즘을 말합니다.
가장 작은 값을 찾아서 가장 앞의 값과 교환하는 방식입니다.

주어진 리스트 중에 최소값을 찾는다.
그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 Θ(n2) 만큼의 시간이 걸린다.
선택 정렬은 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다.
비교 횟수가 입력 크기의 제곱에 비례하는 시간 복잡도가 O(n2)인 알고리즘

2.1 코드구현

#선택정렬
"""
given :
  numList = [1, 5, 3, 9, 7]

when :
  selectionSort(numList) # numList를 선택정렬을 구현한 함수에 인자로 전달

then :
  numList === [1, 3, 5, 7, 9] 오름 차순위로 정렬되어야 한다

"""


def sortingIndex(x, i, j):

    x[i], x[j] = x[j], x[i]


def selectionSort(numList):
    n = len(numList)
    for currentIndex in range(0, n - 1):
        changeIndex = currentIndex

        #currentIndex를 기준으로 전체 list를 비교하여 가장 작은 값의 index를 구한다.
        for compareIndex in range(currentIndex + 1, n):
            if numList[compareIndex] < numList[changeIndex]:
                changeIndex = compareIndex

        sortingIndex(numList, currentIndex, changeIndex)
        #print(numList)

numList = [4, 9, 2, 1, 3]
selectionSort(numList)
print(numList)

3. 삽입 정렬

3.1 정의

삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘을 말합니다.

k번째 반복 후의 결과 배열은, 앞쪽 k + 1 항목이 정렬된 상태이다.

주어진 리스트 중에 index = 1의 값 선택 (numList[i])
그 값을 맨 앞에 위치한 값과 교체
맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체
이미 정렬된 리스트의 경우가 아닌 경우 삽입 정렬의 계산 복잡도는 선택 정렬과 같은 O(n2)

3.1 코드구현

# 삽입 정렬

def insertSort(numList):
    n = len(numList)
    for i in range(1, n):
        insertValue = numList[i]

        compareIndex = i - 1 # insertValue의 바로 이전값

        while compareIndex >= 0 and numList[compareIndex] > insertValue:
            #compareIndex의 value가 더 큰 경우의 값을 바로 다음 값 위치로 변경
            numList[compareIndex + 1] = numList[compareIndex]
            #compareIndex의 앞 값들을 비교하기 위해서 index를 하나씩 감소
            compareIndex -= 1
        numList[compareIndex + 1] = insertValue  # 찾은 삽입 위치에 key를 저장


numList = [4, 2, 5, 1, 3, 9, 7]
insertSort(numList)
print(numList)