📖 학습한 내용

• 선형 검색
• 이진 검색
• 순위
• 버블 정렬
• 삽입 정렬
• 선택 정렬

📖 핵심내용

📌 선형 검색

• 선형으로 나열되어 있는 데이터를 순차적으로 스캔하면서 원하는 값을 찾는다.
• 보초법
  마지막 인덱스에 찾으려는 값을 추가해서 찾는 과정을 간략화한다.

📌 이진 검색

가운데 데이터를 이용한다.
데이터가 정렬되어있어야한다.
중앙값과의 크고 작음을 이용해서 데이터를 검색한다.
자료구조가 엄청 클때 선형구조보다 효과적일 것 같다.
인덱스의 시작, 중간인덱스, 끝 인덱스를 초기화 시키면서 검색한다.

가장 처음에 끝값과 같은지 체크해야한다.

📌 순위

수의 크고작음을 이용해서 수의 순서를 정하는 것을 순위라고한다.
순차적으로 아이템 하나씩 비교해가면서 작은 숫자에 1씩 카운트하는 리스트를 만든다. 결국 가장 작은 숫자는 가장 많이 카운트되고, 가장 큰숫자는 한번도 카운트 되지 않으므로 순위가 저장된 리스트가 만들어진다. 이것을 이용해서 전체 자료의 순위를 알아낸다.
enumerate() 함수를 이용한다.

scores = random.sample(range(50, 101), 20)
ranks = [0 for i in range(20)]

for idx, sco1 in enumerate(scores):
    for sco2 in scores:
        if sco1 < sco2:
            ranks[idx] += 1

끝에서 바로 앞까지만 비교한다.

length = len(nums) - 1

📌 버블 정렬

처음부터 끝까지 차례로 비교한다. 하나씩 크기를 비교하여 자리를 바꿔간다. i를 빼서 마지막까지 않고 그 전단계까지 비교한다.
가장 마지막 전까지 비교한다.

• 두개의 값을 서로 바꾸는 코드

nums[j], nums[j+1] = nums[j+1], nums[j]

📌 삽입 정렬

정렬되어 있는 자료 배열과 비교해서 정렬 위치를 찾는다. 정렬이 이미 되어있는 것과 나 자신을 비교해서 자리를 찾아가는 방식이다.

• 이전 것보다 큰지 비교와 자리수가 0보다 작으면 종료하는 아이디어

while nums[i2] > cNum and i2 >= 0:
        nums[i2 + 1] = nums[i2]
        i2 -= 1

📖 흥미로운 점 / 새로 알게된 점

• 깊은복사, 앝은복사 (버블정렬)
  함수에 매개변수로 값을 줬을때, 어떤 값을 반환 받았다면, 그것은 얕은복사를 한 것이다. 따라서 원본도 함수 내부의 연산에 영향을 받는다.
  영향을 받지 않으려면 함수 내부에서 받은 값을 copy.copy() 안에 넣어 사용한다.
  이때 얕은복사, 깊은복사 둘 중 하나를 선택하려면, 매개변수를 하나더 만들면된다. 함수 매개변수를 정할때, 따로 지정하지 않으면 기본값으로 정의되는 성질을 이용한다.

def bubbleSort(ns, deepCopy = True):

    if deepCopy:
        cns = copy.copy(ns)
    else:
        cns = ns

    length = len(cns) - 1
    for i in range(length):
        for j in range(length - i):
            if cns[j] > cns[j + 1]:
                cns[j], cns[j + 1] = cns[j + 1], cns[j]

    return cns
    
sortedStudents = sm.bubbleSort(students, deepCopy=False)

📖 이후 학습 계획

• 선택 정렬
• 최댓값
• 최솟값
• 최빈값
• 근삿값
• 평균
• 재귀