2022.11.11 TIL 알고리즘 정렬 / CPU

정렬

버블 정렬

배열의 첫 번째 원소부터 차례대로 비교하여 정렬

예시코드

input = [4, 6, 2, 9, 1]
 
 
def bubble_sort(array):
    n = len(array)
    for i in range(n):
        for j in range(n - i - 1):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]
    return array
 
bubble_sort(input)
print(input)
 
print("정답 = [1, 2, 4, 6, 9] / 현재 풀이 값 = ",bubble_sort([4, 6, 2, 9, 1]))
print("정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ",bubble_sort([3,-1,17,9]))
print("정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ",bubble_sort([100,56,-3,32,44]))

선택 정렬

정해진 기준에 따라 선택해서 부합하는 값을 먼저 정렬

 

예시코드

input = [4, 6, 2, 9, 1]
 
 
def selection_sort(array):
    n = len(array)
    for i in range(n - 1):
        min_index = i
        for j in range(n - i):
            if array[i + j] < array[min_index]:
                min_index = i + j
 
        array[i], array[min_index] = array[min_index], array[i]
    return array
 
 
selection_sort(input)
print(input)
 
print("정답 = [1, 2, 4, 6, 9] / 현재 풀이 값 = ",selection_sort([4, 6, 2, 9, 1]))
print("정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ",selection_sort([3,-1,17,9]))
print("정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ",selection_sort([100,56,-3,32,44]))

삽입 정렬

정렬 기준에 맞는 값을 중간에 삽입하는 정렬

예시코드

input = [4, 6, 2, 9, 1]
 
 
def insertion_sort(array):
    n = len(array)
    for i in range(1, n):
        for j in range(i):
            if array[i - j - 1] > array[i - j]:
                array[i - j - 1], array[i - j] = array[i - j], array[i - j - 1]
            else:
                break
    return array
 
insertion_sort(input)
print(input)
 
print("정답 = [4, 5, 7, 7, 8] / 현재 풀이 값 = ",insertion_sort([5,8,4,7,7]))
print("정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ",insertion_sort([3,-1,17,9]))
print("정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ",insertion_sort([100,56,-3,32,44]))

병합정렬

배열의 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복

 

예시코드

def merge_sort(array):
    if len(array) <= 1:
        return array
    mid = len(array) // 2
    left_array = array[:mid]
    right_array = array[mid:]
 
    return merge(merge_sort(left_array), merge_sort(right_array))

 

 

CPU<작성 중>

1. 싱글코어 > 멀티코어로 변화한 이유

   - 소비 전력과 발열 문제, 클럭 수에 따른 작업양 증가 효과 미미

2. CPU의 생김새

레지스터 
프로세서에 위치한 고속 메모리로, 극히 소량의 데이터나
처리 중인 중간 결과와도 같은, 프로세서가 바로 사용할 수 있는 데이터를 담고 있는 영역

캐시 메모리 
속도가 빠른 장치와 느린 장치에서 속도 차이에 따른 병목 현상을 줄이기 위한 메모리를 말한다. 
CPU가 주기억장치에서 저장된 데이터를 읽어올 때, 자주 사용하는 데이터를 캐시 메모리에 저장한 뒤, 
다음에 이용할 때 주기억장치가 아닌 캐시 메모리에서 먼저 가져오면서 속도를 향상시킨다.

 

3. CPU와 프로그래머는 어떻게 소통하는가

    기계어 - 어셈블리어 - 프로그래밍 언어

4. 명령어 수행 방법

명령어 인출 -> 명령어 해독        - >       실행 - >반영

CU                   opcode인출            

CPU----컴파일러----프로그래머

ISA 명령어 설정 아키텍쳐

CISC
RISC

ALU 산술논리연산
CU