[크래프톤 정글 5기] week01 알고리즘 주차 다섯번째 날, CPU, 인스트럭션, 퀵 정렬(Quick Sort)

버스(Buses)

- 시스템 내를 관통하는 “전기적 배선군”

- 컴포넌트들 간에 “워드(word)라는 고정 크기의 바이트 단위”로 바이트 정보들을 전송한다

 

워드(word)

- 고정 크기의 바이트 단위

- 워드의 바이트 수는 시스템마다 보유하는 기본 시스템 변수이다.

- 대부분의 컴퓨터는 4바이트 또는 8바이트의 워드 크기를 갖는다

 

입출력 장치

- 시스템과 외부세계와의 연결을 담당한다

- 입력 : 키보드, 마우스 등

- 출력 : 디스플레이 등

 

메인 메모리

- 프로세서(CPU)가 프로그램을 실행하는 동안, 데이터와 프로그램을 모두 저장하는 “임시 저장장치”

- 물리적 메인 메모리는 "DRAM칩"들로 구성되어 있음

- 논리적 메모리는 연속적인 바이트들의 배열로, 0부터 시작해서 각각 고유주소(배열의 인덱스)를 가지고 있음

 

프로세서(CPU)

- 메인 메모리에 저장된 인스트럭션들을 해독(실행)하는 엔진

- 프로세서의 중심에는 레지스터인 "프로그램 카운터(PC)"가 있다

- 시스템에 전원이 공급되는 순간부터 끊임없이, 프로세서는 PC가 가리키는 인스트럭션을 반복적으로 실행하고 다음 인스트럭션의 위치를 가리키도록 업데이트 한다

 

인스트럭션(Instruction)

- CPU가 실행하는, "중앙처리장치의 작업 단위"이다

- 컴퓨터가 실행할 작업을 지시하는 명령어를 의미한다

- 산술연산 명령, 데이터를 읽어오는 명령, 조건문 평가, 분기 등 명령을 모두 포함한다

 

퀵 정렬(Quick sort)

- 일반적으로 사용되는 아주 빠른 정렬 알고리즘, 분할정복 알고리즘이다

- 복잡도는 O(N * logN)이며, 타 정렬 알고리즘에 비해 매우 빠르다

- 임의로 한 데이터를 선택하여 그걸 기준으로 정렬하여 그룹을 2개로 나누는 걸 반복한다. 이 기준은 피벗(pivot, 중심축) 이라고 한다. 각 그룹마다 각각의 피벗이 있고 각각 정렬이 이루어진다.

- 일반적으로 가장 좌측(맨 앞)의 데이터가 피벗이 되며, 모든 그룹이 1명씩 남으면 정렬이 완료된다

- 좌측, 우측에서 각각 진행하는 커서인 pl, pr을 사용한다.

- pl은 우측으로 진행하며 피벗보다 큰 값을 찾고, pr은 좌측으로 진행하며 피벗보다 작은 값을 찾는다.

 

 

아래는 퀵 정렬의 과정이다. 밑줄은 피벗, 빨간색은 정렬(고정)된 값이다.

빨간색의 정렬된 데이터를 기준으로 그룹이 나뉜다.

3 7 8 1 5 9 6 10 2 4

3 2 8 1 5 9 6 10 7 4

3 2 1 8 5 9 6 10 7 4

1 2 3 8 5 9 6 10 7 4

1 2 3 8 5 9 6 10 7 4

1 2 3 8 5 9 6 10 7 4

1 2 3 8 5 9 6 10 7 4

1 2 3 8 5 4 6 10 7 9

1 2 3 8 5 4 6 7 10 9

1 2 3 7 5 4 6 8 10 9

1 2 3 6 5 4 7 8 10 9

1 2 3 4 5 6 7 8 10 9

1 2 3 4 5 6 7 8 10 9

1 2 3 4 5 6 7 8 10 9

1 2 3 4 5 6 7 8 9 10

1 2 3 4 5 6 7 8 9 10

 

좌 -> 우 커서 : pl

우 -> 좌 커서 : pr

1. 가장 좌측 값 피벗으로 선택

2. pl은 피벗보다 큰 값, pr은 피벗보다 작은 값 선택

3. 두 값을 교환한 후, 해당 자리에서부터 다시 선택하고 교환 반복

4. 교환할 게 없어 pl과 pr이 교차되었으면 작은 값을 피벗과 교환한다.

5. 피벗이 교환되면, 교환된 피벗은 해당 위치에 정렬된다(위치고정).

6. 정렬된 값(기존피벗)을 기준으로 좌측은 작은 값, 우측은 큰 값만 존재한다. 두 그룹으로 분할되었다.

7. 각 그룹의 가장 좌측 값을 각각 피벗으로 설정한 후, 각각 정렬을 시작한다.

8. 엇갈렸거나, 선택할 값이 없을 때마다 작은 값을 피벗과 교환하거나(교환 후 기존피벗 정렬), 피벗이 가장 작은 값이면 정렬한다.

9. 반복한다.

 

아래는 퀵 정렬 파이썬 코드이다.

# array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

array = [3, 7, 8, 1, 5, 9, 6, 10, 2, 4]

def quick_sort(array, start, end): # start, end는 배열의 첫번째, 마지막 인덱스 / left, right는 커서

    if start >= end: # 원소가 1개인 경우 종료

        return

    pivot = start # 피벗은 첫 번째 원소

    left = start + 1 # 첫 번째는 피벗이므로, pl은 두 번째

    right = end

    while left <= right:

        # 피벗보다 큰 데이터를 찾을 때까지 반복

        while left <= end and array[left] <= array[pivot]:

            left += 1

        # 피벗보다 작은 데이터를 찾을 때까지 반복

        while right > start and array[right] >= array[pivot]:

            right -= 1

       

        if left > right: # 엇갈렸다면 작은 데이터와 피벗을 교체

            array[right], array[pivot] = array[pivot], array[right]

        else: # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체

            array[right], array[left] = array[left], array[right]

       

    quick_sort(array, start, right - 1)

    quick_sort(array, right + 1, end)

quick_sort(array, 0, len(array) -1)

print(array)

 

 

====추가=====

훨씬 간단한 퀵정렬 코드를 찾아서 업로드한다.

array = [3, 7, 8, 1, 5, 9, 6, 10, 2, 4]

def quick_sort(array):

    if len(array) <= 1:

        return array

    pivot = array[len(array) // 2]

    lesser_arr, equal_arr, greater_arr = [], [], []

    for num in array:

        if num < pivot:

            lesser_arr.append(num)

        elif num > pivot:

            greater_arr.append(num)

        else:

            equal_arr.append(num)

    return quick_sort(lesser_arr) + equal_arr + quick_sort(greater_arr)

print(quick_sort(array))

 

quick_sort() 함수는 피벗을 가운데 값으로 설정 후, 3개의 그룹으로 나눈다.

-> 피벗보다 작은 그룹 , 피벗과 동일한 그룹, 피벗보다 큰 그룹

 

그리고 작은그룹, 큰그룹을 대상으로 함수를 재귀호출하고, 피벗과 동일한 그룹과 더해버린다.

매우 간단하고 직관적이다.