3주차-정렬

선택정렬

-배열의 맨 처음 인덱스부터 마지막까지 돌면서 최솟값만을 선택해서 정렬

 input = [4, 6, 2, 9, 1]


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

selection_sort(input)
print(input) # [1, 2, 4, 6, 9] 가 되어야 합니다!

삽입정렬

-전체에서 하나씩 올바른 위치에 삽입하며 정렬
break문이 있어서 최선의 경우 O(N)이다.(버블과 선택정렬은 O(N^2))

input = [4, 6, 2, 9, 1]


def insertion_sort(array):
    for i in range(len(array)-1): #i=0,1,2,3,4
        for index in range(i,0-1,-1): #0/10/210/3210
            if array[index] > array[index+1]:
                array[index], array[index+1] = array[index+1], array[index]
            else:
                break
    return array



print(insertion_sort(input))
# print(input) # [1, 2, 4, 6, 9] 가 되어야 합니다!

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 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

병합(Merge)

• 내 코드

array_a = [1, 2, 3, 5]
array_b = [4, 6, 7, 8]


def merge(array1, array2):
    array_new =[]

    while array1 != [] and array2 != []:
        if array1[0] < array2[0]:
            array_new.append(array1[0])
            array1.pop(0)
        elif array1[0] > array2[0]:
            array_new.append(array2[0])
            array2.pop(0)
        continue

    if array1 == []:
        array_new += array2
    elif array2 == []:
        array_new += array1

    return array_new


print(merge(array_a, array_b))  # [1, 2, 3, 4, 5, 6, 7, 8] 가 되어야 합니다!

• 튜터님 코드

def merge(array1, array2):
    result = []
    array1_index = 0
    array2_index = 0
    while array1_index < len(array1) and array2_index < len(array2):
        if array1[array1_index] < array2[array2_index]:
            result.append(array1[array1_index])
            array1_index += 1
        else:
            result.append(array2[array2_index])
            array2_index += 1

    if array1_index == len(array1):
        while array2_index < len(array2):
            result.append(array2[array2_index])
            array2_index += 1

    if array2_index == len(array2):
        while array1_index < len(array1):
            result.append(array1[array1_index])
            array1_index += 1

    return result

=>처음에 튜터님 코드처럼 작성하다가 pop을 사용해 보았는데 나는 내 코드가 더 간단해 보여서 좋다!

병합정렬(MergeSort)

• 분할 정복(Divide and Conquer)은 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략

def merge_sort(array):
    if len(array) <= 1:   #탈출조건
        return array
    mid = (0 + len(array)) // 2
    left_array = merge_sort(array[:mid])   # 왼쪽 부분을 정렬하고
    right_array = merge_sort(array[mid:])  # 오른쪽 부분을 정렬한 다음에
    return merge(left_array, right_array)         # 합치면서 정렬하면 됩니다!
    
def merge(array1, array2): #O(N)
    result = []
    array1_index = 0
    array2_index = 0
    while array1_index < len(array1) and array2_index < len(array2):
        if array1[array1_index] < array2[array2_index]:
            result.append(array1[array1_index])
            array1_index += 1
        else:
            result.append(array2[array2_index])
            array2_index += 1

    if array1_index == len(array1):
        while array2_index < len(array2):
            result.append(array2[array2_index])
            array2_index += 1

    if array2_index == len(array2):
        while array1_index < len(array1):
            result.append(array1[array1_index])
            array1_index += 1

    return result

Stack/Queue/Hash

Stack

• 한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료 구조. (빨래통..)
• Last In First Out (LIFO)
• 넣은 순서가 필요할 때 사용
• 스택자료구조에서 제공하는 기능
  push(data) : 맨 앞에 데이터 넣기
  pop() : 맨 앞의 데이터 뽑기
  peek() : 맨 앞의 데이터 보기
  isEmpty(): 스택이 비었는지 안 비었는지 여부 반환해주기
  -데이터 넣고 뽑는 걸 자주하는 자료 구조 => 링크드리스트로 구현

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class Stack:
    def __init__(self):
        self.head = None

    # push 기능 구현
    def push(self, value):
        if self.is_empty():
            self.head = Node(value)
        else:
            new_head = Node(value)
            new_head.next = self.head
            self.head = new_head

    # pop 기능 구현
    def pop(self):
        if self.is_empty():
            return 'empty!'
        delete_head = self.head
        self.head = self.head.next
        return delete_head.data

    # peek 기능 구현
    def peek(self):
        if self.is_empty():
            return 'empty!'

        return self.head.data

    # isEmpty 기능 구현
    def is_empty(self):
        if self.head is None: # return self.head is None
            return True
        else:
            return False