CS50 Week 3

• Linear search
• Binary search
• Bubble sort
• Selection sort
• Insertion sort
• Recursion
• Merge sort

 

 

---

Bubble Sort

def bubblesort(data):
    for index in range(len(data) - 1):
        for index2 in range(len(data) - index - 1):
            if data[index2] > data[index2 + 1]:
                data[index2], data[index2 + 1] = data[index2 + 1], data[index2]
    return data

• 반복문이 두 개 O(n2)
  • 최악의 경우, n∗(n−1)2
• 완전 정렬이 되어 있는 상태라면 최선은 O(n)

---

Selection Sort

def selection_sort(data):
    for stand in range(len(data) - 1):
        lowest = stand # set lowest idx
        for index in range(stand + 1, len(data)):
            if data[lowest] > data[index]:
                lowest = index # Find Lowest idx
        data[lowest], data[stand] = data[stand], data[lowest] # Replace lowest with current stand
    return data

def selection_sort(li):
    for i in range(len(li)-1):
        min_idx = i
        for j in range(i+1, len(li)):
            if li[min_idx] > li[j]:
                min_idx = j
        if min_idx != i:
            li[i], li[min_idx] = li[min_idx], li[i]
    return li

반복문이 두 개 O(n2)

• 실제로 상세하게 계산하면, n∗(n−1)2

---

Insertion Sort

def insertion_sort(data):
    for index in range(len(data) - 1):
        for index2 in range(index + 1, 0, -1): # backward
            if data[index2] < data[index2 - 1]:
                data[index2], data[index2 - 1] = data[index2 - 1], data[index2]
            else:
                break
    return data

def insertion_sort(li):
    for i in range(1, len(li)):
        j = i - 1
        key = li[i]
        while li[j] > key and j >= 0:
            li[j+1] = li[j]
            j = j -1
        li[j+1] = key
    return li

• 반복문이 두 개 O(n2)
  • 최악의 경우, n∗(n−1)2
• 완전 정렬이 되어 있는 상태라면 최선은 O(n)

---

Recursion

Pyramid printing

#include <cs50.h>
#include <stdio.h>

int main(void)
{
	int height = get_int("Height: ");
    
    draw(height);
}

void draw(int h)
{
	if (h==0):
    {
    	return;
    }                 //just error checking
    
    draw(h-1); // called before looping
    
    for (int i = 0; i < h; i++)
    {
    	printf("#")
    }
    printf("\n")
}

print h=4 pyramid

- called draw(h=4)

- called draw(h=3)

- called draw(h=2)

- called draw(h=1)

- called draw(h=0)

- print("#")

- print("##")

- print("###")

- print("####")

 

def factorial(num):
    if num > 1:
        return num * factorial(num - 1)
    else:
        return num

recursion

---

Merge Sort

재귀용법을 활용한 정렬 알고리즘

1. 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
2. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
3. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

def merge(left, right):
    merged = list()
    left_point, right_point = 0, 0 # increasing idx
    
    # case1 - left/right 둘다 있을때
    while len(left) > left_point and len(right) > right_point:
        if left[left_point] > right[right_point]: # right is small then append and move right idx +1
            merged.append(right[right_point])
            right_point += 1
        else:                               # left is small then append and move left idx +1
            merged.append(left[left_point])
            left_point += 1

    # case2
    while len(left) > left_point:       # 남은 left를 add
        merged.append(left[left_point])
        left_point += 1
        
    # case3
    while len(right) > right_point:    # 남은 right를 add
        merged.append(right[right_point])
        right_point += 1
    
    return merged


def mergesplit(data):
    if len(data) <= 1:
        return data
    medium = int(len(data) / 2)
    left = mergesplit(data[:medium])
    right = mergesplit(data[medium:])
    return merge(left, right)

 

 

---

출처:

• edx cs50
• fastcampus 알고리즘 / 기술면접 완전 정복 올인원 패키지 online